Changeset 4704674 in git for factory/cf_gcd.cc

Timestamp:

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

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

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

File:

• factory/cf_gcd.cc (modified) (2 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");