Changeset 1130ffc in git

Timestamp:

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

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')

Children:

139f6f800b915490dfaa914ef7676d29a3236b92186df6b3fe891f605e0e3e7324333e7713165436

Parents:

becbea965e6c5de8e8ab195c7f480cabc295ac0cd91423947d67c2ab2eaf1aae4a61f9f2988e9510

Message:

Merge pull request #198 from mmklee/factory_clean_sw

Factory clean sw

Location:

factory

Files:

• algext.cc (modified) (18 diffs)
• cfNewtonPolygon.cc (modified) (1 diff)
• cf_gcd.cc (modified) (8 diffs)
• cf_gcd_smallp.cc (modified) (17 diffs)
• facAlgExt.cc (modified) (9 diffs)
• facBivar.cc (modified) (6 diffs)
• facBivar.h (modified) (3 diffs)
• facFactorize.cc (modified) (21 diffs)
• facFactorize.h (modified) (2 diffs)
• facFqBivar.cc (modified) (13 diffs)
• facFqBivar.h (modified) (8 diffs)
• facFqFactorize.cc (modified) (23 diffs)
• facFqFactorize.h (modified) (7 diffs)
• fac_ezgcd.cc (modified) (12 diffs)
• libfac/factor/timing.h (modified) (2 diffs)
• timing.h (modified) (2 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/cfNewtonPolygon.cc

@@ -879 +879 @@
         if (isRat)
           On (SW_RATIONAL);
-        if (tmp == 1)
-        {
-          for (int i= 0; i < sizeOfNewtonPolygon; i++)
-            delete [] newtonPolyg [i];
-          delete [] newtonPolyg;
-        }
+        for (int i= 0; i < sizeOfNewtonPolygon; i++)
+          delete [] newtonPolyg [i];
+        delete [] newtonPolyg;
         return (tmp==1);
       }

factory/cf_gcd.cc

@@ -3 +3 @@
 #include "config.h"
 
+#include "timing.h"
 #include "cf_assert.h"
 #include "debug.h"
@@ -572 +573 @@
     Variable v = f.mvar();
     Hi = power( LC( pi1, v ), delta );
+    int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
+
+    if (!(pi.isUnivariate() && pi1.isUnivariate()))
+    {
+      if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
+      {
+        On (SW_USE_FF_MOD_GCD);
+        C *= gcd (pi, pi1);
+        Off (SW_USE_FF_MOD_GCD);
+        return C;
+      }
+    }
+
     if ( (delta+1) % 2 )
         bi = 1;
     else
         bi = -1;
-    int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
-    CanonicalForm oldPi= pi, oldPi1= pi1;
+    CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
     while ( degree( pi1, v ) > 0 )
     {
@@ -604 +617 @@
         {
             delta = degree( pi, v ) - degree( pi1, v );
+            powHi= power (Hi, delta-1);
             if ( (delta+1) % 2 )
-                bi = LC( pi, v ) * power( Hi, delta );
+                bi = LC( pi, v ) * powHi*Hi;
             else
-                bi = -LC( pi, v ) * power( Hi, delta );
-            Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
+                bi = -LC( pi, v ) * powHi*Hi;
+            Hi = power( LC( pi1, v ), delta ) / powHi;
+            if (!(pi.isUnivariate() && pi1.isUnivariate()))
+            {
+              if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
+              {
+                On (SW_USE_FF_MOD_GCD);
+                C *= gcd (oldPi, oldPi1);
+                Off (SW_USE_FF_MOD_GCD);
+                return C;
+              }
+            }
         }
     }
@@ -1156 +1180 @@
 }
 
+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 +1251 @@
     fp= mapinto (f);
     gp= mapinto (g);
+    TIMING_START (chinrem_recursion)
 #ifdef HAVE_NTL
     if (size (fp)/maxNumVars > 500 && size (gp)/maxNumVars > 500)
@@ -1237 +1266 @@
     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 +1318 @@
     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 +1337 @@
         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);
-
-      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)

factory/facAlgExt.cc

@@ -29 +29 @@
 #include "fac_sqrfree.h"
 
+TIMING_DEFINE_PRINT(fac_alg_resultant)
+TIMING_DEFINE_PRINT(fac_alg_norm)
+TIMING_DEFINE_PRINT(fac_alg_factor_norm)
+TIMING_DEFINE_PRINT(fac_alg_gcd)
+TIMING_DEFINE_PRINT(fac_alg_sqrf)
+TIMING_DEFINE_PRINT(fac_alg_factor_sqrf)
+
 // squarefree part of F
 CanonicalForm
@@ -53 +60 @@
   int degmipo= degree (mipo);
   CanonicalForm norm;
+  TIMING_START (fac_alg_resultant);
   if (degg >= 8 || degmipo >= 8)
     norm= resultantZ (g, mipo, x);
   else
     norm= resultant (g, mipo, x);
+  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
 
   i= 0;
@@ -72 +81 @@
         g= F (y - i*alpha, y);
         g *= bCommonDen (g);
+        TIMING_START (fac_alg_resultant);
         if (degg >= 8 || degmipo >= 8)
           norm= resultantZ (g (x, alpha), mipo, x);
         else
           norm= resultant (g (x, alpha), mipo, x);
+        TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant1: ");
       }
       else
@@ -81 +92 @@
         g= F (y + i*alpha, y);
         g *= bCommonDen (g);
+        TIMING_START (fac_alg_resultant);
         if (degg >= 8 || degmipo >= 8)
           norm= resultantZ (g (x, alpha), mipo, x);
         else
           norm= resultant (g (x, alpha), mipo, x);
+        TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant2: ");
       }
       if (degree (gcd (deriv (norm, y), norm)) <= 0)
@@ -108 +121 @@
   CanonicalForm f= F*bCommonDen (F);
   int shift;
+  TIMING_START (fac_alg_norm);
   CanonicalForm norm= sqrfNorm (f, alpha, shift);
+  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
   ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
+  TIMING_START (fac_alg_factor_norm);
   CFFList normFactors= factorize (norm);
+  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
   CFList factors;
   if (normFactors.length() <= 2)
@@ -125 +142 @@
   {
     ASSERT (i.getItem().exp() == 1, "norm not squarefree");
+    TIMING_START (fac_alg_gcd);
     if (shift == 0)
       factor= gcd (buf, i.getItem().factor());
@@ -130 +148 @@
       factor= gcd (buf, i.getItem().factor() (f.mvar() + shift*alpha, f.mvar()));
     buf /= factor;
+    TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
     factors.append (factor);
   }
@@ -149 +168 @@
   bool save_rat=!isOn (SW_RATIONAL);
   On (SW_RATIONAL);
+  TIMING_START (fac_alg_sqrf);
   CFFList sqrf= sqrFreeZ (F);
+  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
   CFList factorsSqrf;
   CFFList factors;
