Changeset 1ade96 in git

Timestamp:

Feb 16, 2012, 4:35:20 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

f9bd3df575b00ad6b5b1f49bf42ebe194e4bb7b2

Parents:

667ba13dd7bcac6f144c71d80aad80c7fe86c3cd

git-author:

Martin Lee <martinlee84@web.de>2012-02-16 16:35:20+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-04-04 14:42:26+02:00

Message:

chg: use coeff bound in bivariate poly factorization over Q

File:

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

factory/facBivar.cc

@@ -24 +24 @@
 #include "facHensel.h"
 #include "facMul.h"
+#include "cf_primes.h"
 
 #ifdef HAVE_NTL
 TIMING_DEFINE_PRINT(uni_factorize)
 TIMING_DEFINE_PRINT(hensel_lift12)
+
+static modpk
+coeffBound ( const CanonicalForm & f, int p )
+{
+    int * degs = degrees( f );
+    int M = 0, i, k = f.level();
+    for ( i = 1; i <= k; i++ )
+        M += degs[i];
+    CanonicalForm b = 2 * maxNorm( f ) * power( CanonicalForm( 3 ), M );
+    CanonicalForm B = p;
+    k = 1;
+    while ( B < b ) {
+        B *= p;
+        k++;
+    }
+    return modpk( p, k );
+}
+
+static
+void find_good_prime(const CanonicalForm &f, int &start)
+{
+  if (! f.inBaseDomain() )
+  {
+    CFIterator i = f;
+    for(;;)
+    {
+      if  ( i.hasTerms() )
+      {
+        find_good_prime(i.coeff(),start);
+        if (0==cf_getSmallPrime(start)) return;
+        if((i.exp()!=0) && ((i.exp() % cf_getSmallPrime(start))==0))
+        {
+          start++;
+          i=f;
+        }
+        else  i++;
+      }
+      else break;
+    }
+  }
+  else
+  {
+    if (f.inZ())
+    {
+      if (0==cf_getSmallPrime(start)) return;
+      while((!f.isZero()) && (mod(f,cf_getSmallPrime(start))==0))
+      {
+        start++;
+        if (0==cf_getSmallPrime(start)) return;
+      }
+    }
+  }
+}
 
 CFList conv (const CFFList& L)
@@ -528 +582 @@
   }
 
-  if (!extension)
-  {
-    for (CFListIterator i= uniFactors; i.hasItem(); i++)
-      i.getItem() /= lc (i.getItem());
-  }
-
   A= A (y + evaluation, y);
 
   int liftBound= degree (A, y) + 1;
+
+  modpk b= modpk();
+  if ( !extension)
+  {
+    Off (SW_RATIONAL);
+    int i= 0;
+    do
+    {
+      find_good_prime(F,i);
+      find_good_prime(Aeval,i);
+      find_good_prime(A,i);
+      setCharacteristic (cf_getSmallPrime(i));
+      if (gcd (Aeval.mapinto(), deriv (Aeval,x).mapinto()).inCoeffDomain())
+      {
+        setCharacteristic (0);
+        break;
+      }
+      else
+        i++;
+      if (i > cf_getNumSmallPrimes())
+      {
+        printf ("out of primes\n");
+        break;
+      }
+    } while (1);
+
+    int p=cf_getSmallPrime(i);
+    b = coeffBound( A, p );
+    modpk bb= coeffBound (Aeval, p);
+    if (bb.getk() > b.getk() ) b=bb;
+      bb= coeffBound (F, p);
+    if (bb.getk() > b.getk() ) b=bb;
+  }
 
   ExtensionInfo dummy= ExtensionInfo (false);
@@ -545 +626 @@
   uniFactors= henselLiftAndEarly
               (A, earlySuccess, earlyFactors, degs, liftBound,
-               uniFactors, dummy, evaluation);
+               uniFactors, dummy, evaluation, b);
   TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
   DEBOUTLN (cerr, "lifted factors= " << uniFactors);
@@ -552 +633 @@
 
   factors= factorRecombination (uniFactors, A, MODl, degs, 1,
-                                uniFactors.length()/2);
+                                uniFactors.length()/2, b);
+
+  if (!extension)
+    On (SW_RATIONAL);
 
   if (earlySuccess)