Changeset 9f84ad in git

Timestamp:

Apr 24, 2012, 4:38:56 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

47046743f1273df49ef99fda72ed22a1531d10bd

Parents:

c244d04150a9fd45331938d2c9fb6f89985acb05

git-author:

Martin Lee <martinlee84@web.de>2012-04-24 16:38:56+02:00

git-committer:

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

Message:

chg: try to use evaluation points that preserve sparseness chg: handling of SW_RATIONAL

File:

• factory/fac_ezgcd.cc (modified) (12 diffs)

factory/fac_ezgcd.cc

@@ -342 +342 @@
 }
 
+static
+bool findeval (const CanonicalForm & F, const CanonicalForm & G,
+               CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db,
+               REvaluation & b, int delta, int degF, int degG, int maxeval,
+               int & count, int& k, int bound, int& l)
+{
+  if( count == 0 && delta != 0)
+  {
+    if( count++ > maxeval )
+      return false;
+  }
+  if (count > 0)
+  {
+    b.nextpoint(k);
+    if (k == 0)
+      k++;
+    l++;
+    if (l > bound)
+    {
+      l= 1;
+      k++;
+      if (k > tmax (F.level(), G.level()) - 1)
+        return false;
+      b.nextpoint (k);
+    }
+    if (count++ > maxeval)
+      return false;
+  }
+  while( true )
+  {
+    Fb = b( F );
+    if( degree( Fb, 1 ) == degF )
+    {
+      Gb = b( G );
+      if( degree( Gb, 1 ) == degG )
+      {
+        Db = gcd( Fb, Gb );
+        if( delta > 0 )
+        {
+          if( degree( Db, 1 ) <= delta )
+            return true;
+        }
+        else
+        {
+          k++;
+          return true;
+        }
+      }
+    }
+    if (k == 0)
+      k++;
+    b.nextpoint(k);
+    l++;
+    if (l > bound)
+    {
+      l= 1;
+      k++;
+      if (k > tmax (F.level(), G.level()) - 1)
+        return false;
+      b.nextpoint (k);
+    }
+    if( count++ > maxeval )
+      return false;
+  }
+}
+
 static CanonicalForm
 ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b,
@@ -347 +413 @@
 {
   bool isRat= isOn (SW_RATIONAL);
-  if (!isRat)
-    On (SW_RATIONAL);
   CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
                 lcD, cand, result;
   CFArray DD( 1, 2 ), lcDD( 1, 2 );
-  int degF, degG, delta, t;
+  int degF, degG, delta, t, count, maxeval;
   REvaluation bt;
   bool gcdfound = false;
   Variable x = Variable(1);
-  modpk bound;
-
-  F= FF;
-  G= GG;
+  count= 0;
+  maxeval= 200;
+  int o, l;
+  o= 0;
+  l= 1;
+
+  if (!isRat)
+    On (SW_RATIONAL);
+  F= FF*bCommonDen (FF);
+  G= GG*bCommonDen (GG);
+  if (!isRat)
+    Off (SW_RATIONAL);
 
   CFMap M,N;
@@ -367 +439 @@
   if (best_level == 0)
   {
-    if (!isRat)
-      Off (SW_RATIONAL);
+    DEBDECLEVEL( cerr, "ezgcd" );
     return G.genOne();
   }
@@ -374 +445 @@
   F= M (F);
   G= M (G);
-
 
   DEBINCLEVEL( cerr, "ezgcd" );
@@ -380 +450 @@
   DEBOUTLN( cerr, "GG = " << GG );
   f = content( F, x ); g = content( G, x ); d = gcd( f, g );
+  d /= icontent (d);
   DEBOUTLN( cerr, "f = " << f );
   DEBOUTLN( cerr, "g = " << g );
@@ -386 +457 @@
   {
     DEBDECLEVEL( cerr, "ezgcd" );
-    if (!isRat)
-      Off (SW_RATIONAL);
     if(F.mvar()==G.mvar())
       d*=gcd(F,G);
     return N (d);
   }
-  else  if ( gcd_test_one( F, G, false ) )
+
+  int maxNumVars= tmax (getNumVars (F), getNumVars (G));
+  int sizeF= size (F);
+  int sizeG= size (G);
+
+
+  if (!isRat)
+    On (SW_RATIONAL);
+  if (sizeF/maxNumVars > 500 && sizeG/maxNumVars > 500)
+  {
+    Off(SW_USE_EZGCD);
+    result=gcd( F, G );
+    On(SW_USE_EZGCD);
+    if (!isRat)
+      Off (SW_RATIONAL);
+    result /= icontent (result);
+    DEBDECLEVEL( cerr, "ezgcd" );
+    return N (d*result);
+  }
+
+  if ( gcd_test_one( F, G, false ) )
   {
     DEBDECLEVEL( cerr, "ezgcd" );
@@ -404 +493 @@
   degF = degree( F, x ); degG = degree( G, x );
   t = tmax( F.level(), G.level() );
-  //bound = findBound( F, G, lcF, lcG, degF, degG );
   if ( ! internal )
     b = REvaluation( 2, t, IntRandom( 25 ) );
@@ -413 +501 @@
     DEBOUTLN( cerr, "F = " << F );
     DEBOUTLN( cerr, "G = " << G );
-    findeval( F, G, Fb, Gb, Db, b, delta, degF, degG );
+    if (!findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count,
+                   o, 25, l))
+    {
+      Off(SW_USE_EZGCD);
+      result=gcd( F, G );
+      On(SW_USE_EZGCD);
+      if (!isRat)
+        Off (SW_RATIONAL);
+      DEBDECLEVEL( cerr, "ezgcd" );
+      result /= icontent (result);
+      return N (d*result);
+    }
     DEBOUTLN( cerr, "found evaluation b = " << b );
     DEBOUTLN( cerr, "F(b) = " << Fb );
@@ -432 +531 @@
     {
       bt = b;
-      findeval( F, G, Fbt, Gbt, Dbt, bt, delta + 1, degF, degG );
+      if (!findeval( F, G, Fbt, Gbt, Dbt, bt, delta, degF, degG, maxeval, count,
+                     o, 25,l ))
+      {
+        Off(SW_USE_EZGCD);
+        result=gcd( F, G );
+        On(SW_USE_EZGCD);
+        if (!isRat)
+          Off (SW_RATIONAL);
+        DEBDECLEVEL( cerr, "ezgcd" );
+        result /= icontent (result);
+        return N (d*result);
+      }
       int dd=degree( Dbt );
       if ( dd /*degree( Dbt )*/ == 0 )
@@ -515 +625 @@
         if (!isRat)
           Off (SW_RATIONAL);
+        DEBDECLEVEL( cerr, "ezgcd" );
+        result /= icontent (result);
         return N (d*result);
       }
@@ -535 +647 @@
         if (!isRat)
           Off (SW_RATIONAL);
+        DEBDECLEVEL( cerr, "ezgcd" );
+        result /= icontent (result);
         return N (d*result);
       }
@@ -549 +663 @@
   /// ---> A9
   DEBDECLEVEL( cerr, "ezgcd" );
+  cand *= bCommonDen (cand);
   if (!isRat)
     Off (SW_RATIONAL);
+  cand /= icontent (cand);
   return N (d*cand);
 }