@@ -158 +179 @@
   {
     if (i.getItem().factor().inCoeffDomain()) continue;
+    TIMING_START (fac_alg_factor_sqrf);
     factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
+    TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
+                          "time to factor sqrf factors in Q(a)[x]: ");
     for (j= factorsSqrf; j.hasItem(); j++)
     {

factory/facBivar.cc

@@ -13 +13 @@
 #include "config.h"
 
-#include "assert.h"
+#include "cf_assert.h"
 #include "debug.h"
 #include "timing.h"
@@ -28 +28 @@
 TIMING_DEFINE_PRINT(fac_bi_hensel_lift)
 TIMING_DEFINE_PRINT(fac_bi_factor_recombination)
+TIMING_DEFINE_PRINT(fac_bi_evaluation)
+TIMING_DEFINE_PRINT(fac_bi_shift_to_zero)
 
 // bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
@@ -186 +188 @@
 }
 
-CFList
-earlyFactorDetection0 (CanonicalForm& F, CFList& factors,int& adaptedLiftBound,
-                      DegreePattern& degs, bool& success, int deg)
-{
-  DegreePattern bufDegs1= degs;
-  DegreePattern bufDegs2;
-  CFList result;
-  CFList T= factors;
-  CanonicalForm buf= F;
-  CanonicalForm LCBuf= LC (buf, Variable (1));
-  CanonicalForm g, quot;
-  CanonicalForm M= power (F.mvar(), deg);
-  adaptedLiftBound= 0;
-  int d= degree (F) + degree (LCBuf, F.mvar());
-  for (CFListIterator i= factors; i.hasItem(); i++)
-  {
-    if (!bufDegs1.find (degree (i.getItem(), 1)))
-      continue;
-    else
-    {
-      g= i.getItem() (0, 1);
-      g *= LCBuf;
-      g= mod (g, M);
-      if (fdivides (LC (g), LCBuf))
-      {
-        g= mulMod2 (i.getItem(), LCBuf, M);
-        g /= content (g, Variable (1));
-        if (fdivides (g, buf, quot))
-        {
-          result.append (g);
-          buf= quot;
-          d -= degree (g) + degree (LC (g, Variable (1)), F.mvar());
-          LCBuf= LC (buf, Variable (1));
-          T= Difference (T, CFList (i.getItem()));
-
-          // compute new possible degree pattern
-          bufDegs2= DegreePattern (T);
-          bufDegs1.intersect (bufDegs2);
-          bufDegs1.refine ();
-          if (bufDegs1.getLength() <= 1)
-          {
-            result.append (buf);
-            break;
-          }
-        }
-      }
-    }
-  }
-  adaptedLiftBound= d + 1;
-  if (d < deg)
-  {
-    factors= T;
-    degs= bufDegs1;
-    F= buf;
-    success= true;
-  }
-  if (bufDegs1.getLength() <= 1)
-    degs= bufDegs1;
-  return result;
-}
-
-
-CFList
-henselLiftAndEarly0 (CanonicalForm& A, bool& earlySuccess, CFList&
-                    earlyFactors, DegreePattern& degs, int& liftBound,
-                    const CFList& uniFactors, const CanonicalForm& eval)
-{
-  int sizeOfLiftPre;
-  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
-
-  Variable x= Variable (1);
-  Variable y= Variable (2);
-  CFArray Pi;
-  CFList diophant;
-  CFList bufUniFactors= uniFactors;
-  bufUniFactors.insert (LC (A, x));
-  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
-  earlySuccess= false;
-  int newLiftBound= 0;
-  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
-  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
-    henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);
-  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
-  {
-    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
-    earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                                        degs, earlySuccess,
-                                        smallFactorDeg);
-    if (degs.getLength() > 1 && !earlySuccess &&
-        smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
-    {
-      if (newLiftBound > liftPre[sizeOfLiftPre-1]+1)
-      {
-        bufUniFactors.insert (LC (A, x));
-        henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
-                            liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M);
-        earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                      degs, earlySuccess, liftPre[sizeOfLiftPre-1] + 1);
-      }
-    }
-    else if (earlySuccess)
-      liftBound= newLiftBound;
-    int i= sizeOfLiftPre - 1;
-    while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
-    {
-      if (newLiftBound > liftPre[i] + 1)
-      {
-        bufUniFactors.insert (LC (A, x));
-        henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
-                            liftPre[i-1] + 1, Pi, diophant, M);
-        earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                      degs, earlySuccess, liftPre[i-1] + 1);
-      }
-      else
-      {
-        liftBound= newLiftBound;
-        break;
-      }
-      i--;
-    }
-    if (earlySuccess)
-      liftBound= newLiftBound;
-    //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
-  }
-  else
-  {
-    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
-    earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                                        degs, earlySuccess,
-                                        smallFactorDeg);
-    int i= 1;
-    while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
-      i++;
-    if (degs.getLength() > 1 && !earlySuccess)
-    {
-      bufUniFactors.insert (LC (A, x));
-      henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
-                          (degree (A, y)/4)*i + 4, Pi, diophant, M);
-      earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                    degs, earlySuccess, (degree (A, y)/4)*i + 4);
-    }
-    while (degs.getLength() > 1 && !earlySuccess && i < 4)
-    {
-      if (newLiftBound > (degree (A, y)/4)*i + 4)
-      {
-        bufUniFactors.insert (LC (A, x));
-        henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
-                            (degree (A, y)/4)*(i+1) + 4, Pi, diophant, M);
-        earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                      degs, earlySuccess, (degree (A, y)/4)*(i+1) + 4);
-      }
-      else
-      {
-        liftBound= newLiftBound;
-        break;
-      }
-      i++;
-    }
-    if (earlySuccess)
-      liftBound= newLiftBound;
-  }
-
-  return bufUniFactors;
-}
-
 CFList biFactorize (const CanonicalForm& F, const Variable& v)
 {
@@ -499 +336 @@
   {
     bufAeval= A;
+    TIMING_START (fac_bi_evaluation);
     bufAeval= evalPoint (A, bufEvaluation);
+    TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
 
     bufAeval2= buf;
+    TIMING_START (fac_bi_evaluation);
     bufAeval2= evalPoint (buf, bufEvaluation2);
+    TIMING_END_AND_PRINT (fac_bi_evaluation,
+                          "time for eval point over Q in y: ");
 
     // univariate factorization
-    TIMING_START (uni_factorize);
-
+    TIMING_START (fac_uni_factorizer);
     if (extension)
       bufUniFactors= conv (factorize (bufAeval, v));
     else
       bufUniFactors= conv (factorize (bufAeval, true));
-    TIMING_END_AND_PRINT (uni_factorize,
-                          "time for univariate factorization: ");
+    TIMING_END_AND_PRINT (fac_uni_factorizer,
+                          "time for univariate factorization over Q: ");
     DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
               (prod (bufUniFactors) == bufAeval));
 
-    TIMING_START (uni_factorize);
+    TIMING_START (fac_uni_factorizer);
     if (extension)
       bufUniFactors2= conv (factorize (bufAeval2, v));
     else
       bufUniFactors2= conv (factorize (bufAeval2, true));
-    TIMING_END_AND_PRINT (uni_factorize,
-                          "time for univariate factorization in y: ");
+    TIMING_END_AND_PRINT (fac_uni_factorizer,
+                          "time for univariate factorization in y over Q: ");
     DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
               (prod (bufUniFactors2) == bufAeval2));
