Changeset 5f92d8 in git

Timestamp:

Mar 6, 2012, 12:03:45 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '828514cf6e480e4bafc26df99217bf2a1ed1ef45')

Children:

4a0a30398a875d80f01a41e504fcf8ad0cfd7541

Parents:

4e6d2aac480d2946ef572d24bd5dd72906cf1e57

git-author:

Martin Lee <martinlee84@web.de>2012-03-06 12:03:45+01:00

git-committer:

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

Message:

chg: added coeff bound for polys over Q(a)
chg: renamed find_good_prime to findGoodPrime
chg: added coeffBound and findGoodPrime to facBivar.h

Location:

factory

Files:

• facBivar.cc (modified) (5 diffs)
• facBivar.h (modified) (1 diff)

factory/facBivar.cc

@@ -30 +30 @@
 TIMING_DEFINE_PRINT(hensel_lift12)
 
-static modpk
+// bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
+//                          Gelfond: Transcendental and Algebraic Numbers)
+modpk
 coeffBound ( const CanonicalForm & f, int p )
 {
     int * degs = degrees( f );
     int M = 0, i, k = f.level();
+    CanonicalForm b= 1;
     for ( i = 1; i <= k; i++ )
-        M += degs[i];
-    CanonicalForm b = 2 * maxNorm( f ) * power( CanonicalForm( 3 ), M );
+    {
+      M += degs[i];
+      b *= degs[i] + 1;
+    }
+    b /= power (CanonicalForm (2), k);
+    b= b.sqrt() + 1;
+    b *= 2 * maxNorm( f ) * power( CanonicalForm( 2 ), M );
     CanonicalForm B = p;
     k = 1;
@@ -47 +55 @@
 }
 
-static
-void find_good_prime(const CanonicalForm &f, int &start)
+void findGoodPrime(const CanonicalForm &f, int &start)
 {
   if (! f.inBaseDomain() )
@@ -57 +64 @@
       if  ( i.hasTerms() )
       {
-        find_good_prime(i.coeff(),start);
+        findGoodPrime(i.coeff(),start);
         if (0==cf_getBigPrime(start)) return;
         if((i.exp()!=0) && ((i.exp() % cf_getBigPrime(start))==0))
@@ -81 +88 @@
     }
   }
+}
+
+modpk
+coeffBound ( const CanonicalForm & f, int p, const CanonicalForm& mipo )
+{
+    int * degs = degrees( f );
+    int M = 0, i, k = f.level();
+    CanonicalForm K= 1;
+    for ( i = 1; i <= k; i++ )
+    {
+        M += degs[i];
+        K *= degs[i] + 1;
+    }
+    K /= power (CanonicalForm (2), k);
+    K= K.sqrt()+1;
+    K *= power (CanonicalForm (2), M);
+    int N= degree (mipo);
+    CanonicalForm b;
+    b= 2*power (maxNorm (f), N)*power (maxNorm (mipo), 4*N)*K*power (CanonicalForm (2), N)*(CanonicalForm (M+1).sqrt()+1)*power (CanonicalForm (N+1).sqrt()+1, 7*N);
+    b /= power (abs (lc (mipo)), N);
+
+    ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
+    ZZX NTLLcf= convertFacCF2NTLZZX (Lc (f));
+    ZZ NTLf= resultant (NTLmipo, NTLLcf);
+    ZZ NTLD= discriminant (NTLmipo);
+    b /= abs (convertZZ2CF (NTLf))*abs (convertZZ2CF (NTLD));
+
+    CanonicalForm B = p;
+    k = 1;
+    while ( B < b ) {
+        B *= p;
+        k++;
+    }
+    return modpk( p, k );
 }
 
@@ -591 +632 @@
     Off (SW_RATIONAL);
     int i= 0;
-    find_good_prime(F,i);
-    find_good_prime(Aeval,i);
-    find_good_prime(A,i);
+    findGoodPrime(F,i);
+    findGoodPrime(Aeval,i);
+    findGoodPrime(A,i);
     if (i >= cf_getNumBigPrimes())
       printf ("out of primes\n"); //TODO exit

factory/facBivar.h

@@ -275 +275 @@
             );
 
+modpk
+coeffBound ( const CanonicalForm & f, int p, const CanonicalForm& mipo );
+
+void findGoodPrime(const CanonicalForm &f, int &start);
+
+modpk
+coeffBound ( const CanonicalForm & f, int p );
+
 #endif