Changeset 8a30b1 in git for factory/facFqFactorize.cc

Timestamp:

Jul 19, 2012, 12:14:06 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

4fee0ed1233fdc5967b5508da747cc77fe30de63

Parents:

e0af3ef0dd8793dabc30eac5d848f0b020acd362

git-author:

Martin Lee <martinlee84@web.de>2012-07-19 12:14:06+02:00

git-committer:

Martin Lee <martinlee84@web.de>2012-09-04 17:25:37+02:00

Message:

fix: bug in precomputation of leading coefficient

File:

• factory/facFqFactorize.cc (modified) (15 diffs)

factory/facFqFactorize.cc

@@ -1220 +1220 @@
       {
         CFListIterator iter1= result;
-        for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
+        for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
              iter2++, iter1++)
         {
@@ -1233 +1233 @@
 
   Variable v;
-  CFListIterator iter1;
+  CFListIterator iter1, iter2;
   CanonicalForm tmp, g;
+  CFList multiplier;
   for (int i= 0; i < length; i++)
   {
@@ -1243 +1244 @@
 
     v= Variable (i + 3);
-    for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
+    tmp= 1;
+    for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
          iter2++, iter1++)
     {
       if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v))
+      {
+        multiplier.append (1);
         continue;
-      tmp= iter1.getItem();
-      for (int j= tmp.level(); j > 1; j--)
-      {
-        if (j == i + 3)
-          continue;
-        tmp= tmp (0, j);
       }
       g= gcd (iter2.getItem(), content);
-      if (degree (g) > 0)
-      {
-        if (!tmp.isZero())
-          iter2.getItem() /= tmp;
-        content /= g;
-        iter1.getItem() *= g;
-      }
-    }
+      if (!g.inCoeffDomain())
+      {
+        tmp *= g;
+        multiplier.append (g);
+      }
+      else
+        multiplier.append (1);
+    }
+    if (!tmp.isOne() && fdivides (tmp, content))
+    {
+      iter1= l;
+      iter1++;
+      content /= tmp;
+      for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
+        iter1.getItem() *= iter2.getItem();
+    }
+    multiplier= CFList();
   }
 
@@ -1433 +1440 @@
 
   CFMap N, M;
-  CFArray dummy= CFArray (1);
+  CFArray dummy= CFArray (2);
   dummy [0]= LCF;
+  dummy [1]= Variable (2);
   compress (dummy, M, N);
   CanonicalForm F= M (LCF);
@@ -1486 +1494 @@
   CFList evalSqrfPartF, bufFactors;
   CFArray evalPoint= CFArray (evaluation.length() - 1);
+  CFArray buf= CFArray (evaluation.length());
+  CFArray swap= CFArray (evaluation.length());
   CFListIterator iter= evaluation;