@@ -709 +550 @@
               (A, earlySuccess, earlyFactors, degs, liftBound,
                uniFactors, dummy, evaluation, b);
-  TIMING_END_AND_PRINT (fac_bi_hensel_lift, "time for hensel lifting: ");
+  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
+                        "time for bivariate hensel lifting over Q: ");
   DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
@@ -728 +570 @@
   Off (SW_RATIONAL);
 
+  TIMING_START (fac_bi_factor_recombination);
   factors= factorRecombination (uniFactors, A, MODl, degs, 1,
                                 uniFactors.length()/2, b);
+  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
+                        "time for bivariate factor recombination over Q: ");
 
   On (SW_RATIONAL);

factory/facBivar.h

@@ -14 +14 @@
 #define FAC_BIVAR_H
 
-#include <config.h>
-
-#include "assert.h"
+#include "config.h"
+
+#include "cf_assert.h"
+#include "timing.h"
 
 #include "facFqBivarUtil.h"
@@ -26 +27 @@
 #include "algext.h"
 #include "fac_util.h"
+
+TIMING_DEFINE_PRINT(fac_bi_sqrf)
+TIMING_DEFINE_PRINT(fac_bi_factor_sqrf)
 
 /// @return @a biFactorize returns a list of factors of F. If F is not monic
@@ -196 +200 @@
   vec_ZZ S;
   F= compress (F, M, S);
+  TIMING_START (fac_bi_sqrf);
   CFFList sqrfFactors= sqrFree (F);
+  TIMING_END_AND_PRINT (fac_bi_sqrf,
+                       "time for bivariate sqrf factors over Q: ");
   for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
   {
+    TIMING_START (fac_bi_factor_sqrf);
     CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
+    TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over Q: ");
     for (CFListIterator j= tmp; j.hasItem(); j++)
     {

factory/facFactorize.cc

@@ -29 +29 @@
 #include "facSparseHensel.h"
 
-TIMING_DEFINE_PRINT(fac_bi_factorize)
+TIMING_DEFINE_PRINT(fac_bi_factorizer)
 TIMING_DEFINE_PRINT(fac_hensel_lift)
 TIMING_DEFINE_PRINT(fac_factor_recombination)
+TIMING_DEFINE_PRINT(fac_shift_to_zero)
+TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
+TIMING_DEFINE_PRINT(fac_evaluation)
+TIMING_DEFINE_PRINT(fac_recover_factors)
+TIMING_DEFINE_PRINT(fac_preprocess_and_content)
+TIMING_DEFINE_PRINT(fac_bifactor_total)
+TIMING_DEFINE_PRINT(fac_luckswang)
+TIMING_DEFINE_PRINT(fac_lcheuristic)
+TIMING_DEFINE_PRINT(fac_cleardenom)
+TIMING_DEFINE_PRINT(fac_content)
+TIMING_DEFINE_PRINT(fac_compress)
 
 #ifdef HAVE_NTL
@@ -149 +160 @@
       Aeval [j]= factors;
     }
-    else if (!Aeval[j].isEmpty())
-      Aeval[j]=CFList();
   }
 }
