source: git/factory/facFactorize.cc @ c89740

spielwiese
Last change on this file since c89740 was 5dad7c7, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: minor improvements chg: check if distribution of leading coeff by variables is applicable
  • Property mode set to 100644
File size: 46.4 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.cc
5 *
6 * multivariate factorization over Q(a)
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13#include "config.h"
14
15#include "assert.h"
16#include "debug.h"
17#include "timing.h"
18
19#include "cf_algorithm.h"
20#include "facFqFactorizeUtil.h"
21#include "facFactorize.h"
22#include "facFqFactorize.h"
23#include "cf_random.h"
24#include "facHensel.h"
25#include "cf_gcd_smallp.h"
26#include "cf_map_ext.h"
27#include "algext.h"
28#include "cf_reval.h"
29#include "facSparseHensel.h"
30
31TIMING_DEFINE_PRINT(fac_bi_factorize)
32TIMING_DEFINE_PRINT(fac_hensel_lift)
33TIMING_DEFINE_PRINT(fac_factor_recombination)
34
35#ifdef HAVE_NTL
36CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
37{
38  CFList result;
39  Variable x= Variable (1);
40
41  bool found= false;
42  bool allZero= true;
43  bool foundZero= false;
44  CanonicalForm deriv_x, gcd_deriv;
45  CFListIterator iter;
46  do
47  {
48    eval.insert (F);
49    bool bad= false;
50    for (int i= E.max(); i >= E.min(); i--)
51    {
52      eval.insert (eval.getFirst()( E [i], i));
53      result.append (E[i]);
54      if (!E[i].isZero())
55        allZero= false;
56      else
57        foundZero= true;
58      if (!allZero && foundZero)
59      {
60        result= CFList();
61        eval= CFList();
62        bad= true;
63        foundZero= false;
64        break;
65      }
66      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
67      {
68        result= CFList();
69        eval= CFList();
70        bad= true;
71        break;
72      }
73    }
74
75    if (bad)
76    {
77      E.nextpoint();
78      continue;
79    }
80
81    if (degree (eval.getFirst()) != degree (F, 1))
82    {
83      result= CFList();
84      eval= CFList();
85      E.nextpoint();
86      continue;
87    }
88
89    deriv_x= deriv (eval.getFirst(), x);
90    gcd_deriv= gcd (eval.getFirst(), deriv_x);
91    if (degree (gcd_deriv) > 0)
92    {
93      result= CFList();
94      eval= CFList();
95      E.nextpoint();
96      continue;
97    }
98    iter= eval;
99    iter++;
100    CanonicalForm contentx= content (iter.getItem(), x);
101    if (degree (contentx) > 0)
102    {
103      result= CFList();
104      eval= CFList();
105      E.nextpoint();
106      continue;
107    }
108    found= true;
109  }
110  while (!found);
111
112  if (!eval.isEmpty())
113    eval.removeFirst();
114  return result;
115}
116
117void
118factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
119                                     int& minFactorsLength, bool& irred,
120                                     const Variable& w)
121{
122  Variable x= Variable (1);
123  minFactorsLength= 0;
124  irred= false;
125  Variable v;
126  CFList factors;
127  CanonicalForm LCA= LC (A,1);
128  if (!LCA.inCoeffDomain())
129  {
130    for (int j= 0; j < A.level() - 2; j++)
131    {
132      if (!Aeval[j].isEmpty() && (degree (LCA, j+3) > 0))
133      {
134        v= Variable (Aeval[j].getFirst().level());
135
136        factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
137
138        if (factors.getFirst().inCoeffDomain())
139          factors.removeFirst();
140
141        if (minFactorsLength == 0)
142          minFactorsLength= factors.length();
143        else
144          minFactorsLength= tmin (minFactorsLength, factors.length());
145
146        if (factors.length() == 1)
147        {
148          irred= true;
149          return;
150        }
151        sortList (factors, x);
152        Aeval [j]= factors;
153      }
154      else if (!Aeval[j].isEmpty())
155      {
156        Aeval[j]=CFList();
157      }
158    }
159  }
160  else
161  {
162    for (int j= 0; j < A.level() - 2; j++)
163      Aeval[j]= CFList();
164  }
165}
166
167int
168testFactors (const CanonicalForm& G, const CFList& uniFactors,
169             CanonicalForm& sqrfPartF, CFList& factors,
170             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
171             const CFArray& evalPoint)
172{
173  CanonicalForm tmp;
174  CFListIterator j;
175  for (CFListIterator i= uniFactors; i.hasItem(); i++)
176  {
177    tmp= i.getItem();
178    if (i.hasItem())
179      i++;
180    else
181      break;
182    for (j= i; j.hasItem(); j++)
183    {
184      if (tmp == j.getItem())
185        return 0;
186    }
187  }
188
189  CanonicalForm F= G;
190  CFFList sqrfFactorization= sqrFree (F);
191
192  sqrfPartF= 1;
193  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
194    sqrfPartF *= i.getItem().factor();
195
196  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
197
198  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
199
200  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
201    return 0;
202
203  CFFList sqrfFactors;
204  CFList tmp2;
205  int k= 0;
206  factors= uniFactors;
207  CFFListIterator iter;
208  for (CFListIterator i= factors; i.hasItem(); i++, k++)
209  {
210    tmp= 1;
211    sqrfFactors= sqrFree (i.getItem());
212
213    for (iter= sqrfFactors; iter.hasItem(); iter++)
214    {
215      tmp2.append (iter.getItem().factor());
216      tmp *= iter.getItem().factor();
217    }
218    i.getItem()= tmp/Lc(tmp);
219    bufSqrfFactors [k]= sqrfFactors;
220  }
221
222  for (int i= 0; i < factors.length() - 1; i++)
223  {
224    for (int k= i + 1; k < factors.length(); k++)
225    {
226      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
227    }
228  }
229
230  factors= CFList();
231  for (int i= 0; i < uniFactors.length(); i++)
232  {
233    if (i == 0)
234    {
235      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
236      {
237        if (iter.getItem().factor().inCoeffDomain())
238          continue;
239        iter.getItem()= CFFactor (iter.getItem().factor()/
240                                  Lc (iter.getItem().factor()),
241                                  iter.getItem().exp());
242        factors.append (iter.getItem().factor());
243      }
244    }
245    else
246    {
247      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
248      {
249        if (iter.getItem().factor().inCoeffDomain())
250          continue;
251        iter.getItem()= CFFactor (iter.getItem().factor()/
252                               Lc (iter.getItem().factor()),
253                               iter.getItem().exp());
254        if (!find (factors, iter.getItem().factor()))
255          factors.append (iter.getItem().factor());
256      }
257    }
258  }
259
260  test= prod (factors);
261  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
262  if (test/Lc (test) != tmp/Lc (tmp))
263    return 0;
264  else
265    return 1;
266}
267
268CFList
269precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
270                        const CFList& evaluation,CFList*& differentSecondVarLCs,
271                        int length, Variable& y
272                       )
273{
274  y= Variable (1);
275  if (LCF.inCoeffDomain())
276  {
277    CFList result;
278    for (int i= 1; i <= LCFFactors.length() + 1; i++)
279      result.append (1);
280    return result;
281  }
282
283  CFMap N, M;
284  CFArray dummy= CFArray (2);
285  dummy [0]= LCF;
286  dummy [1]= Variable (2);
287  compress (dummy, M, N);
288  CanonicalForm F= M (LCF);
289  if (LCF.isUnivariate())
290  {
291    CFList result;
292    int LCFLevel= LCF.level();
293    bool found= false;
294    if (LCFLevel == 2)
295    {
296    //bivariate leading coefficients are already the true leading coefficients
297      result= LCFFactors;
298      found= true;
299    }
300    else
301    {
302      CFListIterator j;
303      for (int i= 0; i < length; i++)
304      {
305        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
306        {
307          if (j.getItem().level() == LCFLevel)
308          {
309            found= true;
310            break;
311          }
312        }
313        if (found)
314        {
315          result= differentSecondVarLCs [i];
316          break;
317        }
318      }
319      if (!found)
320        result= LCFFactors;
321    }
322    if (found)
323      result.insert (Lc (LCF));
324    else
325      result.append (LCF);
326    return result;
327  }
328
329  CFList factors= LCFFactors;
330
331  for (CFListIterator i= factors; i.hasItem(); i++)
332    i.getItem()= M (i.getItem());
333
334  CanonicalForm sqrfPartF;
335  CFFList * bufSqrfFactors= new CFFList [factors.length()];
336  CFList evalSqrfPartF, bufFactors;
337  CFArray evalPoint= CFArray (evaluation.length() - 1);
338  CFArray buf= CFArray (evaluation.length());
339  CFArray swap= CFArray (evaluation.length());
340  CFListIterator iter= evaluation;
341  CanonicalForm vars=getVars (LCF)*Variable (2);
342  for (int i= evaluation.length() +1; i > 1; i--, iter++)
343  {
344    buf[i-2]=iter.getItem();
345    if (degree (vars, i) > 0)
346      swap[M(Variable (i)).level()-1]=buf[i-2];
347  }
348  buf= swap;
349  for (int i= 0; i < evaluation.length() - 1; i++)
350    evalPoint[i]= buf[i+1];
351
352  //TODO sqrfPartF einmal berechnen nicht stÀndig
353  int pass= testFactors (F, factors, sqrfPartF,
354                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
355
356  bool foundDifferent= false;
357  Variable z;
358  Variable x= y;
359  int j= 0;
360  if (!pass)
361  {
362    int lev= 0;
363    CanonicalForm bufF;
364    CFList bufBufFactors;
365    for (int i= 0; i < length; i++)
366    {
367      if (!differentSecondVarLCs [i].isEmpty())
368      {
369        bool allConstant= true;
370        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
371        {
372          if (!iter.getItem().inCoeffDomain())
373          {
374            allConstant= false;
375            y= Variable (iter.getItem().level());
376            lev= M(y).level();
377          }
378        }
379        if (allConstant)
380          continue;
381
382        bufFactors= differentSecondVarLCs [i];
383        for (iter= bufFactors; iter.hasItem(); iter++)
384          iter.getItem()= swapvar (iter.getItem(), x, y);
385        bufF= F;
386        z= Variable (lev);
387        bufF= swapvar (bufF, x, z);
388        bufBufFactors= bufFactors;
389        evalPoint= CFArray (evaluation.length() - 1);
390        for (int k= 0; k < evaluation.length()-1; k++)
391        {
392          if (N (Variable (k+1)).level() != y.level())
393            evalPoint[k]= buf[k+1];
394          else
395            evalPoint[k]= buf[0];
396        }
397        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
398                           bufSqrfFactors, evalSqrfPartF, evalPoint);
399        if (pass)
400        {
401          foundDifferent= true;
402          F= bufF;
403          CFList l= factors;
404          for (iter= l; iter.hasItem(); iter++)
405            iter.getItem()= swapvar (iter.getItem(), x, y);
406          differentSecondVarLCs [i]= l;
407          j= i;
408          break;
409        }
410        if (!pass && i == length - 1)
411        {
412          CFList result;
413          result.append (LCF);
414          for (int j= 1; j <= factors.length(); j++)
415            result.append (1);
416          result= distributeContent (result, differentSecondVarLCs, length);
417          if (!result.getFirst().inCoeffDomain())
418          {
419            CFListIterator iter= result;
420            CanonicalForm tmp= iter.getItem();
421            iter++;
422            for (; iter.hasItem(); iter++)
423              iter.getItem() *= tmp;
424          }
425
426          y= Variable (1);
427          delete [] bufSqrfFactors;
428          return result;
429        }
430      }
431    }
432  }
433  if (!pass)
434  {
435    CFList result;
436    result.append (LCF);
437    for (int j= 1; j <= factors.length(); j++)
438      result.append (LCF);
439    y= Variable (1);
440    delete [] bufSqrfFactors;
441    return result;
442  }
443  else
444    factors= bufFactors;
445
446
447  bufFactors= factors;
448
449  CFMap MM, NN;
450  dummy [0]= sqrfPartF;
451  dummy [1]= 1;
452  compress (dummy, MM, NN);
453  sqrfPartF= MM (sqrfPartF);
454  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
455  for (CFListIterator iter= factors; iter.hasItem(); iter++)
456    iter.getItem()= MM (iter.getItem());
457
458  CFList evaluation2;
459  for (int i= 2; i <= varsSqrfPartF.level(); i++)
460    evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
461
462  CFList interMedResult;
463  CanonicalForm oldSqrfPartF= sqrfPartF;
464  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
465  if (factors.length() > 1)
466  {
467    CanonicalForm LC1= LC (oldSqrfPartF, 1);
468    CFList leadingCoeffs;
469    for (int i= 0; i < factors.length(); i++)
470      leadingCoeffs.append (LC1);
471
472    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
473    CFList oldFactors= factors;
474    for (CFListIterator i= oldFactors; i.hasItem(); i++)
475      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
476
477    bool success= false;
478    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
479    CFList heuResult;
480    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
481        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
482                                  oldFactors, 2, leadingCoeffs, heuResult))
483    {
484      interMedResult= recoverFactors (oldSqrfPartF, heuResult);
485      if (oldFactors.length() == interMedResult.length())
486        success= true;
487    }
488    if (!success)
489    {
490      LC1= LC (evalSqrfPartF.getFirst(), 1);
491
492      CFArray leadingCoeffs= CFArray (factors.length());
493      for (int i= 0; i < factors.length(); i++)
494        leadingCoeffs[i]= LC1;
495
496      for (CFListIterator i= factors; i.hasItem(); i++)
497        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
498      factors.insert (1);
499
500      CanonicalForm
501      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
502
503      int liftBound= degree (newSqrfPartF,2) + 1;
504
505      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
506      CFArray Pi;
507      CFList diophant;
508      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
509                            leadingCoeffs, false);
510
511      if (sqrfPartF.level() > 2)
512      {
513        int* liftBounds= new int [sqrfPartF.level() - 1];
514        liftBounds [0]= liftBound;
515        bool noOneToOne= false;
516        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
517        LC1= LC (evalSqrfPartF.getLast(), 1);
518        CFList LCs;
519        for (int i= 0; i < factors.length(); i++)
520          LCs.append (LC1);
521        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
522        for (int i= sqrfPartF.level() - 1; i > 2; i--)
523        {
524          for (CFListIterator j= LCs; j.hasItem(); j++)
525            j.getItem()= j.getItem() (0, i + 1);
526          leadingCoeffs2 [i - 3]= LCs;
527        }
528        sqrfPartF *= power (LC1, factors.length()-1);
529
530        int liftBoundsLength= sqrfPartF.level() - 1;
531        for (int i= 1; i < liftBoundsLength; i++)
532          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
533        evalSqrfPartF= evaluateAtZero (sqrfPartF);
534        evalSqrfPartF.removeFirst();
535        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
536                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
537        delete [] leadingCoeffs2;
538        delete [] liftBounds;
539      }
540      for (CFListIterator iter= factors; iter.hasItem(); iter++)
541        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
542
543      interMedResult=
544      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
545                      factors);
546    }
547  }
548  else
549  {
550    CanonicalForm contF=content (oldSqrfPartF,1);
551    factors= CFList (oldSqrfPartF/contF);
552    interMedResult= recoverFactors (oldSqrfPartF, factors);
553  }
554
555  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
556    iter.getItem()= NN (iter.getItem());
557
558  CFList result;
559  CFFListIterator k;
560  CanonicalForm tmp;
561  for (int i= 0; i < LCFFactors.length(); i++)
562  {
563    tmp= 1;
564    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
565    {
566      int pos= findItem (bufFactors, k.getItem().factor());
567      if (pos)
568        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
569    }
570    result.append (tmp);
571  }
572
573  for (CFListIterator i= result; i.hasItem(); i++)
574  {
575    F /= i.getItem();
576    if (foundDifferent)
577      i.getItem()= swapvar (i.getItem(), x, z);
578    i.getItem()= N (i.getItem());
579  }
580
581  if (foundDifferent)
582  {
583    CFList l= differentSecondVarLCs [j];
584    for (CFListIterator i= l; i.hasItem(); i++)
585      i.getItem()= swapvar (i.getItem(), y, z);
586    differentSecondVarLCs [j]= l;
587    F= swapvar (F, x, z);
588  }
589
590  result.insert (N (F));
591
592  result= distributeContent (result, differentSecondVarLCs, length);
593
594  if (!result.getFirst().inCoeffDomain())
595  {
596    CFListIterator i= result;
597    CanonicalForm tmp;
598    if (foundDifferent)
599      i.getItem()= swapvar (i.getItem(), Variable (2), y);
600
601    tmp= i.getItem();
602
603    i++;
604    for (; i.hasItem(); i++)
605    {
606      if (foundDifferent)
607        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
608      else
609        i.getItem() *= tmp;
610    }
611  }
612  else
613    y= Variable (1);
614
615  delete [] bufSqrfFactors;
616
617  return result;
618}
619
620
621CFList
622multiFactorize (const CanonicalForm& F, const Variable& v)
623{
624  if (F.inCoeffDomain())
625    return CFList (F);
626
627  // compress and find main Variable
628  CFMap N;
629  CanonicalForm A= myCompress (F, N);
630
631  //univariate case
632  if (F.isUnivariate())
633  {
634    CFList result;
635    if (v.level() != 1)
636      result= conv (factorize (F, v));
637    else
638      result= conv (factorize (F,true));
639    if (result.getFirst().inCoeffDomain())
640      result.removeFirst();
641    return result;
642  }
643
644  //bivariate case
645  if (A.level() == 2)
646  {
647    CFList buf= biFactorize (F, v);
648    return buf;
649  }
650
651  Variable x= Variable (1);
652  Variable y= Variable (2);
653
654  // remove content
655  CFList contentAi;
656  CanonicalForm lcmCont= lcmContent (A, contentAi);
657  A /= lcmCont;
658
659  // trivial after content removal
660  CFList contentAFactors;
661  if (A.inCoeffDomain())
662  {
663    for (CFListIterator i= contentAi; i.hasItem(); i++)
664    {
665      if (i.getItem().inCoeffDomain())
666        continue;
667      else
668      {
669        lcmCont /= i.getItem();
670        contentAFactors=
671        Union (multiFactorize (lcmCont, v),
672               multiFactorize (i.getItem(), v));
673        break;
674      }
675    }
676    decompress (contentAFactors, N);
677    if (isOn (SW_RATIONAL))
678      normalize (contentAFactors);
679    return contentAFactors;
680  }
681
682  // factorize content
683  contentAFactors= multiFactorize (lcmCont, v);
684
685  // univariate after content removal
686  CFList factors;
687  if (A.isUnivariate ())
688  {
689    if (v.level() != 1)
690      factors= conv (factorize (A, v));
691    else
692      factors= conv (factorize (A,true));
693    append (factors, contentAFactors);
694    decompress (factors, N);
695    return factors;
696  }
697
698  A *= bCommonDen (A);
699  // check main variable
700  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
701  int factorNums= 3;
702  CanonicalForm bivarEval;
703  CFList biFactors, bufBiFactors;
704  CanonicalForm evalPoly;
705  int lift, bufLift, lengthAeval2= A.level()-2;
706  CFList* bufAeval2= new CFList [lengthAeval2];
707  CFList* Aeval2= new CFList [lengthAeval2];
708  int counter;
709  int differentSecondVar= 0;
710  CanonicalForm bufA;
711  // several bivariate factorizations
712  REvaluation E (2, A.level(), IntRandom (25));
713  for (int i= 0; i < factorNums; i++)
714  {
715    counter= 0;
716    bufA= A;
717    bufAeval= CFList();
718    bufEvaluation= evalPoints (bufA, bufAeval, E);
719    E.nextpoint();
720    evalPoly= 0;
721
722    bivarEval= bufEvaluation.getLast();
723
724    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
725
726    for (int j= 0; j < A.level() - 1; j++)
727    {
728      if (!bufAeval2[j].isEmpty())
729        counter++;
730    }
731
732    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
733
734    TIMING_START (fac_bi_factorize);
735    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
736    TIMING_END_AND_PRINT (fac_bi_factorize,
737                          "time for bivariate factorization: ");
738    bufBiFactors.removeFirst();
739
740    if (bufBiFactors.length() == 1)
741    {
742      factors.append (A);
743      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
744      if (isOn (SW_RATIONAL))
745        normalize (factors);
746      delete [] bufAeval2;
747      delete [] Aeval2;
748      return factors;
749    }
750
751    if (i == 0)
752    {
753      Aeval= bufAeval;
754      evaluation= bufEvaluation;
755      biFactors= bufBiFactors;
756      lift= bufLift;
757      for (int j= 0; j < lengthAeval2; j++)
758        Aeval2 [j]= bufAeval2 [j];
759      differentSecondVar= counter;
760    }
761    else
762    {
763      if (bufBiFactors.length() < biFactors.length() ||
764          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
765          counter > differentSecondVar)
766      {
767        Aeval= bufAeval;
768        evaluation= bufEvaluation;
769        biFactors= bufBiFactors;
770        lift= bufLift;
771        for (int j= 0; j < lengthAeval2; j++)
772          Aeval2 [j]= bufAeval2 [j];
773        differentSecondVar= counter;
774      }
775    }
776    int k= 0;
777    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
778      evalPoly += j.getItem()*power (x, k);
779    list.append (evalPoly);
780  }
781
782  delete [] bufAeval2;
783
784  sortList (biFactors, x);
785
786  int minFactorsLength;
787  bool irred= false;
788  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
789
790  if (irred)
791  {
792    factors.append (A);
793    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
794    if (isOn (SW_RATIONAL))
795      normalize (factors);
796    delete [] Aeval2;
797    return factors;
798  }
799
800  if (minFactorsLength == 0)
801    minFactorsLength= biFactors.length();
802  else if (biFactors.length() > minFactorsLength)
803    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
804
805  if (differentSecondVar == lengthAeval2 && getNumVars(LC(A,1)) == A.level()-1)
806  {
807    bool zeroOccured= false;
808    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
809    {
810      if (iter.getItem().isZero())
811      {
812        zeroOccured= true;
813        break;
814      }
815    }
816    if (!zeroOccured)
817    {
818      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
819                                minFactorsLength);
820      if (factors.length() == biFactors.length())
821      {
822        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
823        normalize (factors);
824        delete [] Aeval2;
825        return factors;
826      }
827      else
828        factors= CFList();
829      //TODO case where factors.length() > 0
830    }
831  }
832
833  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
834
835  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
836
837  CFList * oldAeval= new CFList [lengthAeval2];
838  for (int i= 0; i < lengthAeval2; i++)
839    oldAeval[i]= Aeval2[i];
840
841  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
842
843  CFList biFactorsLCs;
844  for (CFListIterator i= biFactors; i.hasItem(); i++)
845    biFactorsLCs.append (LC (i.getItem(), 1));
846
847  Variable w;
848  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
849                                          evaluation, Aeval2, lengthAeval2, w);
850
851  if (w.level() != 1)
852  {
853    A= swapvar (A, y, w);
854    int i= A.level();
855    CanonicalForm evalPoint;
856    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
857    {
858      if (i == w.level())
859      {
860        evalPoint= iter.getItem();
861        iter.getItem()= evaluation.getLast();
862        evaluation.removeLast();
863        evaluation.append (evalPoint);
864        break;
865      }
866    }
867    for (i= 0; i < lengthAeval2; i++)
868    {
869      if (oldAeval[i].isEmpty())
870        continue;
871      if (oldAeval[i].getFirst().level() == w.level())
872      {
873        CFArray tmp= copy (oldAeval[i]);
874        oldAeval[i]= biFactors; 
875        for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
876          iter.getItem()= swapvar (iter.getItem(), w, y);
877        for (int ii= 0; ii < tmp.size(); ii++)
878          tmp[ii]= swapvar (tmp[ii], w, y);
879        CFArray tmp2= CFArray (tmp.size());
880        CanonicalForm buf;
881        for (int ii= 0; ii < tmp.size(); ii++)
882        {
883          buf= tmp[ii] (evaluation.getLast(),y);
884          buf /= Lc (buf);
885          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
886        }
887        biFactors= CFList();
888        for (int j= 0; j < tmp2.size(); j++)
889          biFactors.append (tmp2[j]);
890      }
891    }
892  }
893
894  CFListIterator iter;
895  CanonicalForm oldA= A;
896  CFList oldBiFactors= biFactors;
897  if (!leadingCoeffs.getFirst().inCoeffDomain())
898  {
899    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
900    A *= tmp;
901    tmp= leadingCoeffs.getFirst();
902    iter= evaluation;
903    for (int i= A.level(); i > 2; i--, iter++)
904      tmp= tmp (iter.getItem(), i);
905    if (!tmp.inCoeffDomain())
906    {
907      for (CFListIterator i= biFactors; i.hasItem(); i++)
908      {
909        i.getItem() *= tmp/LC (i.getItem(), 1);
910        i.getItem() /= Lc (i.getItem());
911      }
912    }
913  }
914
915  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
916  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
917  leadingCoeffs.removeFirst();
918
919  //prepare leading coefficients
920  CFList* leadingCoeffs2= new CFList [lengthAeval2];
921  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
922                        evaluation);
923
924
925  Aeval= evaluateAtEval (A, evaluation, 2);
926
927  CanonicalForm hh= Lc (Aeval.getFirst());
928
929  for (iter= Aeval; iter.hasItem(); iter++)
930    iter.getItem() /= hh;
931
932  A /= hh;
933
934  CFListIterator iter2;
935  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
936  bufBiFactors= biFactors;
937  bufA= A;
938  CanonicalForm bufLCmultiplier= LCmultiplier;
939  CanonicalForm testVars;
940  if (!LCmultiplierIsConst)
941  {
942    testVars= Variable (2);
943    for (int i= 0; i < lengthAeval2; i++)
944    {
945      if (!oldAeval[i].isEmpty())
946        testVars *= oldAeval[i].getFirst().mvar();
947    }
948  }
949  CFList bufFactors= CFList();
950  bool LCheuristic= false;
951  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
952                                factors))
953  {
954    int check= biFactors.length();
955    int * index= new int [factors.length()];
956    CFList oldFactors= factors;
957    factors= recoverFactors (A, factors, index);
958
959    if (check == factors.length())
960    {
961      if (w.level() != 1)
962      {
963        for (iter= factors; iter.hasItem(); iter++)
964          iter.getItem()= swapvar (iter.getItem(), w, y);
965      }
966
967      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
968      normalize (factors);
969      delete [] index;
970      delete [] Aeval2;
971      return factors;
972    }
973    else if (factors.length() > 0)
974    {
975      int oneCount= 0;
976      CFList l;
977      for (int i= 0; i < check; i++)
978      {
979        if (index[i] == 1)
980        {
981          iter=biFactors;
982          for (int j=1; j <= i-oneCount; j++)
983            iter++;
984          iter.remove (1);
985          for (int j= 0; j < lengthAeval2; j++)
986          {
987            l= leadingCoeffs2[j];
988            iter= l;
989            for (int k=1; k <= i-oneCount; k++)
990              iter++;
991            iter.remove (1);
992            leadingCoeffs2[j]=l;
993          }
994          oneCount++;
995        }
996      }
997      bufFactors= factors;
998      factors= CFList();
999    }
1000    else if (!LCmultiplierIsConst && factors.length() == 0)
1001    {
1002      LCheuristic= true;
1003      factors= oldFactors;
1004      CanonicalForm cont;
1005      CFList contents, LCs;
1006      int index=1;
1007      bool foundTrueMultiplier= false;
1008      for (iter= factors; iter.hasItem(); iter++, index++)
1009      {
1010        cont= content (iter.getItem(), 1);
1011        cont= gcd (cont , LCmultiplier);
1012        contents.append (cont);
1013        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
1014        {
1015          foundTrueMultiplier= true;
1016          int index2= 1;
1017          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
1018                                                                    index2++)
1019          {
1020            if (index2 == index)
1021              continue;
1022            iter2.getItem() /= LCmultiplier;
1023          }
1024          A= oldA;
1025          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1026          for (int i= lengthAeval2-1; i > -1; i--)
1027            leadingCoeffs2[i]= CFList();
1028          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
1029                                biFactors, evaluation );
1030          Aeval= evaluateAtEval (A, evaluation, 2);
1031
1032          hh= Lc (Aeval.getFirst());
1033
1034          for (iter2= Aeval; iter2.hasItem(); iter2++)
1035            iter2.getItem() /= hh;
1036
1037          A /= hh;
1038          break;
1039        }
1040        else
1041          LCs.append (LC (iter.getItem()/cont, 1));
1042      }
1043      if (!foundTrueMultiplier)
1044      {
1045        index= 1;
1046        iter2= factors;
1047        bool foundMultiplier= false;
1048        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1049        {
1050          if (fdivides (iter.getItem(), LCmultiplier))
1051          {
1052            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
1053                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
1054            {
1055              int index2= 1;
1056              for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
1057                   iter3.hasItem(); iter3++, index2++)
1058              {
1059                if (index2 == index)
1060                {
1061                  iter3.getItem() /= LCmultiplier;
1062                  break;
1063                }
1064              }
1065              A /= LCmultiplier;
1066              foundMultiplier= true;
1067              iter.getItem()= 1;
1068            }
1069          }
1070        }
1071        // coming from above: divide out more LCmultiplier if possible
1072        if (foundMultiplier)
1073        {
1074          foundMultiplier= false;
1075          index=1;
1076          iter2= factors;
1077          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1078          {
1079            if (!iter.getItem().isOne() &&
1080                fdivides (iter.getItem(), LCmultiplier))
1081            {
1082              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
1083              {
1084                int index2= 1;
1085                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1086                     iter2++, index2++)
1087                {
1088                  if (index2 == index)
1089                  {
1090                    iter2.getItem() /= iter.getItem();
1091                    foundMultiplier= true;
1092                    break;
1093                  }
1094                }
1095                A /= iter.getItem();
1096                LCmultiplier /= iter.getItem();
1097                iter.getItem()= 1;
1098              }
1099              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
1100              {
1101                Variable xx= Variable (2);
1102                CanonicalForm vars;
1103                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
1104                                          xx));
1105                for (int i= 0; i < lengthAeval2; i++)
1106                {
1107                  if (oldAeval[i].isEmpty())
1108                    continue;
1109                  xx= oldAeval[i].getFirst().mvar();
1110                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
1111                                             xx));
1112                }
1113                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
1114                    /myGetVars (LCmultiplier) == vars)
1115                {
1116                  int index2= 1;
1117                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1118                       iter2++, index2++)
1119                  {
1120                    if (index2 == index)
1121                    {
1122                      iter2.getItem() /= LCmultiplier;
1123                      foundMultiplier= true;
1124                      break;
1125                    }
1126                  }
1127                  A /= LCmultiplier;
1128                  iter.getItem()= 1;
1129                }
1130              }
1131            }
1132          }
1133        }
1134        else
1135        {
1136          CanonicalForm pLCs= prod (LCs);
1137          if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
1138          {
1139            A= oldA;
1140            iter2= leadingCoeffs2[lengthAeval2-1];
1141            for (iter= contents; iter.hasItem(); iter++, iter2++)
1142              iter2.getItem() /= iter.getItem();
1143            foundMultiplier= true;
1144          }
1145          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
1146          {
1147            Variable xx;
1148            CFList vars1;
1149            CFFList sqrfMultiplier= sqrFree (LCmultiplier);
1150            if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
1151              sqrfMultiplier.removeFirst();
1152            sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
1153            xx= Variable (2);
1154            for (iter= oldBiFactors; iter.hasItem(); iter++)
1155              vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
1156            for (int i= 0; i < lengthAeval2; i++)
1157            {
1158              if (oldAeval[i].isEmpty())
1159                continue;
1160              xx= oldAeval[i].getFirst().mvar();
1161              iter2= vars1;
1162              for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
1163                iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
1164            }
1165            CanonicalForm tmp;
1166            iter2= vars1;
1167            for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
1168                                                                    iter2++)
1169            {
1170              tmp= iter.getItem()/LCmultiplier;
1171              for (int i=1; i <= tmp.level(); i++)
1172              {
1173                if (degree (tmp, i) > 0)
1174                  iter2.getItem() /= power (Variable (i), degree (tmp,i));
1175              }
1176            }
1177            int multi;
1178            for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
1179            {
1180              multi= 0;
1181              for (iter= vars1; iter.hasItem(); iter++)
1182              {
1183                tmp= iter.getItem();
1184                while (fdivides (myGetVars (ii.getItem().factor()), tmp))
1185                {
1186                  multi++;
1187                  tmp /= myGetVars (ii.getItem().factor());
1188                }
1189              }
1190              if (multi == ii.getItem().exp())
1191              {
1192                index= 1;
1193                for (iter= vars1; iter.hasItem(); iter++, index++)
1194                {
1195                  while (fdivides (myGetVars(ii.getItem().factor()),
1196                                   iter.getItem()
1197                                  )
1198                        )
1199                  {
1200                    int index2= 1;
1201                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1202                         iter2++, index2++)
1203                    {
1204                      if (index2 == index)
1205                        continue;
1206                      else
1207                      {
1208                        tmp= ii.getItem().factor();
1209                        iter2.getItem() /= tmp;
1210                        CFListIterator iter3= evaluation;
1211                        for (int jj= A.level(); jj > 2; jj--, iter3++)
1212                          tmp= tmp (iter3.getItem(), jj);
1213                        if (!tmp.inCoeffDomain())
1214                        {
1215                          int index3= 1;
1216                          for (iter3= biFactors; iter3.hasItem(); iter3++,
1217                                                                  index3++)
1218                          {
1219                            if (index3 == index2)
1220                            {
1221                              iter3.getItem() /= tmp;
1222                              iter3.getItem() /= Lc (iter3.getItem());
1223                              break;
1224                            }
1225                          }
1226                        }
1227                        A /= ii.getItem().factor();
1228                      }
1229                    }
1230                    iter.getItem() /= getVars (ii.getItem().factor());
1231                  }
1232                }
1233              }
1234              else
1235              {
1236                index= 1;
1237                for (iter= vars1; iter.hasItem(); iter++, index++)
1238                {
1239                  if (!fdivides (myGetVars (ii.getItem().factor()),
1240                                 iter.getItem()
1241                                )
1242                     )
1243                  {
1244                    int index2= 1;
1245                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1246                         iter2++, index2++)
1247                    {
1248                      if (index2 == index)
1249                      {
1250                        tmp= power (ii.getItem().factor(), ii.getItem().exp());
1251                        iter2.getItem() /= tmp;
1252                        A /= tmp;
1253                        CFListIterator iter3= evaluation;
1254                        for (int jj= A.level(); jj > 2; jj--, iter3++)
1255                          tmp= tmp (iter3.getItem(), jj);
1256                        if (!tmp.inCoeffDomain())
1257                        {
1258                          int index3= 1;
1259                          for (iter3= biFactors; iter3.hasItem(); iter3++,
1260                                                                  index3++)
1261                          {
1262                            if (index3 == index2)
1263                            {
1264                              iter3.getItem() /= tmp;
1265                              iter3.getItem() /= Lc (iter3.getItem());
1266                              break;
1267                            }
1268                          }
1269                        }
1270                      }
1271                    }
1272                  }
1273                }
1274              }
1275            }
1276          }
1277        }
1278
1279        // patch everything together again
1280        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1281        for (int i= lengthAeval2-1; i > -1; i--)
1282          leadingCoeffs2[i]= CFList();
1283        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1284                              evaluation);
1285        Aeval= evaluateAtEval (A, evaluation, 2);
1286
1287        hh= Lc (Aeval.getFirst());
1288
1289        for (CFListIterator i= Aeval; i.hasItem(); i++)
1290          i.getItem() /= hh;
1291
1292        A /= hh;
1293      }
1294      factors= CFList();
1295      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
1296      {
1297        LCheuristic= false;
1298        A= bufA;
1299        biFactors= bufBiFactors;
1300        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1301        LCmultiplier= bufLCmultiplier;
1302      }
1303    }
1304    else
1305      factors= CFList();
1306    delete [] index;
1307  }
1308  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
1309      && fdivides (getVars (LCmultiplier), testVars))
1310  {
1311    int index;
1312    Variable xx;
1313    CFList vars1;
1314    CFFList sqrfMultiplier= sqrFree (LCmultiplier);
1315    if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
1316      sqrfMultiplier.removeFirst();
1317    sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
1318    xx= Variable (2);
1319    for (iter= oldBiFactors; iter.hasItem(); iter++)
1320      vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
1321    for (int i= 0; i < lengthAeval2; i++)
1322    {
1323      if (oldAeval[i].isEmpty())
1324        continue;
1325      xx= oldAeval[i].getFirst().mvar();
1326      iter2= vars1;
1327      for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
1328        iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
1329    }
1330    CanonicalForm tmp;
1331    iter2= vars1;
1332    for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
1333    {
1334      tmp= iter.getItem()/LCmultiplier;
1335      for (int i=1; i <= tmp.level(); i++)
1336      {
1337        if (degree (tmp, i) > 0)
1338          iter2.getItem() /= power (Variable (i), degree (tmp,i));
1339      }
1340    }
1341    int multi;
1342    for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
1343    {
1344      multi= 0;
1345      for (iter= vars1; iter.hasItem(); iter++)
1346      {
1347        tmp= iter.getItem();
1348        while (fdivides (myGetVars (ii.getItem().factor()), tmp))
1349        {
1350          multi++;
1351          tmp /= myGetVars (ii.getItem().factor());
1352        }
1353      }
1354      if (multi == ii.getItem().exp())
1355      {
1356        index= 1;
1357        for (iter= vars1; iter.hasItem(); iter++, index++)
1358        {
1359          while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
1360          {
1361            int index2= 1;
1362            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
1363                                                                      index2++)
1364            {
1365              if (index2 == index)
1366                continue;
1367              else
1368              {
1369                tmp= ii.getItem().factor();
1370                iter2.getItem() /= tmp;
1371                CFListIterator iter3= evaluation;
1372                for (int jj= A.level(); jj > 2; jj--, iter3++)
1373                  tmp= tmp (iter3.getItem(), jj);
1374                if (!tmp.inCoeffDomain())
1375                {
1376                  int index3= 1;
1377                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
1378                  {
1379                    if (index3 == index2)
1380                    {
1381                      iter3.getItem() /= tmp;
1382                      iter3.getItem() /= Lc (iter3.getItem());
1383                      break;
1384                    }
1385                  }
1386                }
1387                A /= ii.getItem().factor();
1388              }
1389            }
1390            iter.getItem() /= getVars (ii.getItem().factor());
1391          }
1392        }
1393      }
1394      else
1395      {
1396        index= 1;
1397        for (iter= vars1; iter.hasItem(); iter++, index++)
1398        {
1399          if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
1400          {
1401            int index2= 1;
1402            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
1403                                                                      index2++)
1404            {
1405              if (index2 == index)
1406              {
1407                tmp= power (ii.getItem().factor(), ii.getItem().exp());
1408                iter2.getItem() /= tmp;
1409                A /= tmp;
1410                CFListIterator iter3= evaluation;
1411                for (int jj= A.level(); jj > 2; jj--, iter3++)
1412                  tmp= tmp (iter3.getItem(), jj);
1413                if (!tmp.inCoeffDomain())
1414                {
1415                  int index3= 1;
1416                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
1417                  {
1418                    if (index3 == index2)
1419                    {
1420                      iter3.getItem() /= tmp;
1421                      iter3.getItem() /= Lc (iter3.getItem());
1422                      break;
1423                    }
1424                  }
1425                }
1426              }
1427            }
1428          }
1429        }
1430      }
1431    }
1432
1433    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1434    for (int i= lengthAeval2-1; i > -1; i--)
1435      leadingCoeffs2[i]= CFList();
1436    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1437                          evaluation);
1438    Aeval= evaluateAtEval (A, evaluation, 2);
1439
1440    hh= Lc (Aeval.getFirst());
1441
1442    for (CFListIterator i= Aeval; i.hasItem(); i++)
1443      i.getItem() /= hh;
1444
1445    A /= hh;
1446  }
1447
1448tryAgainWithoutHeu:
1449  //shifting to zero
1450  A= shift2Zero (A, Aeval, evaluation);
1451
1452  for (iter= biFactors; iter.hasItem(); iter++)
1453    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1454
1455  for (int i= 0; i < lengthAeval2-1; i++)
1456    leadingCoeffs2[i]= CFList();
1457  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
1458  {
1459    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
1460    for (int i= A.level() - 4; i > -1; i--)
1461    {
1462      if (i + 1 == lengthAeval2-1)
1463        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
1464      else
1465        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
1466    }
1467  }
1468
1469  CFArray Pi;
1470  CFList diophant;
1471  int* liftBounds= new int [A.level() - 1];
1472  int liftBoundsLength= A.level() - 1;
1473  for (int i= 0; i < liftBoundsLength; i++)
1474    liftBounds [i]= degree (A, i + 2) + 1;
1475
1476  Aeval.removeFirst();
1477  bool noOneToOne= false;
1478
1479  CFList commonDenominators;
1480  for (iter=biFactors; iter.hasItem(); iter++)
1481    commonDenominators.append (bCommonDen (iter.getItem()));
1482  CanonicalForm tmp1, tmp2, tmp3=1;
1483  for (int i= 0; i < lengthAeval2; i++)
1484  {
1485    iter2= commonDenominators;
1486    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1487    {
1488      tmp1= bCommonDen (iter.getItem());
1489      Off (SW_RATIONAL);
1490      iter2.getItem()= lcm (iter2.getItem(), tmp1);
1491      On (SW_RATIONAL);
1492    }
1493  }
1494  tmp1= prod (commonDenominators);
1495  for (iter= Aeval; iter.hasItem(); iter++)
1496  {
1497    tmp2= bCommonDen (iter.getItem());
1498    Off (SW_RATIONAL);
1499    tmp3= lcm (tmp2,tmp3);
1500    On (SW_RATIONAL);
1501  }
1502  CanonicalForm multiplier;
1503  multiplier= tmp3/tmp1;
1504  iter2= commonDenominators;
1505  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
1506    iter.getItem() *= iter2.getItem()*multiplier;
1507
1508  for (iter= Aeval; iter.hasItem(); iter++)
1509    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
1510
1511  for (int i= 0; i < lengthAeval2; i++)
1512  {
1513    iter2= commonDenominators;
1514    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1515      iter.getItem() *= iter2.getItem()*multiplier;
1516  }
1517
1518
1519  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
1520                               Pi, liftBounds, liftBoundsLength, noOneToOne);
1521
1522  if (!noOneToOne)
1523  {
1524    int check= factors.length();
1525    A= oldA;
1526    factors= recoverFactors (A, factors, evaluation);
1527    if (check != factors.length())
1528      noOneToOne= true;
1529    else
1530      factors= Union (factors, bufFactors);
1531  }
1532  if (noOneToOne)
1533  {
1534    if (!LCmultiplierIsConst && LCheuristic)
1535    {
1536      A= bufA;
1537      biFactors= bufBiFactors;
1538      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1539      delete [] liftBounds;
1540      LCheuristic= false;
1541      goto tryAgainWithoutHeu;
1542      //something probably went wrong in the heuristic
1543    }
1544
1545    A= shift2Zero (oldA, Aeval, evaluation);
1546    biFactors= oldBiFactors;
1547    for (iter= biFactors; iter.hasItem(); iter++)
1548      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1549    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
1550    CanonicalForm yToLift= power (y, lift);
1551    CFListIterator i= biFactors;
1552    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
1553    i++;
1554
1555    for (; i.hasItem(); i++)
1556      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
1557
1558    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
1559
1560    i= biFactors;
1561    yToLift= power (y, lift);
1562    CanonicalForm dummy;
1563    for (; i.hasItem(); i++)
1564    {
1565      LCA= LC (i.getItem(), 1);
1566      extgcd (LCA, yToLift, LCA, dummy);
1567      i.getItem()= mod (i.getItem()*LCA, yToLift);
1568    }
1569
1570    liftBoundsLength= F.level() - 1;
1571    liftBounds= liftingBounds (A, lift);
1572
1573    CFList MOD;
1574    bool earlySuccess;
1575    CFList earlyFactors;
1576    ExtensionInfo info= ExtensionInfo (false);
1577    CFList liftedFactors;
1578    TIMING_START (fac_hensel_lift);
1579    liftedFactors= henselLiftAndEarly
1580                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
1581                    Aeval, biFactors, evaluation, info);
1582    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
1583
1584    TIMING_START (fac_factor_recombination);
1585    factors= factorRecombination (A, liftedFactors, MOD);
1586    TIMING_END_AND_PRINT (fac_factor_recombination,
1587                          "time for factor recombination: ");
1588
1589    if (earlySuccess)
1590      factors= Union (factors, earlyFactors);
1591
1592    for (CFListIterator i= factors; i.hasItem(); i++)
1593    {
1594      int kk= Aeval.getLast().level();
1595      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
1596      {
1597        if (i.getItem().level() < kk)
1598          continue;
1599       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
1600      }
1601    }
1602  }
1603
1604  if (w.level() != 1)
1605  {
1606    for (CFListIterator iter= factors; iter.hasItem(); iter++)
1607      iter.getItem()= swapvar (iter.getItem(), w, y);
1608  }
1609
1610  swap (factors, 0, 0, x);
1611  append (factors, contentAFactors);
1612  decompress (factors, N);
1613  if (isOn (SW_RATIONAL))
1614    normalize (factors);
1615
1616  delete [] leadingCoeffs2;
1617  delete [] oldAeval;
1618  delete [] Aeval2;
1619  delete[] liftBounds;
1620
1621  return factors;
1622}
1623
1624#endif
Note: See TracBrowser for help on using the repository browser.