Changeset 2a95b2 in git

Timestamp:

Oct 12, 2012, 5:30:21 PM (10 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

0851b018d4d94918ad78eea2f6350c7012d2a9aa

Parents:

2df3610db1525b99bc5f170fb64ea83dc29d0ac6

git-author:

Martin Lee <martinlee84@web.de>2012-10-12 17:30:21+02:00

git-committer:

Martin Lee <martinlee84@web.de>2012-10-24 12:26:22+02:00

Message:

chg: added more timing infos to gcd functions

Location:

factory

Files:

• algext.cc (modified) (18 diffs)
• cf_gcd.cc (modified) (6 diffs)
• cf_gcd_smallp.cc (modified) (18 diffs)
• fac_ezgcd.cc (modified) (12 diffs)

factory/algext.cc

@@ -15 +15 @@
 
 #include "cf_assert.h"
+#include "timing.h"
 
 #include "templates/ftmpl_functions.h"
@@ -29 +30 @@
 #include "NTLconvert.h"
 #endif
+
+TIMING_DEFINE_PRINT(alg_content_p)
+TIMING_DEFINE_PRINT(alg_content)
+TIMING_DEFINE_PRINT(alg_compress)
+TIMING_DEFINE_PRINT(alg_termination)
+TIMING_DEFINE_PRINT(alg_termination_p)
+TIMING_DEFINE_PRINT(alg_reconstruction)
+TIMING_DEFINE_PRINT(alg_newton_p)
+TIMING_DEFINE_PRINT(alg_recursion_p)
+TIMING_DEFINE_PRINT(alg_gcd_p)
+TIMING_DEFINE_PRINT(alg_euclid_p)
 
 /// compressing two polynomials F and G, M is used for compressing,
@@ -430 +442 @@
     return;
   }
+  TIMING_START (alg_compress)
   CFMap MM,NN;
   int lev= myCompress (F, G, MM, NN, topLevel);
@@ -439 +452 @@
   CanonicalForm f=MM(F);
   CanonicalForm g=MM(G);
+  TIMING_END_AND_PRINT (alg_compress, "time to compress in alg gcd: ")
   // here: f,g are compressed
   // compute largest variable in f or g (least one is Variable(1))
@@ -447 +461 @@
   if(mv == 1) // f,g univariate
   {
+    TIMING_START (alg_euclid_p)
     tryEuclid(f,g,M,result,fail);
+    TIMING_END_AND_PRINT (alg_euclid_p, "time for euclidean alg mod p: ")
     if(fail)
       return;
@@ -453 +469 @@
     return;
   }
+  TIMING_START (alg_content_p)
   // here: mv > 1
   CanonicalForm cf = tryvcontent(f, Variable(2), M, fail); // cf is univariate poly in var(1)
@@ -472 +489 @@
   if(fail)
     return;
+  TIMING_END_AND_PRINT (alg_content_p, "time for content in alg gcd mod p: ")
   if(f.inCoeffDomain())
   {
@@ -495 +513 @@
   N = leadDeg(g, N);
   CanonicalForm gamma;
+  TIMING_START (alg_euclid_p)
   tryEuclid( firstLC(f), firstLC(g), M, gamma, fail );
+  TIMING_END_AND_PRINT (alg_euclid_p, "time for gcd of lcs in alg mod p: ")
   if(fail)
     return;
@@ -517 +537 @@
     if(gamma_image.isZero()) // skip lc-bad points var(1)-alpha
       continue;
+    TIMING_START (alg_recursion_p)
     tryBrownGCD( f(alpha, x), g(alpha, x), M, g_image, fail, false ); // recursive call with one var less
+    TIMING_END_AND_PRINT (alg_recursion_p,
+                         "time for recursive calls in alg gcd mod p: ")
     if(fail)
       return;
@@ -541 +564 @@
       g_image *= gamma_image; // multiply by multiple of image lc(gcd)
       g_image= reduce (g_image, M);
+      TIMING_START (alg_newton_p)
       gnew= tryNewtonInterp (alpha, g_image, m, gm, x, M, fail);
+      TIMING_END_AND_PRINT (alg_newton_p,
+                            "time for Newton interpolation in alg gcd mod p: ")
       // gnew = gm mod m
       // gnew = g_image mod var(1)-alpha
@@ -550 +576 @@
       if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
       {
+        TIMING_START (alg_termination_p)
         cf = tryvcontent(gnew, Variable(2), M, fail);
         if(fail)
@@ -569 +596 @@
           {
             result = NN(reduce (c*g_image, M));
+            TIMING_END_AND_PRINT (alg_termination_p,
+                      "time for successful termination test in alg gcd mod p: ")
             return;
           }
         }
+        TIMING_END_AND_PRINT (alg_termination_p,
+                    "time for unsuccessful termination test in alg gcd mod p: ")
       }
       gm = gnew;
