Changeset e22ea7 in git

Timestamp:

Jan 5, 2005, 12:27:17 PM (19 years ago)

Author:

Hans Schönemann <hannes@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

7dd754926fbde53f14c682a4eee9f02960f174e1

Parents:

672566a7f6af2a2349ebd32302a58c4c91a0259e

Message:

*hannes/pfister: ezgcd fixed


git-svn-id: file:///usr/local/Singular/svn/trunk@7645 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

factory

Files:

• cf_gcd.cc (modified) (4 diffs)
• fac_ezgcd.cc (modified) (9 diffs)

factory/cf_gcd.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_gcd.cc,v 1.26 2004-11-25 15:43:36 Singular Exp $ */
+/* $Id: cf_gcd.cc,v 1.27 2005-01-05 11:27:17 Singular Exp $ */
 
 #include <config.h>
@@ -376 +376 @@
         CFMap M, N;
         compress( f, g, M, N );
+#if 0
         CanonicalForm r=N( ezgcd( M(f), M(g) ) );
         if ((f%r!=0) || (g % r !=0))
@@ -383 +384 @@
            return gcd_poly1( f, g, modularflag);
         }
-        else return r;
+        else
+           return r;
+#else
+         return N( ezgcd( M(f), M(g) ) );
+#endif    
     }
     else if ( isOn( SW_USE_SPARSEMOD )
     && ! ( f.isUnivariate() && g.isUnivariate() ) )
     {
+#if 0
         CanonicalForm r=sparsemod( f, g );
         if ((f%r!=0) || (g % r !=0))
@@ -393 +399 @@
            if (si_factor_reminder)
            printf("sparsemod failed, trying gcd_poly1\n");
-           return gcd_poly1( f, g, modularflag);
+           return r;
+           //return gcd_poly1( f, g, modularflag);
         }
-        else return r;
+        else
+          return r;
+#else
+        return sparsemod( f, g );
+#endif
     }
     else

factory/fac_ezgcd.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: fac_ezgcd.cc,v 1.14 2001-01-24 18:09:41 Singular Exp $ */
+/* $Id: fac_ezgcd.cc,v 1.15 2005-01-05 11:27:17 Singular Exp $ */
 
 #include <config.h>
@@ -40 +40 @@
     CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG, lcD;
     CFArray DD( 1, 2 ), lcDD( 1, 2 );
-    int degF, degG, delta, deltaold, t;
+    int degF, degG, delta, t;
     REvaluation bt;
     bool gcdfound = false;
@@ -54 +54 @@
     F = FF / f; G = GG / g;
     if ( F.isUnivariate() && G.isUnivariate() )
+    {
+        DEBDECLEVEL( cerr, "ezgcd" );
         return d * gcd( F, G );
+    }
     else  if ( gcd_test_one( F, G, false ) )
+    {
+        DEBDECLEVEL( cerr, "ezgcd" );
         return d;
+    }
     lcF = LC( F, x ); lcG = LC( G, x );
     lcD = gcd( lcF, lcG );
@@ -64 +70 @@
     bound = findBound( F, G, lcF, lcG, degF, degG );
     if ( ! internal )
-        b = REvaluation( 2, t, IntRandom( 100 ) );
+        b = REvaluation( 2, t, IntRandom( 50 ) );
     while ( ! gcdfound ) {
         /// ---> A2
@@ -78 +84 @@
         /// ---> A3
         if ( delta == 0 )
-            return d;
+        {
+          DEBDECLEVEL( cerr, "ezgcd" );
+          return d;
+        }
         /// ---> A4
-        deltaold = delta + 1;
-        while ( deltaold != delta ) {
+        //deltaold = delta;
+        while ( 1 ) {
             bt = b;
             findeval( F, G, Fbt, Gbt, Dbt, bt, delta + 1, degF, degG );
-            if ( degree( Dbt ) == 0 )
+            int dd=degree( Dbt );
+            if ( dd /*degree( Dbt )*/ == 0 )
+            {
+                DEBDECLEVEL( cerr, "ezgcd" );
                 return d;
-            if ( degree( Dbt ) == delta )
-                deltaold = delta;
-            else  if ( degree( Dbt ) < delta ) {
-                deltaold = delta;
-                delta = degree( Dbt );
+            }
+            if ( dd /*degree( Dbt )*/ == delta )
+                break;
+            else  if ( dd /*degree( Dbt )*/ < delta ) {
+                delta = dd /*degree( Dbt )*/;
                 b = bt;
                 Db = Dbt; Fb = Fbt; Gb = Gbt;
@@ -98 +110 @@
         /// ---> A5
         if ( degF <= degG && delta == degF && divides( F, G ) )
+        {
+            DEBDECLEVEL( cerr, "ezgcd" );
             return d*F;
+        }
         if ( degG < degF && delta == degG && divides( G, F ) )
+        {
+            DEBDECLEVEL( cerr, "ezgcd" );
             return d*G;
+        }
         if ( delta != degF && delta != degG ) {
             /// ---> A6
@@ -144 +162 @@
             gcdfound = Hensel( B, DD, lcDD, b, bound, x );
             DEBOUTLN( cerr, "(hensel finished) DD   = " << DD );
+            
+            if (gcdfound)
+            {
+              CanonicalForm cand=DD[2] / content(DD[2],Variable(1));
+              if (B==F)
+              {
+                DEBOUTLN( cerr, "(test) G: "<<G<<" % gcd:"<<cand<<" -> " << G%cand );
+                gcdfound= divides(cand,G);
+                //gcdfound= ((G-((G/cand)*cand))==0);
+                //gcdfound= ((G % cand)==0);
+              }
+              else
+              { 
+                DEBOUTLN( cerr, "(test) F: "<<F<<" % gcd:"<<cand<<" -> " << F%cand);
+                gcdfound= divides(cand,F);
+                //gcdfound= ((F-((F/cand)*cand))==0);
+                //gcdfound= ((F % cand)==0);
+              }
+            }
             /// ---> A8 (gcdfound)
         }
@@ -234 +271 @@
 findeval( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db, REvaluation & b, int delta, int degF, int degG )
 {
+//    int t=tmax(F.level(),G.level());
+    int i;
     bool ok;
     if ( delta != 0 )
         b.nextpoint();
+//    i=2;
+//    while(i<=t)
+//    {
+//      if (b[i]==0) { b.nextpoint(); i=2; }
+//      else i++;
+//    }
+    DEBOUTLN( cerr, "ezgcd: (findeval) F = " << F  <<", G="<< G);
+    DEBOUTLN( cerr, "ezgcd: (findeval) degF = " << degF << ", degG="<<degG );
     do {
         DEBOUTLN( cerr, "ezgcd: (findeval) b = " << b );
@@ -245 +292 @@
             ok = degree( Gb ) == degG;
         }
+       
         if ( ok ) {
-            Db = gcd( Fb, Gb );
-            if ( delta > 0 )
+//          if ((Fb.isZero())||(Gb.isZero()))
+//            ok=false;
+//          else
+            {    
+              Db = gcd( Fb, Gb );
+              if ( delta > 0 )
                 ok = degree( Db ) < delta;
+            }
         }
         if ( ! ok )