-
-int
-testFactors (const CanonicalForm& G, const CFList& uniFactors,
-             CanonicalForm& sqrfPartF, CFList& factors,
-             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
-             const CFArray& evalPoint)
-{
-  CanonicalForm tmp;
-  CFListIterator j;
-  for (CFListIterator i= uniFactors; i.hasItem(); i++)
-  {
-    tmp= i.getItem();
-    if (i.hasItem())
-      i++;
-    else
-      break;
-    for (j= i; j.hasItem(); j++)
-    {
-      if (tmp == j.getItem())
-        return 0;
-    }
-  }
-
-  CanonicalForm F= G;
-  CFFList sqrfFactorization= sqrFree (F);
-
-  sqrfPartF= 1;
-  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
-    sqrfPartF *= i.getItem().factor();
-
-  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
-
-  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
-
-  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
-    return 0;
-
-  CFFList sqrfFactors;
-  CFList tmp2;
-  int k= 0;
-  factors= uniFactors;
-  CFFListIterator iter;
-  for (CFListIterator i= factors; i.hasItem(); i++, k++)
-  {
-    tmp= 1;
-    sqrfFactors= sqrFree (i.getItem());
-
-    for (iter= sqrfFactors; iter.hasItem(); iter++)
-    {
-      tmp2.append (iter.getItem().factor());
-      tmp *= iter.getItem().factor();
-    }
-    i.getItem()= tmp/Lc(tmp);
-    bufSqrfFactors [k]= sqrfFactors;
-  }
-
-  for (int i= 0; i < factors.length() - 1; i++)
-  {
-    for (int k= i + 1; k < factors.length(); k++)
-    {
-      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
-    }
-  }
-
-  factors= CFList();
-  for (int i= 0; i < uniFactors.length(); i++)
-  {
-    if (i == 0)
-    {
-      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
-      {
-        if (iter.getItem().factor().inCoeffDomain())
-          continue;
-        iter.getItem()= CFFactor (iter.getItem().factor()/
-                                  Lc (iter.getItem().factor()),
-                                  iter.getItem().exp());
-        factors.append (iter.getItem().factor());
-      }
-    }
-    else
-    {
-      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
-      {
-        if (iter.getItem().factor().inCoeffDomain())
-          continue;
-        iter.getItem()= CFFactor (iter.getItem().factor()/
-                               Lc (iter.getItem().factor()),
-                               iter.getItem().exp());
-        if (!find (factors, iter.getItem().factor()))
-          factors.append (iter.getItem().factor());
-      }
-    }
-  }
-
-  test= prod (factors);
-  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
-  if (test/Lc (test) != tmp/Lc (tmp))
-    return 0;
-  else
-    return 1;
-}
-
-CFList
-precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
-                        const CFList& evaluation,CFList*& differentSecondVarLCs,
-                        int length, Variable& y
-                       )
-{
-  y= Variable (1);
-  if (LCF.inCoeffDomain())
-  {
-    CFList result;
-    for (int i= 1; i <= LCFFactors.length() + 1; i++)
-      result.append (1);
-    return result;
-  }
-
-  CFMap N, M;
-  CFArray dummy= CFArray (2);
-  dummy [0]= LCF;
-  dummy [1]= Variable (2);
-  compress (dummy, M, N);
-  CanonicalForm F= M (LCF);
-  if (LCF.isUnivariate())
-  {
-    CFList result;
-    int LCFLevel= LCF.level();
-    bool found= false;
-    if (LCFLevel == 2)
-    {
-    //bivariate leading coefficients are already the true leading coefficients
-      result= LCFFactors;
-      found= true;
-    }
-    else
-    {
-      CFListIterator j;
-      for (int i= 0; i < length; i++)
-      {
-        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
-        {
-          if (j.getItem().level() == LCFLevel)
-          {
-            found= true;
-            break;
-          }
-        }
-        if (found)
-        {
-          result= differentSecondVarLCs [i];
-          break;
-        }
-      }
-      if (!found)
-        result= LCFFactors;
-    }
-    if (found)
-      result.insert (Lc (LCF));
-    else
-    {
-      for (CFListIterator i= result; i.hasItem(); i++)
-        i.getItem() *= LCF;
-      result.insert (LCF);
-    }
-    return result;
-  }
-
-  CFList factors= LCFFactors;
-
-  for (CFListIterator i= factors; i.hasItem(); i++)
-    i.getItem()= M (i.getItem());
-
-  CanonicalForm sqrfPartF;
-  CFFList * bufSqrfFactors= new CFFList [factors.length()];
-  CFList evalSqrfPartF, bufFactors;
-  CFArray evalPoint= CFArray (evaluation.length() - 1);
-  CFArray buf= CFArray (evaluation.length());
-  CFArray swap= CFArray (evaluation.length());
-  CFListIterator iter= evaluation;
-  CanonicalForm vars=getVars (LCF)*Variable (2);
-  for (int i= evaluation.length() +1; i > 1; i--, iter++)
-  {
-    buf[i-2]=iter.getItem();
-    if (degree (vars, i) > 0)
-      swap[M(Variable (i)).level()-1]=buf[i-2];
-  }
-  buf= swap;
-  for (int i= 0; i < evaluation.length() - 1; i++)
-    evalPoint[i]= buf[i+1];
-
-  //TODO sqrfPartF einmal berechnen nicht stÀndig
-  int pass= testFactors (F, factors, sqrfPartF,
-                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
-
-  bool foundDifferent= false;
-  Variable z;
-  Variable x= y;
-  int j= 0;
-  if (!pass)
-  {
-    int lev= 0;
-    CanonicalForm bufF;
-    CFList bufBufFactors;
-    for (int i= 0; i < length; i++)
-    {
-      if (!differentSecondVarLCs [i].isEmpty())
-      {
-        bool allConstant= true;
-        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
-        {
-          if (!iter.getItem().inCoeffDomain())
-          {
-            allConstant= false;
-            y= Variable (iter.getItem().level());
-            lev= M(y).level();
-          }
-        }
-        if (allConstant)
-          continue;
-
-        bufFactors= differentSecondVarLCs [i];
-        for (iter= bufFactors; iter.hasItem(); iter++)
-          iter.getItem()= swapvar (iter.getItem(), x, y);
-        bufF= F;
-        z= Variable (lev);
-        bufF= swapvar (bufF, x, z);
-        bufBufFactors= bufFactors;
-        evalPoint= CFArray (evaluation.length() - 1);
-        for (int k= 0; k < evaluation.length()-1; k++)
-        {
-          if (N (Variable (k+1)).level() != y.level())
-            evalPoint[k]= buf[k+1];
-          else
-            evalPoint[k]= buf[0];
-        }
-        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
-                           bufSqrfFactors, evalSqrfPartF, evalPoint);
-        if (pass)
-        {
-          foundDifferent= true;
-          F= bufF;
-          CFList l= factors;
-          for (iter= l; iter.hasItem(); iter++)
-            iter.getItem()= swapvar (iter.getItem(), x, y);
-          differentSecondVarLCs [i]= l;
-          j= i;
-          break;
-        }
-        if (!pass && i == length - 1)
-        {
-          CFList result;
-          result.append (LCF);
-          for (int j= 1; j <= factors.length(); j++)
-            result.append (1);
-          result= distributeContent (result, differentSecondVarLCs, length);
-          if (!result.getFirst().inCoeffDomain())
-          {
-            CFListIterator iter= result;
-            CanonicalForm tmp= iter.getItem();
-            iter++;
-            for (; iter.hasItem(); iter++)
-              iter.getItem() *= tmp;
-          }
-
-          y= Variable (1);
-          delete [] bufSqrfFactors;
-          return result;
-        }
-      }
-    }
-  }
-  if (!pass)
-  {
-    CFList result;
-    result.append (LCF);
-    for (int j= 1; j <= factors.length(); j++)
-      result.append (LCF);
-    y= Variable (1);
-    delete [] bufSqrfFactors;
-    return result;
-  }
-  else
-    factors= bufFactors;
-
-
-  bufFactors= factors;
-
-  CFMap MM, NN;
-  dummy [0]= sqrfPartF;
-  dummy [1]= 1;
-  compress (dummy, MM, NN);
-  sqrfPartF= MM (sqrfPartF);
-  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
-  for (CFListIterator iter= factors; iter.hasItem(); iter++)
-    iter.getItem()= MM (iter.getItem());
-
-  CFList evaluation2;
-  for (int i= 2; i <= varsSqrfPartF.level(); i++)
-    evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
-
-  CFList interMedResult;
-  CanonicalForm oldSqrfPartF= sqrfPartF;
-  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
-  if (factors.length() > 1)
-  {
-    CanonicalForm LC1= LC (oldSqrfPartF, 1);
-    CFList leadingCoeffs;
-    for (int i= 0; i < factors.length(); i++)
-      leadingCoeffs.append (LC1);
-
-    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
-    CFList oldFactors= factors;
-    for (CFListIterator i= oldFactors; i.hasItem(); i++)
-      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
-
-    bool success= false;
-    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
-    CFList heuResult;
-    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
-        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
-                                  oldFactors, 2, leadingCoeffs, heuResult))
-    {
-      interMedResult= recoverFactors (oldSqrfPartF, heuResult);
-      if (oldFactors.length() == interMedResult.length())
-        success= true;
-    }
-    if (!success)
-    {
-      LC1= LC (evalSqrfPartF.getFirst(), 1);
-
-      CFArray leadingCoeffs= CFArray (factors.length());
-      for (int i= 0; i < factors.length(); i++)
-        leadingCoeffs[i]= LC1;
-
-      for (CFListIterator i= factors; i.hasItem(); i++)
-        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
-      factors.insert (1);
-
-      CanonicalForm
-      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
-
-      int liftBound= degree (newSqrfPartF,2) + 1;
-
-      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
-      CFArray Pi;
-      CFList diophant;
-      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
-                            leadingCoeffs, false);
-
-      if (sqrfPartF.level() > 2)
-      {
-        int* liftBounds= new int [sqrfPartF.level() - 1];
-        liftBounds [0]= liftBound;
-        bool noOneToOne= false;
-        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
-        LC1= LC (evalSqrfPartF.getLast(), 1);
-        CFList LCs;
-        for (int i= 0; i < factors.length(); i++)
-          LCs.append (LC1);
-        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
-        for (int i= sqrfPartF.level() - 1; i > 2; i--)
-        {
-          for (CFListIterator j= LCs; j.hasItem(); j++)
-            j.getItem()= j.getItem() (0, i + 1);
-          leadingCoeffs2 [i - 3]= LCs;
-        }
-        sqrfPartF *= power (LC1, factors.length()-1);
-
-        int liftBoundsLength= sqrfPartF.level() - 1;
-        for (int i= 1; i < liftBoundsLength; i++)
-          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
-        evalSqrfPartF= evaluateAtZero (sqrfPartF);
-        evalSqrfPartF.removeFirst();
-        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
-                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
-        delete [] leadingCoeffs2;
-        delete [] liftBounds;
-      }
-      for (CFListIterator iter= factors; iter.hasItem(); iter++)
-        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
-
-      interMedResult=
-      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
-                      factors);
-    }
-  }
-  else
-  {
-    CanonicalForm contF=content (oldSqrfPartF,1);
-    factors= CFList (oldSqrfPartF/contF);
-    interMedResult= recoverFactors (oldSqrfPartF, factors);
-  }
-
-  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
-    iter.getItem()= NN (iter.getItem());
-
-  CFList result;
-  CFFListIterator k;
-  CanonicalForm tmp;
-  for (int i= 0; i < LCFFactors.length(); i++)
-  {
-    tmp= 1;
-    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
-    {
-      int pos= findItem (bufFactors, k.getItem().factor());
-      if (pos)
-        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
-    }
-    result.append (tmp);
-  }
-
-  for (CFListIterator i= result; i.hasItem(); i++)
-  {
-    F /= i.getItem();
-    if (foundDifferent)
-      i.getItem()= swapvar (i.getItem(), x, z);
-    i.getItem()= N (i.getItem());
-  }
-
-  if (foundDifferent)
-  {
-    CFList l= differentSecondVarLCs [j];
-    for (CFListIterator i= l; i.hasItem(); i++)
-      i.getItem()= swapvar (i.getItem(), y, z);
-    differentSecondVarLCs [j]= l;
-    F= swapvar (F, x, z);
-  }
-
-  result.insert (N (F));
-
-  result= distributeContent (result, differentSecondVarLCs, length);
-
-  if (!result.getFirst().inCoeffDomain())
-  {
-    CFListIterator i= result;
-    CanonicalForm tmp;
-    if (foundDifferent)
-      i.getItem()= swapvar (i.getItem(), Variable (2), y);
-
-    tmp= i.getItem();
-
-    i++;
-    for (; i.hasItem(); i++)
-    {
-      if (foundDifferent)
-        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
-      else
-        i.getItem() *= tmp;
-    }
-  }
-  else
-    y= Variable (1);
-
-  delete [] bufSqrfFactors;
-
-  return result;
-}
-
 
 CFList
