Changeset 1130ffc in git for factory/cf_gcd_smallp.cc

Timestamp:

Oct 25, 2012, 2:25:59 PM (12 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

139f6f800b915490dfaa914ef7676d29a3236b92186df6b3fe891f605e0e3e7324333e7713165436

Parents:

becbea965e6c5de8e8ab195c7f480cabc295ac0cd91423947d67c2ab2eaf1aae4a61f9f2988e9510

Message:

Merge pull request #198 from mmklee/factory_clean_sw

Factory clean sw

File:

• factory/cf_gcd_smallp.cc (modified) (17 diffs)

factory/cf_gcd_smallp.cc

@@ -45 +45 @@
 TIMING_DEFINE_PRINT(gcd_recursion)
 TIMING_DEFINE_PRINT(newton_interpolation)
+TIMING_DEFINE_PRINT(termination_test)
+TIMING_DEFINE_PRINT(ez_p_compress)
+TIMING_DEFINE_PRINT(ez_p_hensel_lift)
+TIMING_DEFINE_PRINT(ez_p_eval)
+TIMING_DEFINE_PRINT(ez_p_content)
 
 bool
@@ -797 +802 @@
     if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
     {
+      TIMING_START (termination_test);
       if (gcdlcAlcB.isOne())
         cH= 1;
@@ -831 +837 @@
           coF= N ((cA/gcdcAcB)*ppCoF);
           coG= N ((cB/gcdcAcB)*ppCoG);
+          TIMING_END_AND_PRINT (termination_test,
+                                "time for successful termination test Fq: ");
           return N(gcdcAcB*ppH);
         }
@@ -846 +854 @@
         }
         coF= N ((cA/gcdcAcB)*ppCoF);
-        coG= N ((cB/gcdcAcB)*ppCoG);;
+        coG= N ((cB/gcdcAcB)*ppCoG);
+        TIMING_END_AND_PRINT (termination_test,
+                              "time for successful termination test Fq: ");
         return N(gcdcAcB*ppH);
       }
+      TIMING_END_AND_PRINT (termination_test,
+                            "time for unsuccessful termination test Fq: ");
     }
 
@@ -1237 +1249 @@
     if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
     {
+      TIMING_START (termination_test);
       if (gcdlcAlcB.isOne())
         cH= 1;
@@ -1270 +1283 @@
           coG= N ((cB/gcdcAcB)*ppCoG);
           setCharacteristic (p, k, gf_name_buf);
+          TIMING_END_AND_PRINT (termination_test,
+                                "time for successful termination GF: ");
           return N(gcdcAcB*ppH);
         }
@@ -1288 +1303 @@
           coF= N ((cA/gcdcAcB)*ppCoF);
           coG= N ((cB/gcdcAcB)*ppCoG);
+          TIMING_END_AND_PRINT (termination_test,
+                                "time for successful termination GF: ");
           return N(gcdcAcB*ppH);
         }
       }
+      TIMING_END_AND_PRINT (termination_test,
+                            "time for unsuccessful termination GF: ");
     }
 
@@ -1744 +1763 @@
     if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
     {
+      TIMING_START (termination_test);
       if (gcdlcAlcB.isOne())
         cH= 1;
@@ -1769 +1789 @@
         coF= N ((cA/gcdcAcB)*ppCoF);
         coG= N ((cB/gcdcAcB)*ppCoG);
+        TIMING_END_AND_PRINT (termination_test,
+                              "time for successful termination Fp: ");
         return N(gcdcAcB*ppH);
       }
+      TIMING_END_AND_PRINT (termination_test,
+                            "time for unsuccessful termination Fp: ");
     }
 
@@ -4450 +4474 @@
   CFMap M,N;
   int smallestDegLev;
+  TIMING_START (ez_p_compress)
   int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
 
@@ -4456 +4481 @@
   F= M (F);
   G= M (G);
-
+  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
+
+  TIMING_START (ez_p_content)
   f = content( F, x ); g = content( G, x );
   d = gcd( f, g );
   F /= f; G /= g;
+  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
 
   if( F.isUnivariate() && G.isUnivariate() )
@@ -4598 +4626 @@
   while( !gcdfound )
   {
+    TIMING_START (ez_p_eval);
     if( !findeval_P( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
          maxeval/maxNumVars, t ))
@@ -4620 +4649 @@
       return N (d*result);
     }
+    TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
     delta = degree( Db );
     if( delta == 0 )
@@ -4632 +4662 @@
     {
       bt = b;
+      TIMING_START (ez_p_eval);
       if( !findeval_P(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
            maxeval/maxNumVars, t ))
@@ -4654 +4685 @@
         return N (d*result);
       }
+      TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
       int dd = degree( Dbt );
       if( dd == 0 )
@@ -4807 +4839 @@
       }
 
+      TIMING_START (ez_p_hensel_lift);
       gcdfound= Hensel_P (B*lcD, DD, b, lcDD);
-
-      if (gcdfound == -1)
-      {
-        Off (SW_USE_EZGCD_P);
-        result= gcd (F,G);
-        On (SW_USE_EZGCD_P);
-        if (passToGF)
-        {
-          CanonicalForm mipo= gf_mipo;
-          setCharacteristic (p);
-          Variable alpha= rootOf (mipo.mapinto());
-          result= GF2FalphaRep (result, alpha);
+      TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
+
+      if (gcdfound == -1) //things became dense
+      {
+        if (algExtension)
+        {
+          result= GCD_Fp_extension (F, G, a);
+          if (extOfExt)
+            result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
+          return N (d*result);
         }
-        if (k > 1)
-        {
-          result= GFMapDown (result, k);
-          setCharacteristic (p, k, gf_name);
+        if (CFFactory::gettype() == GaloisFieldDomain)
+        {
+          result= GCD_GF (F, G);
+          if (passToGF)
+          {
+            CanonicalForm mipo= gf_mipo;
+            setCharacteristic (p);
+            Variable alpha= rootOf (mipo.mapinto());
+            result= GF2FalphaRep (result, alpha);
+          }
+          if (k > 1)
+          {
+            result= GFMapDown (result, k);
+            setCharacteristic (p, k, gf_name);
+          }
+          return N (d*result);
         }
-        if (extOfExt)
-          result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
-        return N (d*result);
+        else
+          return N (d*GCD_small_p (F,G));
       }
 
       if (gcdfound == 1)
       {
+        TIMING_START (termination_test);
         contcand= content (DD[2], Variable (1));
         cand = DD[2] / contcand;
@@ -4839 +4882 @@
         else
           gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
+        TIMING_END_AND_PRINT (termination_test,
+                              "time for termination test EZ_P: ");
 
         if (passToGF && gcdfound)