@@ -665 +696 @@
   f = F * bCommonDen(F);
   g = G * bCommonDen(G);
+  TIMING_START (alg_content)
   CanonicalForm contf= myicontent (f);
   CanonicalForm contg= myicontent (g);
@@ -670 +702 @@
   g /= contg;
   CanonicalForm gcdcfcg= myicontent (contf, contg);
+  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
   Variable a, b;
   if(hasFirstAlgVar(f,a))
@@ -727 +760 @@
     mipo /= mipo.lc();
     // here: mipo is monic
+    TIMING_START (alg_gcd_p)
     tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
+    TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
     if( fail ) // mipo splits in char p
       continue;
@@ -756 +791 @@
         D = tmp;
       On( SW_RATIONAL );
+      TIMING_START (alg_reconstruction)
       tmp = Farey( D, q ); // Farey
       tmp *= bCommonDen (tmp);
+      TIMING_END_AND_PRINT (alg_reconstruction,
+                            "time for rational reconstruction in alg gcd: ")
       setReduce(a,true); // reduce expressions modulo mipo
       On( SW_RATIONAL ); // needed by fdivides
@@ -764 +802 @@
       else
         equal= true; // modular image did not add any new information
+      TIMING_START (alg_termination)
       if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
       {
@@ -769 +808 @@
         setReduce(a,true);
         if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
+        TIMING_END_AND_PRINT (alg_termination,
+                            "time for successful termination test in alg gcd: ")
         return tmp*gcdcfcg;
       }
+      TIMING_END_AND_PRINT (alg_termination,
+                          "time for unsuccessful termination test in alg gcd: ")
       Off( SW_RATIONAL );
       setReduce(a,false); // do not reduce expressions modulo mipo

factory/cf_gcd.cc

@@ -3 +3 @@
 #include "config.h"
 
+#include "timing.h"
 #include "cf_assert.h"
 #include "debug.h"
@@ -1156 +1157 @@
 }
 
