Changeset cb7827 in git

Timestamp:

Apr 26, 2012, 3:50:40 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38077648e7239f98078663eb941c3c979511150a')

Children:

59778389f5075553bef793320610ce298d74b18d

Parents:

47046743f1273df49ef99fda72ed22a1531d10bd

git-author:

Martin Lee <martinlee84@web.de>2012-04-26 15:50:40+02:00

git-committer:

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

Message:

chg: compute cofactors in chinrem_gcd and use them to test divisibility

File:

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

factory/cf_gcd.cc

@@ -1260 +1260 @@
       minCommonDeg= tmin (minCommonDeg, tmin (degree (g, i), degree (f, i)));
   }
-  b= 2*tmin (maxNorm (f), maxNorm (g))*abs (cl)*power (CanonicalForm (2), minCommonDeg);
+  b= 2*tmin (maxNorm (f), maxNorm (g))*abs (cl)*
+     power (CanonicalForm (2), minCommonDeg);
   bool equal= false;
   i = cf_getNumBigPrimes() - 1;
 
+  CanonicalForm cof, cog, cofp, cogp, newCof, newCog, cofn, cogn;
   //Off (SW_RATIONAL);
   while ( true )
@@ -1277 +1279 @@
     setCharacteristic( p );
     Dp = gcd_poly( mapinto( f ), mapinto( g ) );
+    //Dp = GCD_small_p (mapinto (f), mapinto (g), cofp, cogp);
     Dp /=Dp.lc();
+    cofp= mapinto (f)/Dp;
+    cogp= mapinto (g)/Dp;
+    cofp /= lc (cofp);
+    cogp /= lc (cogp);
     setCharacteristic( 0 );
     dp_deg=totaldegree(Dp);
@@ -1288 +1295 @@
     {
       D = mapinto( Dp );
+      cof= mapinto (cofp);
+      cog= mapinto (cogp);
       d_deg=dp_deg;
       q = p;
@@ -1296 +1305 @@
       {
         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;
@@ -1305 +1318 @@
         q = p;
         D = mapinto( Dp );
+        cof= mapinto (cof);
+        cog= mapinto (cog);
         d_deg=dp_deg;
         test= 0;
@@ -1318 +1333 @@
     {
       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);
@@ -1329 +1348 @@
         equal= true;
       //Dn /=vcontent(Dn,Variable(1));
-      if ((equal || q > b) && fdivides( Dn, f ) && fdivides( Dn, g ) )
+      if ((equal || q > b) || ((cofn*Dn==f) && (cogn*Dn==g)))
       {
         //printf(" -> success\n");
@@ -1348 +1367 @@
 }
 
+