Changeset 4704674 in git

Timestamp:

Apr 26, 2012, 10:46:57 AM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

cb7827a842fd2e9878498f940e9f7735fdbe488e

Parents:

9f84ad2f3376850c4d78697edb203d32c07d3094

git-author:

Martin Lee <martinlee84@web.de>2012-04-26 10:46:57+02:00

git-committer:

Martin Lee <martinlee84@web.de>2012-05-07 14:16:24+02:00

Message:

chg: avoid divisibility tests
chg: use a bound on coeffs in chinrem_gcd

Location:

factory

Files:

• cf_gcd.cc (modified) (2 diffs)
• cf_gcd_smallp.cc (modified) (13 diffs)

factory/cf_gcd.cc

@@ -1237 +1237 @@
 
   CanonicalForm Dn, test= 0;
+  cl =  gcd (f.lc(),g.lc());
+  CanonicalForm b= 1;
+  int minCommonDeg= 0;
+  CanonicalForm gcdcfcg= gcd (cf, cg);
+  for (i= tmax (f.level(), g.level()); i > 0; i--)
+  {
+    if (degree (f, i) <= 0 || degree (g, i) <= 0)
+      continue;
+    else
+    {
+      minCommonDeg= tmin (degree (g, i), degree (f, i));
+      break;
+    }
+  }
+  if (i == 0)
+    return gcdcfcg;
+  for (; i > 0; i--)
+  {
+    if (degree (f, i) <= 0 || degree (g, i) <= 0)
+      continue;
+    else
+      minCommonDeg= tmin (minCommonDeg, tmin (degree (g, i), degree (f, i)));
+  }
+  b= 2*tmin (maxNorm (f), maxNorm (g))*abs (cl)*power (CanonicalForm (2), minCommonDeg);
   bool equal= false;
   i = cf_getNumBigPrimes() - 1;
-  cl =  gcd (f.lc(),g.lc());
-
-  CanonicalForm gcdcfcg= gcd (cf, cg);
+
   //Off (SW_RATIONAL);
   while ( true )
@@ -1307 +1329 @@
         equal= true;
       //Dn /=vcontent(Dn,Variable(1));
-      if (equal && fdivides( Dn, f ) && fdivides( Dn, g ) )
+      if ((equal || q > b) && fdivides( Dn, f ) && fdivides( Dn, g ) )
       {
         //printf(" -> success\n");

factory/cf_gcd_smallp.cc

@@ -560 +560 @@
   CanonicalForm prim_elem, im_prim_elem;
   CFList source, dest;
+  int bound= tmin (degree (ppA, 1), degree (ppB, 1));
+  int count= 0;
   do
   {
@@ -665 +667 @@
       G_m= 0;
       d= d0;
+      count= 0;
     }
 
@@ -672 +675 @@
                           "time for newton interpolation: ");
 
+    count++;
     //termination test
     if (uni_lcoeff (H) == gcdlcAlcB)
@@ -682 +686 @@
         //maybe it's better to test if ppH is an element of F(\alpha) before
         //mapping down
-        if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
+        DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
+        ppH= mapDown (ppH, prim_elem, im_prim_elem, alpha, u, v);
+        ppH /= Lc(ppH);
+        DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
+        if ((count == bound) || (fdivides (ppH, ppA) && fdivides (ppH, ppB)))
         {
           DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
@@ -693 +701 @@
         }
       }
-      else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
+      else if ((count == bound) || (fdivides (ppH, ppA) && fdivides (ppH, ppB)))
       {
         if (compressConvexDense)
@@ -882 +890 @@
   int expon;
   char gf_name_buf= gf_name;
+  int bound= tmin (degree (ppA, 1), degree (ppB, 1));
+  int count= 0;
   do
   {
@@ -963 +973 @@
       G_m= 0;
       d= d0;
+      count= 0;
     }
 
@@ -969 +980 @@
     TIMING_END_AND_PRINT (newton_interpolation, "time for newton interpolation: ");
 
+    count++;
     //termination test
     if (uni_lcoeff (H) == gcdlcAlcB)
@@ -976 +988 @@
       if (inextension)
       {
-        if (fdivides(ppH, ppA) && fdivides(ppH, ppB))
+        if ((count == bound) || (fdivides(ppH, ppA) && fdivides(ppH, ppB)))
         {
           DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
@@ -1186 +1198 @@
   topLevel= false;
   CFList source, dest;
+  int bound= tmin (degree (ppA, 1), degree (ppB, 1));
+  int count= 0;
   do
   {
@@ -1332 +1346 @@
       G_m= 0;
       d= d0;
+      count= 0;
     }
 
@@ -1339 +1354 @@
                           "time for newton_interpolation: ");
 
+    count++;
     //termination test
     if (uni_lcoeff (H) == gcdlcAlcB)
@@ -1346 +1362 @@
       ppH /= Lc (ppH);
       DEBOUTLN (cerr, "ppH= " << ppH);
-      if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
+      if ((count == bound) || (fdivides (ppH, ppA) && fdivides (ppH, ppB)))
       {
         if (compressConvexDense)