-  for (int i= evaluation.length() - 2; i > -1; i--, iter++)
-    evalPoint[i]= iter.getItem();
+  CanonicalForm vars=getVars (LCF);
+  for (int i= evaluation.length() +1; i > 1; i--, iter++)
+  {
+    buf[i-2]=iter.getItem();
+    if (degree (vars, i) > 0)
+      swap[M(Variable (i)).level()-1]=buf[i-2];
+  }
+  buf= swap;
+  for (int i= 0; i < evaluation.length() - 1; i++)
+    evalPoint[i]= buf[i+1];
 
   int pass= testFactors (F, factors, alpha, sqrfPartF,
@@ -1501 +1519 @@
     // LCF is non-constant here
     CFList bufBufFactors;
-    CanonicalForm bufF, swap;
-    CFArray buf;
+    CanonicalForm bufF;
     for (int i= 0; i < lSecondVarLCs; i++)
     {
@@ -1528 +1545 @@
         bufBufFactors= bufFactors;
         evalPoint= CFArray (evaluation.length() - 1);
-        buf= CFArray (evaluation.length());
-        iter= evaluation;
-        int k= evaluation.length() - 1;
-        for (; iter.hasItem(); iter++, k--)
-          buf[k]= iter.getItem();
-        swap= buf[z.level() - 1];
-        buf[z.level() - 1]= buf[0];
-        buf[0]= 0;
-        int l= 0;
-        for (k= 0; k < evaluation.length(); k++)
-        {
-          if (buf[k].isZero())
-            continue;
-          evalPoint[l]= buf[k];
-          l++;
+        for (int k= 0; k < evaluation.length()-1; k++)
+        {
+          if (k+1 != lev)
+            evalPoint[k]= buf[k+1];
+          else
+            evalPoint[k]= buf[0];
         }
         pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
@@ -1585 +1593 @@
   bufFactors= factors;
   CFList evaluation2;
-  if (y == x)
-    evaluation2= evaluation;
-  else
-  {
-    CanonicalForm tmp;
-    evaluation2= evaluation;
-    int i= evaluation.length() + 1;
-    for (CFListIterator iter= evaluation2; iter.hasItem(); iter++, i--)
-    {
-      if (i == y.level())
-      {
-        tmp= iter.getItem();
-        iter.getItem()= evaluation2.getLast();
-        evaluation2.removeLast();
-        evaluation2.append (tmp);
-        break;
-      }
-    }
-  }
+  for (int i= 0; i < F.level()-1; i++)
+    evaluation2.insert (evalPoint[i]);
 
   CFList interMedResult;
   CanonicalForm oldSqrfPartF= sqrfPartF;
-  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
+  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
   if (factors.length() > 1)
   {
@@ -1615 +1606 @@
       leadingCoeffs.append (LC1);
 
-    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
+    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
     CFList oldFactors= factors;
     for (CFListIterator i= oldFactors; i.hasItem(); i++)
@@ -1624 +1615 @@
     if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
         LucksWangSparseHeuristic (oldSqrfPartFPowLC,
-                                  oldFactors, 1, leadingCoeffs, factors))
+                                  oldFactors, 2, leadingCoeffs, factors))
     {
       interMedResult= recoverFactors (oldSqrfPartF, factors);
@@ -1639 +1630 @@
 
       for (CFListIterator i= factors; i.hasItem(); i++)
-      {
-        i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
         i.getItem() *= LC1 (0,2)/Lc (i.getItem());
-      }
       factors.insert (1);
 
@@ -1686 +1674 @@
       }
       for (CFListIterator iter= factors; iter.hasItem(); iter++)
-        iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
+        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
 
       interMedResult=
-      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
+      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
                       factors);
     }
@@ -1916 +1904 @@
 }
 
+CFList conv (const CFArray & A)
+{
+  CFList result;
+  for (int i= A.max(); i >= A.min(); i--)
+    result.insert (A[i]);
+  return result;
+}
+
 void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
                        const CFList& uniFactors, const CFList& evaluation
@@ -1924 +1920 @@
   CFListIterator iter, iter2;
   Variable v;
-  CFList l, LCs, buf;
-  int pos;
+  CFList LCs, buf;
+  CFArray l;
+  int pos, index;
   for (int j= 0; j < A.level() - 2; j++)
   {
@@ -1946 +1943 @@
                                  evalPoint, v);
 
-      l= CFList();
       buf= buildUniFactors (Aeval[j], evalPoint, v);
-      for (iter= uniFactors; iter.hasItem(); iter++)
-      {
-        pos= findItem (buf, iter.getItem());
+      l= CFArray (uniFactors.length());
+      index= 1;
+      for (iter= buf; iter.hasItem(); iter++, index++)
+      {
+        pos= findItem (uniFactors, iter.getItem());
         if (pos)
-          l.append (getItem (Aeval[j], pos));
-      }
-      Aeval [j]= l;
-
+          l[pos-1]= getItem (Aeval[j], index);
+      }
+      buf= conv (l);
+      Aeval [j]= buf;
+
+      buf= buildUniFactors (Aeval[j], evalPoint, v);
       LCs= CFList();
       for (iter= Aeval[j]; iter.hasItem(); iter++)
         LCs.append (LC (iter.getItem(), 1));
-      normalize (LCs);
+      //normalize (LCs);
       Aeval[j]= LCs;
     }