Changeset 2a95b2 in git for factory/algext.cc

Timestamp:

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

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

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

File:

• factory/algext.cc (modified) (18 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