Changeset e7676a in git for factory/cf_gcd.cc

Timestamp:

May 7, 2012, 3:55:50 PM (12 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

517530b37f04ee705b7b271243a265748c447cf5dccd6db99cc44c93669e843ddb6e06d2682769b8

Parents:

a034968a1bff5f6e4e9ad126551a2e9a377d9f6060cc1289a79586c1732ba3885997c3cb49bc01d9

Message:

Merge pull request #100 from mmklee/ezgcd_sw

Ezgcd sw

File:

• factory/cf_gcd.cc (modified) (11 diffs)

factory/cf_gcd.cc

@@ -757 +757 @@
   else if (!fc_and_gc_Univariate)
   {
-    if (
-    isOn(SW_USE_CHINREM_GCD)
-    && (isPurePoly_m(fc)) && (isPurePoly_m(gc))
-    )
-    {
-    #if 0
-      if ( p1 == fc.level() )
-        fc = chinrem_gcd( fc, gc );
-      else
-      {
-        fc = replacevar( fc, Variable(p1), Variable(mp) );
-        gc = replacevar( gc, Variable(p1), Variable(mp) );
-        fc = replacevar( chinrem_gcd( fc, gc ), Variable(mp), Variable(p1) );
-      }
-    #else
-      fc = chinrem_gcd( fc, gc);
-    #endif
-    }
-    else if ( isOn( SW_USE_EZGCD ) )
-    {
-      if ( pe == 1 )
+    if ( isOn( SW_USE_EZGCD ) )
+    {
+      fc= ezgcd (fc, gc);
+      /*if ( pe == 1 )
         fc = ezgcd( fc, gc );
       else if ( pe > 0 )// no variable at position 1
@@ -791 +774 @@
         gc = swapvar( gc, Variable(pe), Variable(1) );
         fc = swapvar( ezgcd( fc, gc ), Variable(1), Variable(pe) );
+      }*/
+    }
+    else if (
+    isOn(SW_USE_CHINREM_GCD)
+    && (isPurePoly_m(fc)) && (isPurePoly_m(gc))
+    )
+    {
+    #if 0
+      if ( p1 == fc.level() )
+        fc = chinrem_gcd( fc, gc );
+      else
+      {
+        fc = replacevar( fc, Variable(p1), Variable(mp) );
+        gc = replacevar( gc, Variable(p1), Variable(mp) );
+        fc = replacevar( chinrem_gcd( fc, gc ), Variable(mp), Variable(p1) );
       }
+    #else
+      fc = chinrem_gcd( fc, gc);
+    #endif
     }
     else
@@ -1236 +1237 @@
 
   CanonicalForm Dn, test= 0;
+  cl =  gcd (f.lc(),g.lc());
+  CanonicalForm gcdcfcg= gcd (cf, cg);
+  CanonicalForm b= 1;
+  int minCommonDeg= 0;
+  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);
+
+  CanonicalForm cof, cog, cofp, cogp, newCof, newCog, cofn, cogn;
   //Off (SW_RATIONAL);
   while ( true )
@@ -1246 +1271 @@
     p = cf_getBigPrime( i );
     i--;
-    while ( i >= 0 && mod( cl, p ) == 0 )
+    while ( i >= 0 && mod( cl*(lc(f)/cl)*(lc(g)/cl), p ) == 0 )
     {
       p = cf_getBigPrime( i );
@@ -1253 +1278 @@
     //printf("try p=%d\n",p);
     setCharacteristic( p );
-    Dp = gcd_poly( mapinto( f ), mapinto( g ) );
+    Dp = GCD_small_p (mapinto (f), mapinto (g), cofp, cogp);
     Dp /=Dp.lc();
+    cofp /= lc (cofp);
+    cogp /= lc (cogp);
     setCharacteristic( 0 );
     dp_deg=totaldegree(Dp);
@@ -1265 +1292 @@
     {
       D = mapinto( Dp );
+      cof= mapinto (cofp);
+      cog= mapinto (cogp);
       d_deg=dp_deg;
       q = p;
@@ -1273 +1302 @@
       {
         chineseRemainder( D, q, mapinto( Dp ), p, newD, newq );
+        chineseRemainder( cof, q, mapinto (cofp), p, newCof, newq);
+        chineseRemainder( cog, q, mapinto (cogp), p, newCog, newq);
+        cof= newCof;
+        cog= newCog;
         q = newq;
         D = newD;
@@ -1282 +1315 @@
         q = p;
         D = mapinto( Dp );
+        cof= mapinto (cof);
+        cog= mapinto (cog);
         d_deg=dp_deg;
         test= 0;
@@ -1295 +1330 @@
     {
       Dn= Farey(D,q);
+      cofn= Farey(cof,q);
+      cogn= Farey(cog,q);
       int is_rat= isOn (SW_RATIONAL);
       On (SW_RATIONAL);
       cd = bCommonDen( Dn ); // we need On(SW_RATIONAL)
+      cofn *= bCommonDen (cofn);
+      cogn *= bCommonDen (cogn);
       if (!is_rat)
         Off (SW_RATIONAL);
@@ -1306 +1345 @@
         equal= true;
       //Dn /=vcontent(Dn,Variable(1));
-      if (equal && fdivides( Dn, f ) && fdivides( Dn, g ) )
+      if ((terminationTest (f,g, cofn, cogn, Dn)) ||
+          ((equal || q > b) && fdivides (Dn, f) && fdivides (Dn, g)))
       {
         //printf(" -> success\n");
@@ -1325 +1365 @@
 }
 
+