Changeset 6e2ef0e in git

Timestamp:

Jun 7, 2011, 11:27:14 AM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')

Children:

c1b99270645a77c4bc459b6e4de16489e0a1a56e

Parents:

aacb5ac3506ca9207c0dc541708e70838974185c

Message:

added better coprimality test for small finite fields
switch to modular gcd if psr sequence gets too dense


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

File:

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

factory/cf_gcd.cc

@@ -20 +20 @@
 #include "fieldGCD.h"
 #include "cf_gcd_smallp.h"
+#include "cf_map_ext.h"
+#include "cf_util.h"
 
 #ifdef HAVE_NTL
@@ -43 +45 @@
     int count = 0;
     // assume polys have same level;
-    CFRandom * sample = CFRandomFactory::generate();
+
+    Variable v= Variable (1);
+    bool algExtension= (hasFirstAlgVar (f, v) || hasFirstAlgVar (g, v));
+    CanonicalForm lcf, lcg;
+    if ( swap )
+    {
+        lcf = swapvar( LC( f ), Variable(1), f.mvar() );
+        lcg = swapvar( LC( g ), Variable(1), f.mvar() );
+    }
+    else
+    {
+        lcf = LC( f, Variable(1) );
+        lcg = LC( g, Variable(1) );
+    }
+
+    CanonicalForm F, G;
+    if ( swap )
+    {
+        F=swapvar( f, Variable(1), f.mvar() );
+        G=swapvar( g, Variable(1), g.mvar() );
+    }
+    else
+    {
+        F = f;
+        G = g;
+    }
+
+    #define TEST_ONE_MAX 50
+    int p= getCharacteristic();
+    bool passToGF= false;
+    int k= 1;
+    if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
+    {
+      if (p == 2)
+        setCharacteristic (2, 6, 'Z');
+      else if (p == 3)
+        setCharacteristic (3, 4, 'Z');
+      else if (p == 5 || p == 7)
+        setCharacteristic (p, 3, 'Z');
+      else
+        setCharacteristic (p, 2, 'Z');
+      passToGF= true;
+    }
+    else if (p > 0 && CFFactory::gettype() == GaloisFieldDomain && ipower (p , getGFDegree()) < TEST_ONE_MAX)
+    {
+      k= getGFDegree();
+      if (ipower (p, 2*k) > TEST_ONE_MAX)
+        setCharacteristic (p, 2*k, gf_name);
+      else
+        setCharacteristic (p, 3*k, gf_name);
+      F= GFMapUp (F, k);
+      G= GFMapUp (G, k);
+      lcf= GFMapUp (lcf, k);
+      lcg= GFMapUp (lcg, k);
+    }
+    else if (p > 0 && p < TEST_ONE_MAX && algExtension)
+    {
+      bool extOfExt= false;
+      int d= degree (getMipo (v));
+      CFList source, dest;
+      Variable v2;
+      CanonicalForm primElem, imPrimElem;
+      if (p == 2 && d < 6)
+      {
+        zz_p::init (p);
+        bool primFail= false;
+        Variable vBuf;
+        primElem= primitiveElement (v, vBuf, primFail);
+        ASSERT (!primFail, "failure in integer factorizer");
+        if (d < 3)
+        {
+          zz_pX NTLIrredpoly;
+          BuildIrred (NTLIrredpoly, d*3);
+          CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
+          v2= rootOf (newMipo);
+        }
+        else
+        {
+          zz_pX NTLIrredpoly;
+          BuildIrred (NTLIrredpoly, d*2);
+          CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
+          v2= rootOf (newMipo);
+        }
+        imPrimElem= mapPrimElem (primElem, v, v2);
+        extOfExt= true;
+      }
+      else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
+      {
+        zz_p::init (p);
+        bool primFail= false;
+        Variable vBuf;
+        primElem= primitiveElement (v, vBuf, primFail);
+        ASSERT (!primFail, "failure in integer factorizer");
+        zz_pX NTLIrredpoly;
+        BuildIrred (NTLIrredpoly, d*2);
+        CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
+        v2= rootOf (newMipo);
+        imPrimElem= mapPrimElem (primElem, v, v2);
+        extOfExt= true;
+      }
+      if (extOfExt)
+      {
+        F= mapUp (F, v, v2, primElem, imPrimElem, source, dest);
+        G= mapUp (G, v, v2, primElem, imPrimElem, source, dest);
+        lcf= mapUp (lcf, v, v2, primElem, imPrimElem, source, dest);
+        lcg= mapUp (lcg, v, v2, primElem, imPrimElem, source, dest);
+        v= v2;
+      }
+    }
+
+    CFRandom * sample;
+    if ((!algExtension && p > 0) || p == 0)
+      sample = CFRandomFactory::generate();
+    else
+      sample = AlgExtRandomF (v).clone();
+
     REvaluation e( 2, tmax( f.level(), g.level() ), *sample );
     delete sample;