@@ -618 +169 @@
     return CFList (F);
 
+  TIMING_START (fac_preprocess_and_content);
   // compress and find main Variable
   CFMap N;
+  TIMING_START (fac_compress)
   CanonicalForm A= myCompress (F, N);
+  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
 
   //univariate case
@@ -646 +200 @@
 
   // remove content
+  TIMING_START (fac_content);
   CFList contentAi;
   CanonicalForm lcmCont= lcmContent (A, contentAi);
   A /= lcmCont;
+  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
 
   // trivial after content removal
@@ -674 +230 @@
 
   // factorize content
+  TIMING_START (fac_content);
   contentAFactors= multiFactorize (lcmCont, v);
+  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
 
   // univariate after content removal
@@ -690 +248 @@
 
   A *= bCommonDen (A);
-  // check main variable
   CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
   int factorNums= 1;
-  CanonicalForm bivarEval;
   CFList biFactors, bufBiFactors;
   CanonicalForm evalPoly;
@@ -702 +258 @@
   int differentSecondVar= 0;
   CanonicalForm bufA;
+  TIMING_END_AND_PRINT (fac_preprocess_and_content,
+                       "time to preprocess poly and extract content over Q: ");
+
   // several bivariate factorizations
+  TIMING_START (fac_bifactor_total);
   REvaluation E (2, A.level(), IntRandom (25));
   for (int i= 0; i < factorNums; i++)
@@ -709 +269 @@
     bufA= A;
     bufAeval= CFList();
+    TIMING_START (fac_evaluation);
     bufEvaluation= evalPoints (bufA, bufAeval, E);
+    TIMING_END_AND_PRINT (fac_evaluation,
+                          "time to find evaluation point over Q: ");
     E.nextpoint();
     evalPoly= 0;
 
-    bivarEval= bufEvaluation.getLast();
-
+    TIMING_START (fac_evaluation);
     evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
+    TIMING_END_AND_PRINT (fac_evaluation,
+                          "time to eval wrt diff second vars over Q: ");
 
     for (int j= 0; j < lengthAeval2; j++)
@@ -725 +289 @@
     bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
 
-    TIMING_START (fac_bi_factorize);
+    TIMING_START (fac_bi_factorizer);
     bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
-    TIMING_END_AND_PRINT (fac_bi_factorize,
+    TIMING_END_AND_PRINT (fac_bi_factorizer,
                           "time for bivariate factorization: ");
     bufBiFactors.removeFirst();
@@ -779 +343 @@
   int minFactorsLength;
   bool irred= false;
+  TIMING_START (fac_bi_factorizer);
   factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
-
+  TIMING_END_AND_PRINT (fac_bi_factorizer,
+             "time for bivariate factorization wrt diff second vars over Q: ");
+
+  TIMING_END_AND_PRINT (fac_bifactor_total,
+                        "total time for eval and bivar factors over Q: ");
   if (irred)
   {
@@ -839 +408 @@
 
   Variable w;
-  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
+  TIMING_START (fac_precompute_leadcoeff);
+  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
                                           evaluation, Aeval2, lengthAeval2, w);
 
@@ -940 +510 @@
     }
   }
+  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
+                       "time to precompute LC over Q: ");
+
+  TIMING_START (fac_luckswang);
   CFList bufFactors= CFList();
   bool LCheuristic= false;
@@ -962 +536 @@
       delete [] index;
       delete [] Aeval2;
+      TIMING_END_AND_PRINT (fac_luckswang,
+                            "time for successful LucksWang over Q: ");
       return factors;
     }
@@ -1300 +876 @@
     delete [] index;
   }
+  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
+
+  TIMING_START (fac_lcheuristic);
   if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
       && fdivides (getVars (LCmultiplier), testVars))
@@ -1449 +1028 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
 
 tryAgainWithoutHeu:
   //shifting to zero
+  TIMING_START (fac_shift_to_zero);
+  CanonicalForm denA= bCommonDen (A);
+  A *= denA;
   A= shift2Zero (A, Aeval, evaluation);
+  A /= denA;
 
   for (iter= biFactors; iter.hasItem(); iter++)
@@ -1470 +1054 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_shift_to_zero,
+                        "time to shift evaluation point to zero: ");
 
   CFArray Pi;
@@ -1481 +1067 @@
   bool noOneToOne= false;
 
+  TIMING_START (fac_cleardenom);
   CFList commonDenominators;
   for (iter=biFactors; iter.hasItem(); iter++)