+TIMING_DEFINE_PRINT(chinrem_termination)
+TIMING_DEFINE_PRINT(chinrem_recursion)
+TIMING_DEFINE_PRINT(chinrem_reconstruction)
+
 CanonicalForm chinrem_gcd ( const CanonicalForm & FF, const CanonicalForm & GG )
 {
@@ -1223 +1228 @@
     fp= mapinto (f);
     gp= mapinto (g);
+    TIMING_START (chinrem_recursion)
 #ifdef HAVE_NTL
     if (size (fp)/maxNumVars > 500 && size (gp)/maxNumVars > 500)
@@ -1237 +1243 @@
     cogp= gp/Dp;
 #endif
+    TIMING_END_AND_PRINT (chinrem_recursion,
+                          "time for gcd mod p in modular gcd: ");
     Dp /=Dp.lc();
     cofp /= lc (cofp);
@@ -1287 +1295 @@
     if ( i >= 0 )
     {
+      TIMING_START (chinrem_reconstruction);
       Dn= Farey(D,q);
       cofn= Farey(cof,q);
       cogn= Farey(cog,q);
+      TIMING_END_AND_PRINT (chinrem_reconstruction,
+                           "time for rational reconstruction in modular gcd: ");
       int is_rat= isOn (SW_RATIONAL);
       On (SW_RATIONAL);
@@ -1303 +1314 @@
         equal= true;
       //Dn /=vcontent(Dn,Variable(1));
+      TIMING_START (chinrem_termination);
       if ((terminationTest (f,g, cofn, cogn, Dn)) ||
           ((equal || q > b) && fdivides (Dn, f) && fdivides (Dn, g)))
       {
+        TIMING_END_AND_PRINT (chinrem_termination,
+                            "time for successful termination in modular gcd: ");
         //printf(" -> success\n");
         return Dn*gcdcfcg;
       }
+      TIMING_END_AND_PRINT (chinrem_termination,
+                          "time for unsuccessful termination in modular gcd: ");
       equal= false;
       //else: try more primes

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);
+      TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
 
       if (gcdfound == -1)
@@ -4833 +4867 @@
       if (gcdfound == 1)
       {
+        TIMING_START (termination_test);
         contcand= content (DD[2], Variable (1));
         cand = DD[2] / contcand;
@@ -4839 +4874 @@
         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)

factory/fac_ezgcd.cc

@@ -15 +15 @@
 #include "config.h"
 
+#include "timing.h"
 #include "cf_assert.h"
 #include "debug.h"
@@ -30 +31 @@
 
 #ifdef HAVE_NTL
+
+TIMING_DEFINE_PRINT(ez_eval)
+TIMING_DEFINE_PRINT(ez_compress)
+TIMING_DEFINE_PRINT(ez_hensel_lift)
+TIMING_DEFINE_PRINT(ez_content)
+TIMING_DEFINE_PRINT(ez_termination)
+
 static
 int compress4EZGCD (const CanonicalForm& F, const CanonicalForm& G, CFMap & M,
@@ -432 +440 @@
     Off (SW_RATIONAL);
 
+  TIMING_START (ez_compress)
   CFMap M,N;
   int smallestDegLev;
@@ -444 +453 @@
   F= M (F);
   G= M (G);
+  TIMING_END_AND_PRINT (ez_compress, "time for compression in EZ: ")
 
   DEBINCLEVEL( cerr, "ezgcd" );
   DEBOUTLN( cerr, "FF = " << FF );
   DEBOUTLN( cerr, "GG = " << GG );
+  TIMING_START (ez_content)
   f = content( F, x ); g = content( G, x ); d = gcd( f, g );
   d /= icontent (d);
@@ -453 +464 @@
   DEBOUTLN( cerr, "g = " << g );
   F /= f; G /= g;
+  TIMING_END_AND_PRINT (ez_content, "time to extract content in EZ: ")
   if ( F.isUnivariate() && G.isUnivariate() )
   {
@@ -500 +512 @@
     DEBOUTLN( cerr, "F = " << F );
     DEBOUTLN( cerr, "G = " << G );
+    TIMING_START (ez_eval)
     if (!findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count,
                    o, 25, l))
@@ -512 +525 @@
       return N (d*result);
     }
+    TIMING_END_AND_PRINT (ez_eval, "time to find eval point in EZ1: ")
     DEBOUTLN( cerr, "found evaluation b = " << b );
     DEBOUTLN( cerr, "F(b) = " << Fb );
@@ -530 +544 @@
     {
       bt = b;
+      TIMING_START (ez_eval)
       if (!findeval( F, G, Fbt, Gbt, Dbt, bt, delta, degF, degG, maxeval, count,
                      o, 25,l ))
@@ -542 +557 @@
         return N (d*result);
       }
+      TIMING_END_AND_PRINT (ez_eval, "time to find eval point in EZ2: ")
       int dd=degree( Dbt );
       if ( dd /*degree( Dbt )*/ == 0 )
@@ -636 +652 @@
       DEBOUTLN( cerr, "(hensel) DD   = " << DD );
       DEBOUTLN( cerr, "(hensel) lcDD = " << lcDD );
+      TIMING_START (ez_hensel_lift)
       gcdfound= Hensel (B*lcD, DD, b, lcDD);
+      TIMING_END_AND_PRINT (ez_hensel_lift, "time to hensel lift in EZ: ")
       DEBOUTLN( cerr, "(hensel finished) DD   = " << DD );
 
@@ -653 +671 @@
       if (gcdfound)
       {
+        TIMING_START (ez_termination)
         contcand= content (DD[2], Variable (1));
         cand = DD[2] / contcand;
@@ -659 +678 @@
         else
           gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
+        TIMING_END_AND_PRINT (ez_termination,
+                              "time for termination test in EZ: ")
       }
       /// ---> A8 (gcdfound)