-    CanonicalForm lcf, lcg;
-    if ( swap )
-    {
-        lcf = swapvar( LC( f ), Variable(1), f.mvar() );
-        lcg = swapvar( LC( g ), Variable(1), f.mvar() );
-    }
-    else
-    {
-        lcf = LC( f, Variable(1) );
-        lcg = LC( g, Variable(1) );
-    }
-    #define TEST_ONE_MAX 50
-    while ( ( e( lcf ).isZero() || e( lcg ).isZero() ) && count < TEST_ONE_MAX )
+
+    if (passToGF)
+    {
+      lcf= lcf.mapinto();
+      lcg= lcg.mapinto();
+    }
+
+    CanonicalForm eval1, eval2;
+    if (passToGF)
+    {
+      eval1= e (lcf);
+      eval2= e (lcg);
+    }
+    else
+    {
+      eval1= e (lcf);
+      eval2= e (lcg);
+    }
+
+    while ( ( eval1.isZero() || eval2.isZero() ) && count < TEST_ONE_MAX )
     {
         e.nextpoint();
         count++;
-    }
-    if ( count == TEST_ONE_MAX )
+        eval1= e (lcf);
+        eval2= e (lcg);
+    }
+    if ( count >= TEST_ONE_MAX )
+    {
+        if (passToGF)
+          setCharacteristic (p);
+        if (k > 1)
+          setCharacteristic (p, k, gf_name);
         return false;
-    CanonicalForm F, G;
-    if ( swap )
-    {
-        F=swapvar( f, Variable(1), f.mvar() );
-        G=swapvar( g, Variable(1), g.mvar() );
-    }
-    else
-    {
-        F = f;
-        G = g;
-    }
-    if ( e(F).taildegree() > 0 && e(G).taildegree() > 0 )
+    }
+
+
+    if (passToGF)
+    {
+      F= F.mapinto();
+      G= G.mapinto();
+      eval1= e (F);
+      eval2= e (G);
+    }
+    else
+    {
+      eval1= e (F);
+      eval2= e (G);
+    }
+
+    if ( eval1.taildegree() > 0 && eval2.taildegree() > 0 )
+    {
+        if (passToGF)
+          setCharacteristic (p);
+        if (k > 1)
+          setCharacteristic (p, k, gf_name);
         return false;
-    return gcd( e( F ), e( G ) ).degree() < 1;
+    }
+
+    CanonicalForm c= gcd (eval1, eval2);
+    bool result= c.degree() < 1;
+
+    if (passToGF)
+      setCharacteristic (p);
+    if (k > 1)
+      setCharacteristic (p, k, gf_name);
+    return result;
 }
 
@@ -413 +563 @@
     else
         bi = -1;
+    int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
+    CanonicalForm oldPi= pi, oldPi1= pi1;
     while ( degree( pi1, v ) > 0 )
     {
+        if (!(pi.isUnivariate() && pi1.isUnivariate()))
+        {
+          if (size (pi)/maxNumVars > 500 || size (pi1)/maxNumVars > 500)
+          {
+            On (SW_USE_FF_MOD_GCD);
+            C *= gcd (oldPi, oldPi1);
+            Off (SW_USE_FF_MOD_GCD);
+            return C;
+          }
+        }
         pi2 = psr( pi, pi1, v );
         pi2 = pi2 / bi;
         pi = pi1; pi1 = pi2;
+        maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
         if ( degree( pi1, v ) > 0 )
         {