@@ -1499 +1086 @@
   for (iter= Aeval; iter.hasItem(); iter++)
   {
-    tmp2= bCommonDen (iter.getItem());
+    tmp2= bCommonDen (iter.getItem()/denA);
     Off (SW_RATIONAL);
     tmp3= lcm (tmp2,tmp3);
@@ -1511 +1098 @@
 
   for (iter= Aeval; iter.hasItem(); iter++)
-    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
+    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
 
   for (int i= 0; i < lengthAeval2; i++)
@@ -1519 +1106 @@
       iter.getItem() *= iter2.getItem()*multiplier;
   }
-
-
+  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
+
+  TIMING_START (fac_hensel_lift);
   factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
                                Pi, liftBounds, liftBoundsLength, noOneToOne);
+  TIMING_END_AND_PRINT (fac_hensel_lift,
+                        "time for non monic hensel lifting over Q: ");
 
   if (!noOneToOne)
@@ -1528 +1118 @@
     int check= factors.length();
     A= oldA;
+    TIMING_START (fac_recover_factors);
     factors= recoverFactors (A, factors, evaluation);
+    TIMING_END_AND_PRINT (fac_recover_factors,
+                          "time to recover factors over Q: ");
     if (check != factors.length())
       noOneToOne= true;

factory/facFactorize.h

@@ -14 +14 @@
 #define FAC_FACTORIZE_H
 
-// #include "config.h"
+#include "config.h"
+#include "timing.h"
 
 #include "facBivar.h"
 #include "facFqBivarUtil.h"
+
+TIMING_DEFINE_PRINT (fac_squarefree)
+TIMING_DEFINE_PRINT (fac_factor_squarefree)
 
 /// Factorization over Q (a)
@@ -120 +124 @@
 
   CFFList result;
+  TIMING_START (fac_squarefree);
   CFFList sqrfFactors= sqrFree (F);
+  TIMING_END_AND_PRINT (fac_squarefree,
+                        "time for squarefree factorization over Q: ");
+
+  CFList tmp;
   for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
   {
-    CFList tmp= ratSqrfFactorize (i.getItem().factor(), v);
+    TIMING_START (fac_factor_squarefree);
+    tmp= ratSqrfFactorize (i.getItem().factor(), v);
+    TIMING_END_AND_PRINT (fac_factor_squarefree,
+                          "time to factorize sqrfree factor over Q: ");
     for (CFListIterator j= tmp; j.hasItem(); j++)
     {

factory/facFqBivar.cc

@@ -46 +46 @@
 TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift)
 TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination)
+TIMING_DEFINE_PRINT(fac_fq_bi_evaluation)
+TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero)
 
 CanonicalForm prodMod0 (const CFList& L, const CanonicalForm& M, const modpk& b)
@@ -6082 +6084 @@
   {
     bufAeval= A;
+    TIMING_START (fac_fq_bi_evaluation);
     bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
+    TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
     if (!derivXZero && !fail2 && !symmetric)
     {
@@ -6091 +6095 @@
       }
       bufAeval2= buf;
+      TIMING_START (fac_fq_bi_evaluation);
       bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
+      TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
+                            "time to find eval point wrt y: ");
     }
     // first try to change main variable if there is no valid evaluation point
@@ -6132 +6139 @@
     bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
     TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
-                          "time for univariate factorization: ");
+                          "time for univariate factorization over Fq: ");
     DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
               (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
@@ -6141 +6148 @@
       bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
       TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
-                            "time for univariate factorization in y: ");
+                            "time for univariate factorization in y over Fq: ");
       DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
                 (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
@@ -6291 +6298 @@
   }
 
+  TIMING_START (fac_fq_bi_shift_to_zero);
   A= A (y + evaluation, y);
+  TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
+                        "time to shift eval to zero: ");
 
   int degMipo= 1;
@@ -6307 +6317 @@
                (A, earlySuccess, earlyFactors, degs, liftBound,
                 uniFactors, info, evaluation);
-    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                          "time for bivariate hensel lifting over Fq: ");
     DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
     CanonicalForm MODl= power (y, liftBound);
 
+    TIMING_START (fac_fq_bi_factor_recombination);
     if (extension)
       factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
@@ -6318 +6330 @@
       factors= factorRecombination (uniFactors, A, MODl, degs, 1,
                                     uniFactors.length()/2);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
+                          "time for naive bivariate factor recombi over Fq: ");
 
     if (earlySuccess)
@@ -6346 +6360 @@
       factors= Union (lll, factors);
     }
-    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                          "time to bivar lift and LLL recombi over Fq: ");
     DEBOUTLN (cerr, "lifted factors= " << uniFactors);
   }
@@ -6357 +6372 @@
                (A, earlySuccess, earlyFactors, degs, liftBound,
                 uniFactors, info, evaluation);
-    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                          "time for bivar hensel lifting over Fq: ");
     DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
@@ -6363 +6379 @@
     if (!extension)
     {
+      TIMING_START (fac_fq_bi_factor_recombination);
       factors= factorRecombination (uniFactors, A, MODl, degs, 1, 3);
+      TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
+                            "time for small subset naive recombi over Fq: ");
 
       int oldUniFactorsLength= uniFactors.length();
@@ -6369 +6388 @@
       {
         CFList tmp;
+        TIMING_START (fac_fq_bi_hensel_lift);
         if (alpha.level() == 1)
           tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
@@ -6384 +6404 @@
                                    );
         }
+        TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                              "time to increase precision: ");
         factors= Union (factors, tmp);
         if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0

factory/facFqBivar.h

@@ -15 +15 @@
 #define FAC_FQ_BIVAR_H
 
-// #include "config.h"
-
+ #include "config.h"
+
+#include "timing.h"
 #include "cf_assert.h"
 
@@ -26 +27 @@
 #include "cf_map.h"
 #include "cfNewtonPolygon.h"
+
+TIMING_DEFINE_PRINT(fac_fq_bi_sqrf)
+TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf)
 
 static const double log2exp= 1.442695041;
@@ -273 +277 @@
   F= compress (F, M, S);
 
+  TIMING_START (fac_fq_bi_sqrf);
   CFFList sqrf= FpSqrf (F, false);
+  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
+                       "time for bivariate sqrf factors over Fp: ");
   CFList bufResult;
   sqrf.removeFirst();
@@ -279 +286 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_bi_factor_sqrf);
     bufResult= biFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over Fp: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (N (decompress (i.getItem(), M, S)),
@@ -374 +384 @@
   F= compress (F, M, S);
 
+  TIMING_START (fac_fq_bi_sqrf);
   CFFList sqrf= FqSqrf (F, alpha, false);
+  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
+                       "time for bivariate sqrf factors over Fq: ");
   CFList bufResult;
   sqrf.removeFirst();
@@ -380 +393 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_bi_factor_sqrf);
     bufResult= biFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over Fq: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (N (decompress (i.getItem(), M, S)),
@@ -476 +492 @@
   F= compress (F, M, S);
 
+  TIMING_START (fac_fq_bi_sqrf);
   CFFList sqrf= GFSqrf (F, false);
+  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
+                       "time for bivariate sqrf factors over GF: ");
   CFList bufResult;
   sqrf.removeFirst();
