Changeset 4f6d99 in git for factory/facAlgExt.cc

Timestamp:

Nov 14, 2012, 4:21:35 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '00e2e9c41af3fde1273eb3633f4c0c7c3db2579d')

Children:

70c40f240ce667ca18d03028aae0c90552755245

Parents:

f6237dd32a31b0c8c58f56d6a808bda992e743fa

git-author:

Martin Lee <martinlee84@web.de>2012-11-14 16:21:35+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-11-16 13:23:04+01:00

Message:

chg: better recovery of factors in univariate factorization over Q(a)

File:

• factory/facAlgExt.cc (modified) (4 diffs)

factory/facAlgExt.cc

@@ -35 +35 @@
 TIMING_DEFINE_PRINT(fac_alg_sqrf)
 TIMING_DEFINE_PRINT(fac_alg_factor_sqrf)
+TIMING_DEFINE_PRINT(fac_alg_time_shift)
 
 // squarefree part of F
@@ -126 +127 @@
   ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
   TIMING_START (fac_alg_factor_norm);
+  bool save_sort= !isOn (SW_USE_NTL_SORT);
+  On (SW_USE_NTL_SORT);
   CFFList normFactors= factorize (norm);
+  if (save_sort)
+    Off (SW_USE_NTL_SORT);
   TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
   CFList factors;
@@ -136 +141 @@
 
   normFactors.removeFirst();
+  CFFListIterator i= normFactors;
   CanonicalForm buf;
-  buf= f;
+  bool shiftBuf= false;
+  if (!(normFactors.length() == 2 && degree (i.getItem().factor()) <= degree (f)))
+  {
+    TIMING_START (fac_alg_time_shift);
+    if (shift != 0)
+      buf= f (f.mvar() - shift*alpha, f.mvar());
+    else
+      buf= f;
+    shiftBuf= true;
+    TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
+  }
+  else
+    buf= f;
   CanonicalForm factor;
   int count= 0;
-  for (CFFListIterator i= normFactors; i.hasItem(); i++)
+  for (; i.hasItem(); i++)
   {
     ASSERT (i.getItem().exp() == 1, "norm not squarefree");
     TIMING_START (fac_alg_gcd);
-    if (shift == 0)
+    if (shiftBuf)
       factor= gcd (buf, i.getItem().factor());
     else
-      factor= gcd (buf, i.getItem().factor() (f.mvar() + shift*alpha, f.mvar()));
+    {
+      if (shift == 0)
+        factor= gcd (buf, i.getItem().factor());
+      else
+        factor= gcd (buf, i.getItem().factor() (f.mvar() + shift*alpha, f.mvar()));
+    }
     buf /= factor;
+    if (shiftBuf)
+    {
+      if (shift != 0)
+        factor= factor (f.mvar() + shift*alpha, f.mvar());
+    }
     TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
     factors.append (factor);
@@ -154 +182 @@
     if (normFactors.length() - 1 == count)
     {
-      factors.append (buf);
+      if (shiftBuf)
+        factors.append (buf (f.mvar() + shift*alpha, f.mvar()));
+      else
+        factors.append (buf);
       buf= 1;
       break;