@@ -482 +501 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_bi_factor_sqrf);
     bufResult= biFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over GF: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (N (decompress (i.getItem(), M, S)),

factory/facFqFactorize.cc

@@ -38 +38 @@
 TIMING_DEFINE_PRINT(fac_fq_hensel_lift)
 TIMING_DEFINE_PRINT(fac_fq_factor_recombination)
+TIMING_DEFINE_PRINT(fac_fq_shift_to_zero)
+TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff)
+TIMING_DEFINE_PRINT(fac_fq_evaluation)
+TIMING_DEFINE_PRINT(fac_fq_recover_factors)
+TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content)
+TIMING_DEFINE_PRINT(fac_fq_bifactor_total)
+TIMING_DEFINE_PRINT(fac_fq_luckswang)
+TIMING_DEFINE_PRINT(fac_fq_lcheuristic)
+TIMING_DEFINE_PRINT(fac_fq_content)
+TIMING_DEFINE_PRINT(fac_fq_check_mainvar)
+TIMING_DEFINE_PRINT(fac_fq_compress)
 
 static inline
@@ -894 +905 @@
 {
   int i= A.level();
-  contentAi.append (myContent (A, i));
-  contentAi.append (myContent (A, i - 1));
+  CanonicalForm buf= A;
+  contentAi.append (content (buf, i));
+  buf /= contentAi.getLast();
+  contentAi.append (content (buf, i - 1));
   CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
   for (i= i - 2; i > 0; i--)
   {
-    contentAi.append (content (A, i));
+    contentAi.append (content (buf, i));
+    buf /= contentAi.getLast();
     result= lcm (result, contentAi.getLast());
   }
@@ -1327 +1341 @@
 
   CanonicalForm F= G;
-  CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
+  CFFList sqrfFactorization;
+  if (getCharacteristic() > 0)
+    sqrfFactorization= squarefreeFactorization (F, alpha);
+  else
+    sqrfFactorization= sqrFree (F);
 
   sqrfPartF= 1;
@@ -1348 +1366 @@
   {
     tmp= 1;
-    sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
+    if (getCharacteristic() > 0)
+      sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
+    else
+      sqrfFactors= sqrFree (i.getItem());
 
     for (iter= sqrfFactors; iter.hasItem(); iter++)
@@ -2189 +2210 @@
     return CFList (F);
 
+  TIMING_START (fac_fq_preprocess_and_content);
   // compress and find main Variable
   CFMap N;
+  TIMING_START (fac_fq_compress)
   CanonicalForm A= myCompress (F, N);
+  TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
 
   A /= Lc (A); // make monic
@@ -2225 +2249 @@
 
   // remove content
+  TIMING_START (fac_fq_content);
   CFList contentAi;
   CanonicalForm lcmCont= lcmContent (A, contentAi);
   A /= lcmCont;
+  TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
 
   // trivial after content removal
@@ -2253 +2279 @@
 
   // factorize content
+  TIMING_START (fac_fq_content);
   contentAFactors= multiFactorize (lcmCont, info);
+  TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
 
   // univariate after content removal
@@ -2266 +2294 @@
 
   // check main variable
+  TIMING_START (fac_fq_check_mainvar);
   int swapLevel= 0;
   CanonicalForm derivZ;
@@ -2308 +2337 @@
     }
   }
-
+  TIMING_END_AND_PRINT (fac_fq_check_mainvar,
+                        "time to check main var over Fq: ");
+  TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
+                       "time to preprocess poly and extract content over Fq: ");
 
   CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
@@ -2315 +2347 @@
   int level;
   int factorNums= 3;
-  CanonicalForm bivarEval;
   CFList biFactors, bufBiFactors;
   CanonicalForm evalPoly;
@@ -2329 +2360 @@
   int differentSecondVar= 0;
   // several bivariate factorizations
+  TIMING_START (fac_fq_bifactor_total);
   for (int i= 0; i < factorNums; i++)
   {
@@ -2334 +2366 @@
     bufA= A;
     bufAeval= CFList();
+    TIMING_START (fac_fq_evaluation);
     bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
+    TIMING_END_AND_PRINT (fac_fq_evaluation,
+                          "time to find evaluation point over Fq: ");
     evalPoly= 0;
 
@@ -2379 +2414 @@
       break;
 
-    bivarEval= bufEvaluation.getLast();
-
+    TIMING_START (fac_fq_evaluation);
     evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
+    TIMING_END_AND_PRINT (fac_fq_evaluation,
+                          "time for evaluation wrt diff second vars over Fq: ");
 
     for (int j= 0; j < lengthAeval2; j++)
@@ -2456 +2492 @@
   int minFactorsLength;
   bool irred= false;
+  TIMING_START (fac_fq_bi_factorizer);
   factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
-
+  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
+             "time for bivariate factorization wrt diff second vars over Fq: ");
+
+  TIMING_END_AND_PRINT (fac_fq_bifactor_total,
+                        "total time for eval and bivar factors over Fq: ");
   if (irred)
   {
@@ -2528 +2569 @@
 
   Variable v;
+  TIMING_START (fac_fq_precompute_leadcoeff);
   CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
                                           evaluation, Aeval2, lengthAeval2, v);
@@ -2627 +2669 @@
     }
   }
+  TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
+                       "time to precompute LC over Fq: ");
+
+  TIMING_START (fac_fq_luckswang);
   CFList bufFactors= CFList();
   bool LCheuristic= false;
@@ -2654 +2700 @@
       delete [] index;
       delete [] Aeval2;
+      TIMING_END_AND_PRINT (fac_fq_luckswang,
+                            "time for successful LucksWang over Fq: ");
       return factors;
     }
@@ -2993 +3041 @@
     delete [] index;
   }
-
+  TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
+
+  TIMING_START (fac_fq_lcheuristic);
   if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
       && fdivides (getVars (LCmultiplier), testVars))
@@ -3143 +3193 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
 
 tryAgainWithoutHeu:
+  TIMING_START (fac_fq_shift_to_zero);
   A= shift2Zero (A, Aeval, evaluation);
 
@@ -3163 +3215 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
+                        "time to shift evaluation point to zero: ");
 
   CFArray Pi;
@@ -3173 +3227 @@
   Aeval.removeFirst();
   bool noOneToOne= false;
+  TIMING_START (fac_fq_hensel_lift);
   factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
                                Pi, liftBounds, liftBoundsLength, noOneToOne);
+  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
+                        "time for non monic hensel lifting over Fq: ");
 
   if (!noOneToOne)
@@ -3180 +3237 @@
     int check= factors.length();
     A= oldA;
+    TIMING_START (fac_fq_recover_factors);
     factors= recoverFactors (A, factors, evaluation);
+    TIMING_END_AND_PRINT (fac_fq_recover_factors,
+                          "time to recover factors over Fq: ");
     if (check != factors.length())
       noOneToOne= true;
@@ -3239 +3299 @@
                    (A, MOD, liftBounds, earlySuccess, earlyFactors,
                     Aeval, biFactors, evaluation, info);
-    TIMING_END_AND_PRINT (fac_fq_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_hensel_lift,
+                          "time for hensel lifting over Fq: ");
 
     if (!extension)

factory/facFqFactorize.h

@@ -15 +15 @@
 #define FAC_FQ_FACTORIZE_H
 
-// #include "config.h"
+#include "config.h"
+#include "timing.h"
 
 #include "facFqBivar.h"
@@ -23 +24 @@
 #include "facFqSquarefree.h"
 #include "facFqBivarUtil.h"
+
+
+TIMING_DEFINE_PRINT (fac_fq_squarefree)
+TIMING_DEFINE_PRINT (fac_fq_factor_squarefree)
 
 /// Factorization over a finite field
@@ -150 +155 @@
   Variable a= Variable (1);
   CanonicalForm LcF= Lc (F);
+  TIMING_START (fac_fq_squarefree);
   CFFList sqrf= FpSqrf (F, false);
+  TIMING_END_AND_PRINT (fac_fq_squarefree,
+                        "time for squarefree factorization over Fq: ");
   CFFList result;
   CFList bufResult;
@@ -157 +165 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_factor_squarefree);
     bufResult= multiFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
+                          "time to factorize sqrfree factor over Fq: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (i.getItem(), iter.getItem().exp()));
@@ -227 +238 @@
   ExtensionInfo info= ExtensionInfo (alpha, false);
   CanonicalForm LcF= Lc (F);
+  TIMING_START (fac_fq_squarefree);
   CFFList sqrf= FqSqrf (F, alpha, false);
+  TIMING_END_AND_PRINT (fac_fq_squarefree,
+                        "time for squarefree factorization over Fq: ");
   CFFList result;
   CFList bufResult;
@@ -234 +248 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_factor_squarefree);
     bufResult= multiFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
+                          "time to factorize sqrfree factor over Fq: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (i.getItem(), iter.getItem().exp()));
@@ -640 +657 @@
              );
 
+/// computes a list l of length length(LCFFactors)+1 of polynomials such that
+/// prod (l)=LCF, note that the first entry of l may be non constant. Intended
+/// to be used to precompute coefficients of a polynomial f from its bivariate 
+/// factorizations.
+///
+/// @return see above
+CFList
+precomputeLeadingCoeff (const CanonicalForm& LCF,       ///<[in] a multivariate
+                                                        ///< poly
+                        const CFList& LCFFactors,       ///<[in] a list of
+                                                        ///< univariate factors
+                                                        ///< of LCF of level 2
+                        const Variable& alpha,          ///<[in] algebraic var.
+                        const CFList& evaluation,       ///<[in] an evaluation
+                                                        ///< point having
+                                                        ///< lSecondVarLCs+1
+                                                        ///< components
+                        CFList* & differentSecondVarLCs,///<[in] LCs of factors
+                                                        ///< of f wrt different
+                                                        ///< second variables
+                        int lSecondVarLCs,              ///<[in] length of the
+                                                        ///< above
+                        Variable& y                     ///<[in,out] if y.level()
+                                                        ///< is not 1 on output
+                                                        ///< the second variable
+                                                        ///< has been changed to
+                                                        ///< y
+                       );
+
 #endif
 /* FAC_FQ_FACTORIZE_H */

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)

factory/libfac/factor/timing.h

@@ -43 +43 @@
 #if defined(WINNT) && ! defined(__GNUC__)
 
-#define TIMING_START(t) { clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
-  timing_ ## t ## _start = clock();
+#define TIMING_START(t) timing_ ## t ## _start = clock();
 #define TIMING_END(t) timing_ ## t ## _end = clock(); \
-timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
+timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
 #define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
   fprintf( stderr, "%s%.2f sec\n", msg, \
            float( timing_ ## t ## _end - timing_ ## t ## _start ) / HZ ); \
-  timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
-#define TIMING_DEFINE_PRINT(t) clock_t timing_ ## t ## _time; \
-void timing_print_ ## t ( char * msg ) { \
+  timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
+#define TIMING_DEFINE_PRINT(t) static clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
+static clock_t timing_ ## t ## _time; \
+static void timing_print_ ## t ( char * msg ) { \
   fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
 } \
-void timing_reset_ ## t () { \
+static void timing_reset_ ## t () { \
   timing_ ## t ## _time = 0; \
 }
@@ -61 +61 @@
 #else /* ! WINNT */
 
-#define TIMING_START(t) { struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
-  times( &timing_ ## t ## _start );
+#define TIMING_START(t) times( &timing_ ## t ## _start );
 #define TIMING_END(t) times( &timing_ ## t ## _end ); \
-  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
+  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
 #define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
   fprintf( stderr, "%s%.2f sec\n", msg, \
            float( timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime ) / HZ ); \
-  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
-#define TIMING_DEFINE_PRINT(t) long timing_ ## t ## _time; \
-void timing_print_ ## t ( char * msg ) { \
+  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
+#define TIMING_DEFINE_PRINT(t) static struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
+static long timing_ ## t ## _time; \
+static void timing_print_ ## t ( char * msg ) { \
   fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
 } \
-void timing_reset_ ## t () { \
+static void timing_reset_ ## t () { \
   timing_ ## t ## _time = 0; \
 }

factory/timing.h

@@ -43 +43 @@
 #if defined(WINNT) && ! defined(__GNUC__)
 
-#define TIMING_START(t) { clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
-  timing_ ## t ## _start = clock();
+#define TIMING_START(t) timing_ ## t ## _start = clock();
 #define TIMING_END(t) timing_ ## t ## _end = clock(); \
-timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
+timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
 #define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
   fprintf( stderr, "%s%.2f sec\n", msg, \
            float( timing_ ## t ## _end - timing_ ## t ## _start ) / HZ ); \
-  timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
-#define TIMING_DEFINE_PRINT(t) clock_t timing_ ## t ## _time; \
-void timing_print_ ## t ( char * msg ) { \
+  timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
+#define TIMING_DEFINE_PRINT(t) static clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
+static clock_t timing_ ## t ## _time; \
+static void timing_print_ ## t ( char * msg ) { \
   fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
 } \
-void timing_reset_ ## t () { \
+static void timing_reset_ ## t () { \
   timing_ ## t ## _time = 0; \
 }
@@ -61 +61 @@
 #else /* ! WINNT */
 
-#define TIMING_START(t) { struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
-  times( &timing_ ## t ## _start );
+#define TIMING_START(t) times( &timing_ ## t ## _start );
 #define TIMING_END(t) times( &timing_ ## t ## _end ); \
-  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
+  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
 #define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
   fprintf( stderr, "%s%.2f sec\n", msg, \
            float( timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime ) / HZ ); \
-  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
-#define TIMING_DEFINE_PRINT(t) long timing_ ## t ## _time; \
-void timing_print_ ## t ( char * msg ) { \
+  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
+#define TIMING_DEFINE_PRINT(t) static struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
+static long timing_ ## t ## _time; \
+static void timing_print_ ## t ( char * msg ) { \
   fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
 } \
-void timing_reset_ ## t () { \
+static void timing_reset_ ## t () { \
   timing_ ## t ## _time = 0; \
 }