Changeset 1130ffc in git


Ignore:
Timestamp:
Oct 25, 2012, 2:25:59 PM (12 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '648d28f488f6ff08f5607ff229b9ad9e4a5b93c2')
Children:
139f6f800b915490dfaa914ef7676d29a3236b92186df6b3fe891f605e0e3e7324333e7713165436
Parents:
becbea965e6c5de8e8ab195c7f480cabc295ac0cd91423947d67c2ab2eaf1aae4a61f9f2988e9510
Message:
Merge pull request #198 from mmklee/factory_clean_sw

Factory clean sw
Location:
factory
Files:
16 edited

Legend:

Unmodified
Added
Removed
  • factory/algext.cc

    rbecbea r1130ffc  
    1515
    1616#include "cf_assert.h"
     17#include "timing.h"
    1718
    1819#include "templates/ftmpl_functions.h"
     
    2930#include "NTLconvert.h"
    3031#endif
     32
     33TIMING_DEFINE_PRINT(alg_content_p)
     34TIMING_DEFINE_PRINT(alg_content)
     35TIMING_DEFINE_PRINT(alg_compress)
     36TIMING_DEFINE_PRINT(alg_termination)
     37TIMING_DEFINE_PRINT(alg_termination_p)
     38TIMING_DEFINE_PRINT(alg_reconstruction)
     39TIMING_DEFINE_PRINT(alg_newton_p)
     40TIMING_DEFINE_PRINT(alg_recursion_p)
     41TIMING_DEFINE_PRINT(alg_gcd_p)
     42TIMING_DEFINE_PRINT(alg_euclid_p)
    3143
    3244/// compressing two polynomials F and G, M is used for compressing,
     
    430442    return;
    431443  }
     444  TIMING_START (alg_compress)
    432445  CFMap MM,NN;
    433446  int lev= myCompress (F, G, MM, NN, topLevel);
     
    439452  CanonicalForm f=MM(F);
    440453  CanonicalForm g=MM(G);
     454  TIMING_END_AND_PRINT (alg_compress, "time to compress in alg gcd: ")
    441455  // here: f,g are compressed
    442456  // compute largest variable in f or g (least one is Variable(1))
     
    447461  if(mv == 1) // f,g univariate
    448462  {
     463    TIMING_START (alg_euclid_p)
    449464    tryEuclid(f,g,M,result,fail);
     465    TIMING_END_AND_PRINT (alg_euclid_p, "time for euclidean alg mod p: ")
    450466    if(fail)
    451467      return;
     
    453469    return;
    454470  }
     471  TIMING_START (alg_content_p)
    455472  // here: mv > 1
    456473  CanonicalForm cf = tryvcontent(f, Variable(2), M, fail); // cf is univariate poly in var(1)
     
    472489  if(fail)
    473490    return;
     491  TIMING_END_AND_PRINT (alg_content_p, "time for content in alg gcd mod p: ")
    474492  if(f.inCoeffDomain())
    475493  {
     
    495513  N = leadDeg(g, N);
    496514  CanonicalForm gamma;
     515  TIMING_START (alg_euclid_p)
    497516  tryEuclid( firstLC(f), firstLC(g), M, gamma, fail );
     517  TIMING_END_AND_PRINT (alg_euclid_p, "time for gcd of lcs in alg mod p: ")
    498518  if(fail)
    499519    return;
     
    517537    if(gamma_image.isZero()) // skip lc-bad points var(1)-alpha
    518538      continue;
     539    TIMING_START (alg_recursion_p)
    519540    tryBrownGCD( f(alpha, x), g(alpha, x), M, g_image, fail, false ); // recursive call with one var less
     541    TIMING_END_AND_PRINT (alg_recursion_p,
     542                         "time for recursive calls in alg gcd mod p: ")
    520543    if(fail)
    521544      return;
     
    541564      g_image *= gamma_image; // multiply by multiple of image lc(gcd)
    542565      g_image= reduce (g_image, M);
     566      TIMING_START (alg_newton_p)
    543567      gnew= tryNewtonInterp (alpha, g_image, m, gm, x, M, fail);
     568      TIMING_END_AND_PRINT (alg_newton_p,
     569                            "time for Newton interpolation in alg gcd mod p: ")
    544570      // gnew = gm mod m
    545571      // gnew = g_image mod var(1)-alpha
     
    550576      if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
    551577      {
     578        TIMING_START (alg_termination_p)
    552579        cf = tryvcontent(gnew, Variable(2), M, fail);
    553580        if(fail)
     
    569596          {
    570597            result = NN(reduce (c*g_image, M));
     598            TIMING_END_AND_PRINT (alg_termination_p,
     599                      "time for successful termination test in alg gcd mod p: ")
    571600            return;
    572601          }
    573602        }
     603        TIMING_END_AND_PRINT (alg_termination_p,
     604                    "time for unsuccessful termination test in alg gcd mod p: ")
    574605      }
    575606      gm = gnew;
     
    665696  f = F * bCommonDen(F);
    666697  g = G * bCommonDen(G);
     698  TIMING_START (alg_content)
    667699  CanonicalForm contf= myicontent (f);
    668700  CanonicalForm contg= myicontent (g);
     
    670702  g /= contg;
    671703  CanonicalForm gcdcfcg= myicontent (contf, contg);
     704  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
    672705  Variable a, b;
    673706  if(hasFirstAlgVar(f,a))
     
    727760    mipo /= mipo.lc();
    728761    // here: mipo is monic
     762    TIMING_START (alg_gcd_p)
    729763    tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
     764    TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
    730765    if( fail ) // mipo splits in char p
    731766      continue;
     
    756791        D = tmp;
    757792      On( SW_RATIONAL );
     793      TIMING_START (alg_reconstruction)
    758794      tmp = Farey( D, q ); // Farey
    759795      tmp *= bCommonDen (tmp);
     796      TIMING_END_AND_PRINT (alg_reconstruction,
     797                            "time for rational reconstruction in alg gcd: ")
    760798      setReduce(a,true); // reduce expressions modulo mipo
    761799      On( SW_RATIONAL ); // needed by fdivides
     
    764802      else
    765803        equal= true; // modular image did not add any new information
     804      TIMING_START (alg_termination)
    766805      if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
    767806      {
     
    769808        setReduce(a,true);
    770809        if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
     810        TIMING_END_AND_PRINT (alg_termination,
     811                            "time for successful termination test in alg gcd: ")
    771812        return tmp*gcdcfcg;
    772813      }
     814      TIMING_END_AND_PRINT (alg_termination,
     815                          "time for unsuccessful termination test in alg gcd: ")
    773816      Off( SW_RATIONAL );
    774817      setReduce(a,false); // do not reduce expressions modulo mipo
  • factory/cfNewtonPolygon.cc

    rbecbea r1130ffc  
    879879        if (isRat)
    880880          On (SW_RATIONAL);
    881         if (tmp == 1)
    882         {
    883           for (int i= 0; i < sizeOfNewtonPolygon; i++)
    884             delete [] newtonPolyg [i];
    885           delete [] newtonPolyg;
    886         }
     881        for (int i= 0; i < sizeOfNewtonPolygon; i++)
     882          delete [] newtonPolyg [i];
     883        delete [] newtonPolyg;
    887884        return (tmp==1);
    888885      }
  • factory/cf_gcd.cc

    rbecbea r1130ffc  
    33#include "config.h"
    44
     5#include "timing.h"
    56#include "cf_assert.h"
    67#include "debug.h"
     
    572573    Variable v = f.mvar();
    573574    Hi = power( LC( pi1, v ), delta );
     575    int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
     576
     577    if (!(pi.isUnivariate() && pi1.isUnivariate()))
     578    {
     579      if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
     580      {
     581        On (SW_USE_FF_MOD_GCD);
     582        C *= gcd (pi, pi1);
     583        Off (SW_USE_FF_MOD_GCD);
     584        return C;
     585      }
     586    }
     587
    574588    if ( (delta+1) % 2 )
    575589        bi = 1;
    576590    else
    577591        bi = -1;
    578     int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
    579     CanonicalForm oldPi= pi, oldPi1= pi1;
     592    CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
    580593    while ( degree( pi1, v ) > 0 )
    581594    {
     
    604617        {
    605618            delta = degree( pi, v ) - degree( pi1, v );
     619            powHi= power (Hi, delta-1);
    606620            if ( (delta+1) % 2 )
    607                 bi = LC( pi, v ) * power( Hi, delta );
     621                bi = LC( pi, v ) * powHi*Hi;
    608622            else
    609                 bi = -LC( pi, v ) * power( Hi, delta );
    610             Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
     623                bi = -LC( pi, v ) * powHi*Hi;
     624            Hi = power( LC( pi1, v ), delta ) / powHi;
     625            if (!(pi.isUnivariate() && pi1.isUnivariate()))
     626            {
     627              if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
     628              {
     629                On (SW_USE_FF_MOD_GCD);
     630                C *= gcd (oldPi, oldPi1);
     631                Off (SW_USE_FF_MOD_GCD);
     632                return C;
     633              }
     634            }
    611635        }
    612636    }
     
    11561180}
    11571181
     1182TIMING_DEFINE_PRINT(chinrem_termination)
     1183TIMING_DEFINE_PRINT(chinrem_recursion)
     1184TIMING_DEFINE_PRINT(chinrem_reconstruction)
     1185
    11581186CanonicalForm chinrem_gcd ( const CanonicalForm & FF, const CanonicalForm & GG )
    11591187{
     
    12231251    fp= mapinto (f);
    12241252    gp= mapinto (g);
     1253    TIMING_START (chinrem_recursion)
    12251254#ifdef HAVE_NTL
    12261255    if (size (fp)/maxNumVars > 500 && size (gp)/maxNumVars > 500)
     
    12371266    cogp= gp/Dp;
    12381267#endif
     1268    TIMING_END_AND_PRINT (chinrem_recursion,
     1269                          "time for gcd mod p in modular gcd: ");
    12391270    Dp /=Dp.lc();
    12401271    cofp /= lc (cofp);
     
    12871318    if ( i >= 0 )
    12881319    {
     1320      TIMING_START (chinrem_reconstruction);
    12891321      Dn= Farey(D,q);
    12901322      cofn= Farey(cof,q);
    12911323      cogn= Farey(cog,q);
     1324      TIMING_END_AND_PRINT (chinrem_reconstruction,
     1325                           "time for rational reconstruction in modular gcd: ");
    12921326      int is_rat= isOn (SW_RATIONAL);
    12931327      On (SW_RATIONAL);
     
    13031337        equal= true;
    13041338      //Dn /=vcontent(Dn,Variable(1));
     1339      TIMING_START (chinrem_termination);
    13051340      if ((terminationTest (f,g, cofn, cogn, Dn)) ||
    13061341          ((equal || q > b) && fdivides (Dn, f) && fdivides (Dn, g)))
    13071342      {
     1343        TIMING_END_AND_PRINT (chinrem_termination,
     1344                            "time for successful termination in modular gcd: ");
    13081345        //printf(" -> success\n");
    13091346        return Dn*gcdcfcg;
    13101347      }
     1348      TIMING_END_AND_PRINT (chinrem_termination,
     1349                          "time for unsuccessful termination in modular gcd: ");
    13111350      equal= false;
    13121351      //else: try more primes
  • factory/cf_gcd_smallp.cc

    rbecbea r1130ffc  
    4545TIMING_DEFINE_PRINT(gcd_recursion)
    4646TIMING_DEFINE_PRINT(newton_interpolation)
     47TIMING_DEFINE_PRINT(termination_test)
     48TIMING_DEFINE_PRINT(ez_p_compress)
     49TIMING_DEFINE_PRINT(ez_p_hensel_lift)
     50TIMING_DEFINE_PRINT(ez_p_eval)
     51TIMING_DEFINE_PRINT(ez_p_content)
    4752
    4853bool
     
    797802    if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
    798803    {
     804      TIMING_START (termination_test);
    799805      if (gcdlcAlcB.isOne())
    800806        cH= 1;
     
    831837          coF= N ((cA/gcdcAcB)*ppCoF);
    832838          coG= N ((cB/gcdcAcB)*ppCoG);
     839          TIMING_END_AND_PRINT (termination_test,
     840                                "time for successful termination test Fq: ");
    833841          return N(gcdcAcB*ppH);
    834842        }
     
    846854        }
    847855        coF= N ((cA/gcdcAcB)*ppCoF);
    848         coG= N ((cB/gcdcAcB)*ppCoG);;
     856        coG= N ((cB/gcdcAcB)*ppCoG);
     857        TIMING_END_AND_PRINT (termination_test,
     858                              "time for successful termination test Fq: ");
    849859        return N(gcdcAcB*ppH);
    850860      }
     861      TIMING_END_AND_PRINT (termination_test,
     862                            "time for unsuccessful termination test Fq: ");
    851863    }
    852864
     
    12371249    if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
    12381250    {
     1251      TIMING_START (termination_test);
    12391252      if (gcdlcAlcB.isOne())
    12401253        cH= 1;
     
    12701283          coG= N ((cB/gcdcAcB)*ppCoG);
    12711284          setCharacteristic (p, k, gf_name_buf);
     1285          TIMING_END_AND_PRINT (termination_test,
     1286                                "time for successful termination GF: ");
    12721287          return N(gcdcAcB*ppH);
    12731288        }
     
    12881303          coF= N ((cA/gcdcAcB)*ppCoF);
    12891304          coG= N ((cB/gcdcAcB)*ppCoG);
     1305          TIMING_END_AND_PRINT (termination_test,
     1306                                "time for successful termination GF: ");
    12901307          return N(gcdcAcB*ppH);
    12911308        }
    12921309      }
     1310      TIMING_END_AND_PRINT (termination_test,
     1311                            "time for unsuccessful termination GF: ");
    12931312    }
    12941313
     
    17441763    if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
    17451764    {
     1765      TIMING_START (termination_test);
    17461766      if (gcdlcAlcB.isOne())
    17471767        cH= 1;
     
    17691789        coF= N ((cA/gcdcAcB)*ppCoF);
    17701790        coG= N ((cB/gcdcAcB)*ppCoG);
     1791        TIMING_END_AND_PRINT (termination_test,
     1792                              "time for successful termination Fp: ");
    17711793        return N(gcdcAcB*ppH);
    17721794      }
     1795      TIMING_END_AND_PRINT (termination_test,
     1796                            "time for unsuccessful termination Fp: ");
    17731797    }
    17741798
     
    44504474  CFMap M,N;
    44514475  int smallestDegLev;
     4476  TIMING_START (ez_p_compress)
    44524477  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
    44534478
     
    44564481  F= M (F);
    44574482  G= M (G);
    4458 
     4483  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
     4484
     4485  TIMING_START (ez_p_content)
    44594486  f = content( F, x ); g = content( G, x );
    44604487  d = gcd( f, g );
    44614488  F /= f; G /= g;
     4489  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
    44624490
    44634491  if( F.isUnivariate() && G.isUnivariate() )
     
    45984626  while( !gcdfound )
    45994627  {
     4628    TIMING_START (ez_p_eval);
    46004629    if( !findeval_P( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
    46014630         maxeval/maxNumVars, t ))
     
    46204649      return N (d*result);
    46214650    }
     4651    TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
    46224652    delta = degree( Db );
    46234653    if( delta == 0 )
     
    46324662    {
    46334663      bt = b;
     4664      TIMING_START (ez_p_eval);
    46344665      if( !findeval_P(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
    46354666           maxeval/maxNumVars, t ))
     
    46544685        return N (d*result);
    46554686      }
     4687      TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
    46564688      int dd = degree( Dbt );
    46574689      if( dd == 0 )
     
    48074839      }
    48084840
     4841      TIMING_START (ez_p_hensel_lift);
    48094842      gcdfound= Hensel_P (B*lcD, DD, b, lcDD);
    4810 
    4811       if (gcdfound == -1)
    4812       {
    4813         Off (SW_USE_EZGCD_P);
    4814         result= gcd (F,G);
    4815         On (SW_USE_EZGCD_P);
    4816         if (passToGF)
    4817         {
    4818           CanonicalForm mipo= gf_mipo;
    4819           setCharacteristic (p);
    4820           Variable alpha= rootOf (mipo.mapinto());
    4821           result= GF2FalphaRep (result, alpha);
     4843      TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
     4844
     4845      if (gcdfound == -1) //things became dense
     4846      {
     4847        if (algExtension)
     4848        {
     4849          result= GCD_Fp_extension (F, G, a);
     4850          if (extOfExt)
     4851            result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
     4852          return N (d*result);
    48224853        }
    4823         if (k > 1)
    4824         {
    4825           result= GFMapDown (result, k);
    4826           setCharacteristic (p, k, gf_name);
     4854        if (CFFactory::gettype() == GaloisFieldDomain)
     4855        {
     4856          result= GCD_GF (F, G);
     4857          if (passToGF)
     4858          {
     4859            CanonicalForm mipo= gf_mipo;
     4860            setCharacteristic (p);
     4861            Variable alpha= rootOf (mipo.mapinto());
     4862            result= GF2FalphaRep (result, alpha);
     4863          }
     4864          if (k > 1)
     4865          {
     4866            result= GFMapDown (result, k);
     4867            setCharacteristic (p, k, gf_name);
     4868          }
     4869          return N (d*result);
    48274870        }
    4828         if (extOfExt)
    4829           result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
    4830         return N (d*result);
     4871        else
     4872          return N (d*GCD_small_p (F,G));
    48314873      }
    48324874
    48334875      if (gcdfound == 1)
    48344876      {
     4877        TIMING_START (termination_test);
    48354878        contcand= content (DD[2], Variable (1));
    48364879        cand = DD[2] / contcand;
     
    48394882        else
    48404883          gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
     4884        TIMING_END_AND_PRINT (termination_test,
     4885                              "time for termination test EZ_P: ");
    48414886
    48424887        if (passToGF && gcdfound)
  • factory/facAlgExt.cc

    rbecbea r1130ffc  
    2929#include "fac_sqrfree.h"
    3030
     31TIMING_DEFINE_PRINT(fac_alg_resultant)
     32TIMING_DEFINE_PRINT(fac_alg_norm)
     33TIMING_DEFINE_PRINT(fac_alg_factor_norm)
     34TIMING_DEFINE_PRINT(fac_alg_gcd)
     35TIMING_DEFINE_PRINT(fac_alg_sqrf)
     36TIMING_DEFINE_PRINT(fac_alg_factor_sqrf)
     37
    3138// squarefree part of F
    3239CanonicalForm
     
    5360  int degmipo= degree (mipo);
    5461  CanonicalForm norm;
     62  TIMING_START (fac_alg_resultant);
    5563  if (degg >= 8 || degmipo >= 8)
    5664    norm= resultantZ (g, mipo, x);
    5765  else
    5866    norm= resultant (g, mipo, x);
     67  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
    5968
    6069  i= 0;
     
    7281        g= F (y - i*alpha, y);
    7382        g *= bCommonDen (g);
     83        TIMING_START (fac_alg_resultant);
    7484        if (degg >= 8 || degmipo >= 8)
    7585          norm= resultantZ (g (x, alpha), mipo, x);
    7686        else
    7787          norm= resultant (g (x, alpha), mipo, x);
     88        TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant1: ");
    7889      }
    7990      else
     
    8192        g= F (y + i*alpha, y);
    8293        g *= bCommonDen (g);
     94        TIMING_START (fac_alg_resultant);
    8395        if (degg >= 8 || degmipo >= 8)
    8496          norm= resultantZ (g (x, alpha), mipo, x);
    8597        else
    8698          norm= resultant (g (x, alpha), mipo, x);
     99        TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant2: ");
    87100      }
    88101      if (degree (gcd (deriv (norm, y), norm)) <= 0)
     
    108121  CanonicalForm f= F*bCommonDen (F);
    109122  int shift;
     123  TIMING_START (fac_alg_norm);
    110124  CanonicalForm norm= sqrfNorm (f, alpha, shift);
     125  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
    111126  ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
     127  TIMING_START (fac_alg_factor_norm);
    112128  CFFList normFactors= factorize (norm);
     129  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
    113130  CFList factors;
    114131  if (normFactors.length() <= 2)
     
    125142  {
    126143    ASSERT (i.getItem().exp() == 1, "norm not squarefree");
     144    TIMING_START (fac_alg_gcd);
    127145    if (shift == 0)
    128146      factor= gcd (buf, i.getItem().factor());
     
    130148      factor= gcd (buf, i.getItem().factor() (f.mvar() + shift*alpha, f.mvar()));
    131149    buf /= factor;
     150    TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
    132151    factors.append (factor);
    133152  }
     
    149168  bool save_rat=!isOn (SW_RATIONAL);
    150169  On (SW_RATIONAL);
     170  TIMING_START (fac_alg_sqrf);
    151171  CFFList sqrf= sqrFreeZ (F);
     172  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
    152173  CFList factorsSqrf;
    153174  CFFList factors;
     
    158179  {
    159180    if (i.getItem().factor().inCoeffDomain()) continue;
     181    TIMING_START (fac_alg_factor_sqrf);
    160182    factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
     183    TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
     184                          "time to factor sqrf factors in Q(a)[x]: ");
    161185    for (j= factorsSqrf; j.hasItem(); j++)
    162186    {
  • factory/facBivar.cc

    rbecbea r1130ffc  
    1313#include "config.h"
    1414
    15 #include "assert.h"
     15#include "cf_assert.h"
    1616#include "debug.h"
    1717#include "timing.h"
     
    2828TIMING_DEFINE_PRINT(fac_bi_hensel_lift)
    2929TIMING_DEFINE_PRINT(fac_bi_factor_recombination)
     30TIMING_DEFINE_PRINT(fac_bi_evaluation)
     31TIMING_DEFINE_PRINT(fac_bi_shift_to_zero)
    3032
    3133// bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
     
    186188}
    187189
    188 CFList
    189 earlyFactorDetection0 (CanonicalForm& F, CFList& factors,int& adaptedLiftBound,
    190                       DegreePattern& degs, bool& success, int deg)
    191 {
    192   DegreePattern bufDegs1= degs;
    193   DegreePattern bufDegs2;
    194   CFList result;
    195   CFList T= factors;
    196   CanonicalForm buf= F;
    197   CanonicalForm LCBuf= LC (buf, Variable (1));
    198   CanonicalForm g, quot;
    199   CanonicalForm M= power (F.mvar(), deg);
    200   adaptedLiftBound= 0;
    201   int d= degree (F) + degree (LCBuf, F.mvar());
    202   for (CFListIterator i= factors; i.hasItem(); i++)
    203   {
    204     if (!bufDegs1.find (degree (i.getItem(), 1)))
    205       continue;
    206     else
    207     {
    208       g= i.getItem() (0, 1);
    209       g *= LCBuf;
    210       g= mod (g, M);
    211       if (fdivides (LC (g), LCBuf))
    212       {
    213         g= mulMod2 (i.getItem(), LCBuf, M);
    214         g /= content (g, Variable (1));
    215         if (fdivides (g, buf, quot))
    216         {
    217           result.append (g);
    218           buf= quot;
    219           d -= degree (g) + degree (LC (g, Variable (1)), F.mvar());
    220           LCBuf= LC (buf, Variable (1));
    221           T= Difference (T, CFList (i.getItem()));
    222 
    223           // compute new possible degree pattern
    224           bufDegs2= DegreePattern (T);
    225           bufDegs1.intersect (bufDegs2);
    226           bufDegs1.refine ();
    227           if (bufDegs1.getLength() <= 1)
    228           {
    229             result.append (buf);
    230             break;
    231           }
    232         }
    233       }
    234     }
    235   }
    236   adaptedLiftBound= d + 1;
    237   if (d < deg)
    238   {
    239     factors= T;
    240     degs= bufDegs1;
    241     F= buf;
    242     success= true;
    243   }
    244   if (bufDegs1.getLength() <= 1)
    245     degs= bufDegs1;
    246   return result;
    247 }
    248 
    249 
    250 CFList
    251 henselLiftAndEarly0 (CanonicalForm& A, bool& earlySuccess, CFList&
    252                     earlyFactors, DegreePattern& degs, int& liftBound,
    253                     const CFList& uniFactors, const CanonicalForm& eval)
    254 {
    255   int sizeOfLiftPre;
    256   int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
    257 
    258   Variable x= Variable (1);
    259   Variable y= Variable (2);
    260   CFArray Pi;
    261   CFList diophant;
    262   CFList bufUniFactors= uniFactors;
    263   bufUniFactors.insert (LC (A, x));
    264   CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
    265   earlySuccess= false;
    266   int newLiftBound= 0;
    267   int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
    268   if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
    269     henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);
    270   else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
    271   {
    272     henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
    273     earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
    274                                         degs, earlySuccess,
    275                                         smallFactorDeg);
    276     if (degs.getLength() > 1 && !earlySuccess &&
    277         smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
    278     {
    279       if (newLiftBound > liftPre[sizeOfLiftPre-1]+1)
    280       {
    281         bufUniFactors.insert (LC (A, x));
    282         henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
    283                             liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M);
    284         earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
    285                       degs, earlySuccess, liftPre[sizeOfLiftPre-1] + 1);
    286       }
    287     }
    288     else if (earlySuccess)
    289       liftBound= newLiftBound;
    290     int i= sizeOfLiftPre - 1;
    291     while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
    292     {
    293       if (newLiftBound > liftPre[i] + 1)
    294       {
    295         bufUniFactors.insert (LC (A, x));
    296         henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
    297                             liftPre[i-1] + 1, Pi, diophant, M);
    298         earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
    299                       degs, earlySuccess, liftPre[i-1] + 1);
    300       }
    301       else
    302       {
    303         liftBound= newLiftBound;
    304         break;
    305       }
    306       i--;
    307     }
    308     if (earlySuccess)
    309       liftBound= newLiftBound;
    310     //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
    311   }
    312   else
    313   {
    314     henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
    315     earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
    316                                         degs, earlySuccess,
    317                                         smallFactorDeg);
    318     int i= 1;
    319     while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
    320       i++;
    321     if (degs.getLength() > 1 && !earlySuccess)
    322     {
    323       bufUniFactors.insert (LC (A, x));
    324       henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
    325                           (degree (A, y)/4)*i + 4, Pi, diophant, M);
    326       earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
    327                     degs, earlySuccess, (degree (A, y)/4)*i + 4);
    328     }
    329     while (degs.getLength() > 1 && !earlySuccess && i < 4)
    330     {
    331       if (newLiftBound > (degree (A, y)/4)*i + 4)
    332       {
    333         bufUniFactors.insert (LC (A, x));
    334         henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
    335                             (degree (A, y)/4)*(i+1) + 4, Pi, diophant, M);
    336         earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
    337                       degs, earlySuccess, (degree (A, y)/4)*(i+1) + 4);
    338       }
    339       else
    340       {
    341         liftBound= newLiftBound;
    342         break;
    343       }
    344       i++;
    345     }
    346     if (earlySuccess)
    347       liftBound= newLiftBound;
    348   }
    349 
    350   return bufUniFactors;
    351 }
    352 
    353190CFList biFactorize (const CanonicalForm& F, const Variable& v)
    354191{
     
    499336  {
    500337    bufAeval= A;
     338    TIMING_START (fac_bi_evaluation);
    501339    bufAeval= evalPoint (A, bufEvaluation);
     340    TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
    502341
    503342    bufAeval2= buf;
     343    TIMING_START (fac_bi_evaluation);
    504344    bufAeval2= evalPoint (buf, bufEvaluation2);
     345    TIMING_END_AND_PRINT (fac_bi_evaluation,
     346                          "time for eval point over Q in y: ");
    505347
    506348    // univariate factorization
    507     TIMING_START (uni_factorize);
    508 
     349    TIMING_START (fac_uni_factorizer);
    509350    if (extension)
    510351      bufUniFactors= conv (factorize (bufAeval, v));
    511352    else
    512353      bufUniFactors= conv (factorize (bufAeval, true));
    513     TIMING_END_AND_PRINT (uni_factorize,
    514                           "time for univariate factorization: ");
     354    TIMING_END_AND_PRINT (fac_uni_factorizer,
     355                          "time for univariate factorization over Q: ");
    515356    DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
    516357              (prod (bufUniFactors) == bufAeval));
    517358
    518     TIMING_START (uni_factorize);
     359    TIMING_START (fac_uni_factorizer);
    519360    if (extension)
    520361      bufUniFactors2= conv (factorize (bufAeval2, v));
    521362    else
    522363      bufUniFactors2= conv (factorize (bufAeval2, true));
    523     TIMING_END_AND_PRINT (uni_factorize,
    524                           "time for univariate factorization in y: ");
     364    TIMING_END_AND_PRINT (fac_uni_factorizer,
     365                          "time for univariate factorization in y over Q: ");
    525366    DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
    526367              (prod (bufUniFactors2) == bufAeval2));
     
    709550              (A, earlySuccess, earlyFactors, degs, liftBound,
    710551               uniFactors, dummy, evaluation, b);
    711   TIMING_END_AND_PRINT (fac_bi_hensel_lift, "time for hensel lifting: ");
     552  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
     553                        "time for bivariate hensel lifting over Q: ");
    712554  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    713555
     
    728570  Off (SW_RATIONAL);
    729571
     572  TIMING_START (fac_bi_factor_recombination);
    730573  factors= factorRecombination (uniFactors, A, MODl, degs, 1,
    731574                                uniFactors.length()/2, b);
     575  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
     576                        "time for bivariate factor recombination over Q: ");
    732577
    733578  On (SW_RATIONAL);
  • factory/facBivar.h

    rbecbea r1130ffc  
    1414#define FAC_BIVAR_H
    1515
    16 #include <config.h>
    17 
    18 #include "assert.h"
     16#include "config.h"
     17
     18#include "cf_assert.h"
     19#include "timing.h"
    1920
    2021#include "facFqBivarUtil.h"
     
    2627#include "algext.h"
    2728#include "fac_util.h"
     29
     30TIMING_DEFINE_PRINT(fac_bi_sqrf)
     31TIMING_DEFINE_PRINT(fac_bi_factor_sqrf)
    2832
    2933/// @return @a biFactorize returns a list of factors of F. If F is not monic
     
    196200  vec_ZZ S;
    197201  F= compress (F, M, S);
     202  TIMING_START (fac_bi_sqrf);
    198203  CFFList sqrfFactors= sqrFree (F);
     204  TIMING_END_AND_PRINT (fac_bi_sqrf,
     205                       "time for bivariate sqrf factors over Q: ");
    199206  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
    200207  {
     208    TIMING_START (fac_bi_factor_sqrf);
    201209    CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
     210    TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
     211                          "time to factor bivariate sqrf factors over Q: ");
    202212    for (CFListIterator j= tmp; j.hasItem(); j++)
    203213    {
  • factory/facFactorize.cc

    rbecbea r1130ffc  
    2929#include "facSparseHensel.h"
    3030
    31 TIMING_DEFINE_PRINT(fac_bi_factorize)
     31TIMING_DEFINE_PRINT(fac_bi_factorizer)
    3232TIMING_DEFINE_PRINT(fac_hensel_lift)
    3333TIMING_DEFINE_PRINT(fac_factor_recombination)
     34TIMING_DEFINE_PRINT(fac_shift_to_zero)
     35TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
     36TIMING_DEFINE_PRINT(fac_evaluation)
     37TIMING_DEFINE_PRINT(fac_recover_factors)
     38TIMING_DEFINE_PRINT(fac_preprocess_and_content)
     39TIMING_DEFINE_PRINT(fac_bifactor_total)
     40TIMING_DEFINE_PRINT(fac_luckswang)
     41TIMING_DEFINE_PRINT(fac_lcheuristic)
     42TIMING_DEFINE_PRINT(fac_cleardenom)
     43TIMING_DEFINE_PRINT(fac_content)
     44TIMING_DEFINE_PRINT(fac_compress)
    3445
    3546#ifdef HAVE_NTL
     
    149160      Aeval [j]= factors;
    150161    }
    151     else if (!Aeval[j].isEmpty())
    152       Aeval[j]=CFList();
    153162  }
    154163}
    155 
    156 int
    157 testFactors (const CanonicalForm& G, const CFList& uniFactors,
    158              CanonicalForm& sqrfPartF, CFList& factors,
    159              CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
    160              const CFArray& evalPoint)
    161 {
    162   CanonicalForm tmp;
    163   CFListIterator j;
    164   for (CFListIterator i= uniFactors; i.hasItem(); i++)
    165   {
    166     tmp= i.getItem();
    167     if (i.hasItem())
    168       i++;
    169     else
    170       break;
    171     for (j= i; j.hasItem(); j++)
    172     {
    173       if (tmp == j.getItem())
    174         return 0;
    175     }
    176   }
    177 
    178   CanonicalForm F= G;
    179   CFFList sqrfFactorization= sqrFree (F);
    180 
    181   sqrfPartF= 1;
    182   for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
    183     sqrfPartF *= i.getItem().factor();
    184 
    185   evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
    186 
    187   CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
    188 
    189   if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
    190     return 0;
    191 
    192   CFFList sqrfFactors;
    193   CFList tmp2;
    194   int k= 0;
    195   factors= uniFactors;
    196   CFFListIterator iter;
    197   for (CFListIterator i= factors; i.hasItem(); i++, k++)
    198   {
    199     tmp= 1;
    200     sqrfFactors= sqrFree (i.getItem());
    201 
    202     for (iter= sqrfFactors; iter.hasItem(); iter++)
    203     {
    204       tmp2.append (iter.getItem().factor());
    205       tmp *= iter.getItem().factor();
    206     }
    207     i.getItem()= tmp/Lc(tmp);
    208     bufSqrfFactors [k]= sqrfFactors;
    209   }
    210 
    211   for (int i= 0; i < factors.length() - 1; i++)
    212   {
    213     for (int k= i + 1; k < factors.length(); k++)
    214     {
    215       gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
    216     }
    217   }
    218 
    219   factors= CFList();
    220   for (int i= 0; i < uniFactors.length(); i++)
    221   {
    222     if (i == 0)
    223     {
    224       for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
    225       {
    226         if (iter.getItem().factor().inCoeffDomain())
    227           continue;
    228         iter.getItem()= CFFactor (iter.getItem().factor()/
    229                                   Lc (iter.getItem().factor()),
    230                                   iter.getItem().exp());
    231         factors.append (iter.getItem().factor());
    232       }
    233     }
    234     else
    235     {
    236       for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
    237       {
    238         if (iter.getItem().factor().inCoeffDomain())
    239           continue;
    240         iter.getItem()= CFFactor (iter.getItem().factor()/
    241                                Lc (iter.getItem().factor()),
    242                                iter.getItem().exp());
    243         if (!find (factors, iter.getItem().factor()))
    244           factors.append (iter.getItem().factor());
    245       }
    246     }
    247   }
    248 
    249   test= prod (factors);
    250   tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
    251   if (test/Lc (test) != tmp/Lc (tmp))
    252     return 0;
    253   else
    254     return 1;
    255 }
    256 
    257 CFList
    258 precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
    259                         const CFList& evaluation,CFList*& differentSecondVarLCs,
    260                         int length, Variable& y
    261                        )
    262 {
    263   y= Variable (1);
    264   if (LCF.inCoeffDomain())
    265   {
    266     CFList result;
    267     for (int i= 1; i <= LCFFactors.length() + 1; i++)
    268       result.append (1);
    269     return result;
    270   }
    271 
    272   CFMap N, M;
    273   CFArray dummy= CFArray (2);
    274   dummy [0]= LCF;
    275   dummy [1]= Variable (2);
    276   compress (dummy, M, N);
    277   CanonicalForm F= M (LCF);
    278   if (LCF.isUnivariate())
    279   {
    280     CFList result;
    281     int LCFLevel= LCF.level();
    282     bool found= false;
    283     if (LCFLevel == 2)
    284     {
    285     //bivariate leading coefficients are already the true leading coefficients
    286       result= LCFFactors;
    287       found= true;
    288     }
    289     else
    290     {
    291       CFListIterator j;
    292       for (int i= 0; i < length; i++)
    293       {
    294         for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
    295         {
    296           if (j.getItem().level() == LCFLevel)
    297           {
    298             found= true;
    299             break;
    300           }
    301         }
    302         if (found)
    303         {
    304           result= differentSecondVarLCs [i];
    305           break;
    306         }
    307       }
    308       if (!found)
    309         result= LCFFactors;
    310     }
    311     if (found)
    312       result.insert (Lc (LCF));
    313     else
    314     {
    315       for (CFListIterator i= result; i.hasItem(); i++)
    316         i.getItem() *= LCF;
    317       result.insert (LCF);
    318     }
    319     return result;
    320   }
    321 
    322   CFList factors= LCFFactors;
    323 
    324   for (CFListIterator i= factors; i.hasItem(); i++)
    325     i.getItem()= M (i.getItem());
    326 
    327   CanonicalForm sqrfPartF;
    328   CFFList * bufSqrfFactors= new CFFList [factors.length()];
    329   CFList evalSqrfPartF, bufFactors;
    330   CFArray evalPoint= CFArray (evaluation.length() - 1);
    331   CFArray buf= CFArray (evaluation.length());
    332   CFArray swap= CFArray (evaluation.length());
    333   CFListIterator iter= evaluation;
    334   CanonicalForm vars=getVars (LCF)*Variable (2);
    335   for (int i= evaluation.length() +1; i > 1; i--, iter++)
    336   {
    337     buf[i-2]=iter.getItem();
    338     if (degree (vars, i) > 0)
    339       swap[M(Variable (i)).level()-1]=buf[i-2];
    340   }
    341   buf= swap;
    342   for (int i= 0; i < evaluation.length() - 1; i++)
    343     evalPoint[i]= buf[i+1];
    344 
    345   //TODO sqrfPartF einmal berechnen nicht stÀndig
    346   int pass= testFactors (F, factors, sqrfPartF,
    347                          bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
    348 
    349   bool foundDifferent= false;
    350   Variable z;
    351   Variable x= y;
    352   int j= 0;
    353   if (!pass)
    354   {
    355     int lev= 0;
    356     CanonicalForm bufF;
    357     CFList bufBufFactors;
    358     for (int i= 0; i < length; i++)
    359     {
    360       if (!differentSecondVarLCs [i].isEmpty())
    361       {
    362         bool allConstant= true;
    363         for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
    364         {
    365           if (!iter.getItem().inCoeffDomain())
    366           {
    367             allConstant= false;
    368             y= Variable (iter.getItem().level());
    369             lev= M(y).level();
    370           }
    371         }
    372         if (allConstant)
    373           continue;
    374 
    375         bufFactors= differentSecondVarLCs [i];
    376         for (iter= bufFactors; iter.hasItem(); iter++)
    377           iter.getItem()= swapvar (iter.getItem(), x, y);
    378         bufF= F;
    379         z= Variable (lev);
    380         bufF= swapvar (bufF, x, z);
    381         bufBufFactors= bufFactors;
    382         evalPoint= CFArray (evaluation.length() - 1);
    383         for (int k= 0; k < evaluation.length()-1; k++)
    384         {
    385           if (N (Variable (k+1)).level() != y.level())
    386             evalPoint[k]= buf[k+1];
    387           else
    388             evalPoint[k]= buf[0];
    389         }
    390         pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
    391                            bufSqrfFactors, evalSqrfPartF, evalPoint);
    392         if (pass)
    393         {
    394           foundDifferent= true;
    395           F= bufF;
    396           CFList l= factors;
    397           for (iter= l; iter.hasItem(); iter++)
    398             iter.getItem()= swapvar (iter.getItem(), x, y);
    399           differentSecondVarLCs [i]= l;
    400           j= i;
    401           break;
    402         }
    403         if (!pass && i == length - 1)
    404         {
    405           CFList result;
    406           result.append (LCF);
    407           for (int j= 1; j <= factors.length(); j++)
    408             result.append (1);
    409           result= distributeContent (result, differentSecondVarLCs, length);
    410           if (!result.getFirst().inCoeffDomain())
    411           {
    412             CFListIterator iter= result;
    413             CanonicalForm tmp= iter.getItem();
    414             iter++;
    415             for (; iter.hasItem(); iter++)
    416               iter.getItem() *= tmp;
    417           }
    418 
    419           y= Variable (1);
    420           delete [] bufSqrfFactors;
    421           return result;
    422         }
    423       }
    424     }
    425   }
    426   if (!pass)
    427   {
    428     CFList result;
    429     result.append (LCF);
    430     for (int j= 1; j <= factors.length(); j++)
    431       result.append (LCF);
    432     y= Variable (1);
    433     delete [] bufSqrfFactors;
    434     return result;
    435   }
    436   else
    437     factors= bufFactors;
    438 
    439 
    440   bufFactors= factors;
    441 
    442   CFMap MM, NN;
    443   dummy [0]= sqrfPartF;
    444   dummy [1]= 1;
    445   compress (dummy, MM, NN);
    446   sqrfPartF= MM (sqrfPartF);
    447   CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
    448   for (CFListIterator iter= factors; iter.hasItem(); iter++)
    449     iter.getItem()= MM (iter.getItem());
    450 
    451   CFList evaluation2;
    452   for (int i= 2; i <= varsSqrfPartF.level(); i++)
    453     evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
    454 
    455   CFList interMedResult;
    456   CanonicalForm oldSqrfPartF= sqrfPartF;
    457   sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
    458   if (factors.length() > 1)
    459   {
    460     CanonicalForm LC1= LC (oldSqrfPartF, 1);
    461     CFList leadingCoeffs;
    462     for (int i= 0; i < factors.length(); i++)
    463       leadingCoeffs.append (LC1);
    464 
    465     CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
    466     CFList oldFactors= factors;
    467     for (CFListIterator i= oldFactors; i.hasItem(); i++)
    468       i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
    469 
    470     bool success= false;
    471     CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
    472     CFList heuResult;
    473     if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
    474         LucksWangSparseHeuristic (oldSqrfPartFPowLC,
    475                                   oldFactors, 2, leadingCoeffs, heuResult))
    476     {
    477       interMedResult= recoverFactors (oldSqrfPartF, heuResult);
    478       if (oldFactors.length() == interMedResult.length())
    479         success= true;
    480     }
    481     if (!success)
    482     {
    483       LC1= LC (evalSqrfPartF.getFirst(), 1);
    484 
    485       CFArray leadingCoeffs= CFArray (factors.length());
    486       for (int i= 0; i < factors.length(); i++)
    487         leadingCoeffs[i]= LC1;
    488 
    489       for (CFListIterator i= factors; i.hasItem(); i++)
    490         i.getItem() *= LC1 (0,2)/Lc (i.getItem());
    491       factors.insert (1);
    492 
    493       CanonicalForm
    494       newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
    495 
    496       int liftBound= degree (newSqrfPartF,2) + 1;
    497 
    498       CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
    499       CFArray Pi;
    500       CFList diophant;
    501       nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
    502                             leadingCoeffs, false);
    503 
    504       if (sqrfPartF.level() > 2)
    505       {
    506         int* liftBounds= new int [sqrfPartF.level() - 1];
    507         liftBounds [0]= liftBound;
    508         bool noOneToOne= false;
    509         CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
    510         LC1= LC (evalSqrfPartF.getLast(), 1);
    511         CFList LCs;
    512         for (int i= 0; i < factors.length(); i++)
    513           LCs.append (LC1);
    514         leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
    515         for (int i= sqrfPartF.level() - 1; i > 2; i--)
    516         {
    517           for (CFListIterator j= LCs; j.hasItem(); j++)
    518             j.getItem()= j.getItem() (0, i + 1);
    519           leadingCoeffs2 [i - 3]= LCs;
    520         }
    521         sqrfPartF *= power (LC1, factors.length()-1);
    522 
    523         int liftBoundsLength= sqrfPartF.level() - 1;
    524         for (int i= 1; i < liftBoundsLength; i++)
    525           liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
    526         evalSqrfPartF= evaluateAtZero (sqrfPartF);
    527         evalSqrfPartF.removeFirst();
    528         factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
    529                  diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
    530         delete [] leadingCoeffs2;
    531         delete [] liftBounds;
    532       }
    533       for (CFListIterator iter= factors; iter.hasItem(); iter++)
    534         iter.getItem()= reverseShift (iter.getItem(), evaluation2);
    535 
    536       interMedResult=
    537       recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
    538                       factors);
    539     }
    540   }
    541   else
    542   {
    543     CanonicalForm contF=content (oldSqrfPartF,1);
    544     factors= CFList (oldSqrfPartF/contF);
    545     interMedResult= recoverFactors (oldSqrfPartF, factors);
    546   }
    547 
    548   for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
    549     iter.getItem()= NN (iter.getItem());
    550 
    551   CFList result;
    552   CFFListIterator k;
    553   CanonicalForm tmp;
    554   for (int i= 0; i < LCFFactors.length(); i++)
    555   {
    556     tmp= 1;
    557     for (k= bufSqrfFactors[i]; k.hasItem(); k++)
    558     {
    559       int pos= findItem (bufFactors, k.getItem().factor());
    560       if (pos)
    561         tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
    562     }
    563     result.append (tmp);
    564   }
    565 
    566   for (CFListIterator i= result; i.hasItem(); i++)
    567   {
    568     F /= i.getItem();
    569     if (foundDifferent)
    570       i.getItem()= swapvar (i.getItem(), x, z);
    571     i.getItem()= N (i.getItem());
    572   }
    573 
    574   if (foundDifferent)
    575   {
    576     CFList l= differentSecondVarLCs [j];
    577     for (CFListIterator i= l; i.hasItem(); i++)
    578       i.getItem()= swapvar (i.getItem(), y, z);
    579     differentSecondVarLCs [j]= l;
    580     F= swapvar (F, x, z);
    581   }
    582 
    583   result.insert (N (F));
    584 
    585   result= distributeContent (result, differentSecondVarLCs, length);
    586 
    587   if (!result.getFirst().inCoeffDomain())
    588   {
    589     CFListIterator i= result;
    590     CanonicalForm tmp;
    591     if (foundDifferent)
    592       i.getItem()= swapvar (i.getItem(), Variable (2), y);
    593 
    594     tmp= i.getItem();
    595 
    596     i++;
    597     for (; i.hasItem(); i++)
    598     {
    599       if (foundDifferent)
    600         i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
    601       else
    602         i.getItem() *= tmp;
    603     }
    604   }
    605   else
    606     y= Variable (1);
    607 
    608   delete [] bufSqrfFactors;
    609 
    610   return result;
    611 }
    612 
    613164
    614165CFList
     
    618169    return CFList (F);
    619170
     171  TIMING_START (fac_preprocess_and_content);
    620172  // compress and find main Variable
    621173  CFMap N;
     174  TIMING_START (fac_compress)
    622175  CanonicalForm A= myCompress (F, N);
     176  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
    623177
    624178  //univariate case
     
    646200
    647201  // remove content
     202  TIMING_START (fac_content);
    648203  CFList contentAi;
    649204  CanonicalForm lcmCont= lcmContent (A, contentAi);
    650205  A /= lcmCont;
     206  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
    651207
    652208  // trivial after content removal
     
    674230
    675231  // factorize content
     232  TIMING_START (fac_content);
    676233  contentAFactors= multiFactorize (lcmCont, v);
     234  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
    677235
    678236  // univariate after content removal
     
    690248
    691249  A *= bCommonDen (A);
    692   // check main variable
    693250  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
    694251  int factorNums= 1;
    695   CanonicalForm bivarEval;
    696252  CFList biFactors, bufBiFactors;
    697253  CanonicalForm evalPoly;
     
    702258  int differentSecondVar= 0;
    703259  CanonicalForm bufA;
     260  TIMING_END_AND_PRINT (fac_preprocess_and_content,
     261                       "time to preprocess poly and extract content over Q: ");
     262
    704263  // several bivariate factorizations
     264  TIMING_START (fac_bifactor_total);
    705265  REvaluation E (2, A.level(), IntRandom (25));
    706266  for (int i= 0; i < factorNums; i++)
     
    709269    bufA= A;
    710270    bufAeval= CFList();
     271    TIMING_START (fac_evaluation);
    711272    bufEvaluation= evalPoints (bufA, bufAeval, E);
     273    TIMING_END_AND_PRINT (fac_evaluation,
     274                          "time to find evaluation point over Q: ");
    712275    E.nextpoint();
    713276    evalPoly= 0;
    714277
    715     bivarEval= bufEvaluation.getLast();
    716 
     278    TIMING_START (fac_evaluation);
    717279    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
     280    TIMING_END_AND_PRINT (fac_evaluation,
     281                          "time to eval wrt diff second vars over Q: ");
    718282
    719283    for (int j= 0; j < lengthAeval2; j++)
     
    725289    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
    726290
    727     TIMING_START (fac_bi_factorize);
     291    TIMING_START (fac_bi_factorizer);
    728292    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
    729     TIMING_END_AND_PRINT (fac_bi_factorize,
     293    TIMING_END_AND_PRINT (fac_bi_factorizer,
    730294                          "time for bivariate factorization: ");
    731295    bufBiFactors.removeFirst();
     
    779343  int minFactorsLength;
    780344  bool irred= false;
     345  TIMING_START (fac_bi_factorizer);
    781346  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
    782 
     347  TIMING_END_AND_PRINT (fac_bi_factorizer,
     348             "time for bivariate factorization wrt diff second vars over Q: ");
     349
     350  TIMING_END_AND_PRINT (fac_bifactor_total,
     351                        "total time for eval and bivar factors over Q: ");
    783352  if (irred)
    784353  {
     
    839408
    840409  Variable w;
    841   CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
     410  TIMING_START (fac_precompute_leadcoeff);
     411  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
    842412                                          evaluation, Aeval2, lengthAeval2, w);
    843413
     
    940510    }
    941511  }
     512  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
     513                       "time to precompute LC over Q: ");
     514
     515  TIMING_START (fac_luckswang);
    942516  CFList bufFactors= CFList();
    943517  bool LCheuristic= false;
     
    962536      delete [] index;
    963537      delete [] Aeval2;
     538      TIMING_END_AND_PRINT (fac_luckswang,
     539                            "time for successful LucksWang over Q: ");
    964540      return factors;
    965541    }
     
    1300876    delete [] index;
    1301877  }
     878  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
     879
     880  TIMING_START (fac_lcheuristic);
    1302881  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
    1303882      && fdivides (getVars (LCmultiplier), testVars))
     
    14491028    }
    14501029  }
     1030  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
    14511031
    14521032tryAgainWithoutHeu:
    14531033  //shifting to zero
     1034  TIMING_START (fac_shift_to_zero);
     1035  CanonicalForm denA= bCommonDen (A);
     1036  A *= denA;
    14541037  A= shift2Zero (A, Aeval, evaluation);
     1038  A /= denA;
    14551039
    14561040  for (iter= biFactors; iter.hasItem(); iter++)
     
    14701054    }
    14711055  }
     1056  TIMING_END_AND_PRINT (fac_shift_to_zero,
     1057                        "time to shift evaluation point to zero: ");
    14721058
    14731059  CFArray Pi;
     
    14811067  bool noOneToOne= false;
    14821068
     1069  TIMING_START (fac_cleardenom);
    14831070  CFList commonDenominators;
    14841071  for (iter=biFactors; iter.hasItem(); iter++)
     
    14991086  for (iter= Aeval; iter.hasItem(); iter++)
    15001087  {
    1501     tmp2= bCommonDen (iter.getItem());
     1088    tmp2= bCommonDen (iter.getItem()/denA);
    15021089    Off (SW_RATIONAL);
    15031090    tmp3= lcm (tmp2,tmp3);
     
    15111098
    15121099  for (iter= Aeval; iter.hasItem(); iter++)
    1513     iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
     1100    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
    15141101
    15151102  for (int i= 0; i < lengthAeval2; i++)
     
    15191106      iter.getItem() *= iter2.getItem()*multiplier;
    15201107  }
    1521 
    1522 
     1108  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
     1109
     1110  TIMING_START (fac_hensel_lift);
    15231111  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
    15241112                               Pi, liftBounds, liftBoundsLength, noOneToOne);
     1113  TIMING_END_AND_PRINT (fac_hensel_lift,
     1114                        "time for non monic hensel lifting over Q: ");
    15251115
    15261116  if (!noOneToOne)
     
    15281118    int check= factors.length();
    15291119    A= oldA;
     1120    TIMING_START (fac_recover_factors);
    15301121    factors= recoverFactors (A, factors, evaluation);
     1122    TIMING_END_AND_PRINT (fac_recover_factors,
     1123                          "time to recover factors over Q: ");
    15311124    if (check != factors.length())
    15321125      noOneToOne= true;
  • factory/facFactorize.h

    rbecbea r1130ffc  
    1414#define FAC_FACTORIZE_H
    1515
    16 // #include "config.h"
     16#include "config.h"
     17#include "timing.h"
    1718
    1819#include "facBivar.h"
    1920#include "facFqBivarUtil.h"
     21
     22TIMING_DEFINE_PRINT (fac_squarefree)
     23TIMING_DEFINE_PRINT (fac_factor_squarefree)
    2024
    2125/// Factorization over Q (a)
     
    120124
    121125  CFFList result;
     126  TIMING_START (fac_squarefree);
    122127  CFFList sqrfFactors= sqrFree (F);
     128  TIMING_END_AND_PRINT (fac_squarefree,
     129                        "time for squarefree factorization over Q: ");
     130
     131  CFList tmp;
    123132  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
    124133  {
    125     CFList tmp= ratSqrfFactorize (i.getItem().factor(), v);
     134    TIMING_START (fac_factor_squarefree);
     135    tmp= ratSqrfFactorize (i.getItem().factor(), v);
     136    TIMING_END_AND_PRINT (fac_factor_squarefree,
     137                          "time to factorize sqrfree factor over Q: ");
    126138    for (CFListIterator j= tmp; j.hasItem(); j++)
    127139    {
  • factory/facFqBivar.cc

    rbecbea r1130ffc  
    4646TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift)
    4747TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination)
     48TIMING_DEFINE_PRINT(fac_fq_bi_evaluation)
     49TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero)
    4850
    4951CanonicalForm prodMod0 (const CFList& L, const CanonicalForm& M, const modpk& b)
     
    60826084  {
    60836085    bufAeval= A;
     6086    TIMING_START (fac_fq_bi_evaluation);
    60846087    bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
     6088    TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
    60856089    if (!derivXZero && !fail2 && !symmetric)
    60866090    {
     
    60916095      }
    60926096      bufAeval2= buf;
     6097      TIMING_START (fac_fq_bi_evaluation);
    60936098      bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
     6099      TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
     6100                            "time to find eval point wrt y: ");
    60946101    }
    60956102    // first try to change main variable if there is no valid evaluation point
     
    61326139    bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
    61336140    TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
    6134                           "time for univariate factorization: ");
     6141                          "time for univariate factorization over Fq: ");
    61356142    DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
    61366143              (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
     
    61416148      bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
    61426149      TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
    6143                             "time for univariate factorization in y: ");
     6150                            "time for univariate factorization in y over Fq: ");
    61446151      DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
    61456152                (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
     
    62916298  }
    62926299
     6300  TIMING_START (fac_fq_bi_shift_to_zero);
    62936301  A= A (y + evaluation, y);
     6302  TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
     6303                        "time to shift eval to zero: ");
    62946304
    62956305  int degMipo= 1;
     
    63076317               (A, earlySuccess, earlyFactors, degs, liftBound,
    63086318                uniFactors, info, evaluation);
    6309     TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
     6319    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
     6320                          "time for bivariate hensel lifting over Fq: ");
    63106321    DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    63116322
    63126323    CanonicalForm MODl= power (y, liftBound);
    63136324
     6325    TIMING_START (fac_fq_bi_factor_recombination);
    63146326    if (extension)
    63156327      factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
     
    63186330      factors= factorRecombination (uniFactors, A, MODl, degs, 1,
    63196331                                    uniFactors.length()/2);
     6332    TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
     6333                          "time for naive bivariate factor recombi over Fq: ");
    63206334
    63216335    if (earlySuccess)
     
    63466360      factors= Union (lll, factors);
    63476361    }
    6348     TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
     6362    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
     6363                          "time to bivar lift and LLL recombi over Fq: ");
    63496364    DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    63506365  }
     
    63576372               (A, earlySuccess, earlyFactors, degs, liftBound,
    63586373                uniFactors, info, evaluation);
    6359     TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
     6374    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
     6375                          "time for bivar hensel lifting over Fq: ");
    63606376    DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    63616377
     
    63636379    if (!extension)
    63646380    {
     6381      TIMING_START (fac_fq_bi_factor_recombination);
    63656382      factors= factorRecombination (uniFactors, A, MODl, degs, 1, 3);
     6383      TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
     6384                            "time for small subset naive recombi over Fq: ");
    63666385
    63676386      int oldUniFactorsLength= uniFactors.length();
     
    63696388      {
    63706389        CFList tmp;
     6390        TIMING_START (fac_fq_bi_hensel_lift);
    63716391        if (alpha.level() == 1)
    63726392          tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
     
    63846404                                   );
    63856405        }
     6406        TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
     6407                              "time to increase precision: ");
    63866408        factors= Union (factors, tmp);
    63876409        if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
  • factory/facFqBivar.h

    rbecbea r1130ffc  
    1515#define FAC_FQ_BIVAR_H
    1616
    17 // #include "config.h"
    18 
     17 #include "config.h"
     18
     19#include "timing.h"
    1920#include "cf_assert.h"
    2021
     
    2627#include "cf_map.h"
    2728#include "cfNewtonPolygon.h"
     29
     30TIMING_DEFINE_PRINT(fac_fq_bi_sqrf)
     31TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf)
    2832
    2933static const double log2exp= 1.442695041;
     
    273277  F= compress (F, M, S);
    274278
     279  TIMING_START (fac_fq_bi_sqrf);
    275280  CFFList sqrf= FpSqrf (F, false);
     281  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
     282                       "time for bivariate sqrf factors over Fp: ");
    276283  CFList bufResult;
    277284  sqrf.removeFirst();
     
    279286  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
    280287  {
     288    TIMING_START (fac_fq_bi_factor_sqrf);
    281289    bufResult= biFactorize (iter.getItem().factor(), info);
     290    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
     291                          "time to factor bivariate sqrf factors over Fp: ");
    282292    for (i= bufResult; i.hasItem(); i++)
    283293      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
     
    374384  F= compress (F, M, S);
    375385
     386  TIMING_START (fac_fq_bi_sqrf);
    376387  CFFList sqrf= FqSqrf (F, alpha, false);
     388  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
     389                       "time for bivariate sqrf factors over Fq: ");
    377390  CFList bufResult;
    378391  sqrf.removeFirst();
     
    380393  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
    381394  {
     395    TIMING_START (fac_fq_bi_factor_sqrf);
    382396    bufResult= biFactorize (iter.getItem().factor(), info);
     397    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
     398                          "time to factor bivariate sqrf factors over Fq: ");
    383399    for (i= bufResult; i.hasItem(); i++)
    384400      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
     
    476492  F= compress (F, M, S);
    477493
     494  TIMING_START (fac_fq_bi_sqrf);
    478495  CFFList sqrf= GFSqrf (F, false);
     496  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
     497                       "time for bivariate sqrf factors over GF: ");
    479498  CFList bufResult;
    480499  sqrf.removeFirst();
     
    482501  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
    483502  {
     503    TIMING_START (fac_fq_bi_factor_sqrf);
    484504    bufResult= biFactorize (iter.getItem().factor(), info);
     505    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
     506                          "time to factor bivariate sqrf factors over GF: ");
    485507    for (i= bufResult; i.hasItem(); i++)
    486508      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
  • factory/facFqFactorize.cc

    rbecbea r1130ffc  
    3838TIMING_DEFINE_PRINT(fac_fq_hensel_lift)
    3939TIMING_DEFINE_PRINT(fac_fq_factor_recombination)
     40TIMING_DEFINE_PRINT(fac_fq_shift_to_zero)
     41TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff)
     42TIMING_DEFINE_PRINT(fac_fq_evaluation)
     43TIMING_DEFINE_PRINT(fac_fq_recover_factors)
     44TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content)
     45TIMING_DEFINE_PRINT(fac_fq_bifactor_total)
     46TIMING_DEFINE_PRINT(fac_fq_luckswang)
     47TIMING_DEFINE_PRINT(fac_fq_lcheuristic)
     48TIMING_DEFINE_PRINT(fac_fq_content)
     49TIMING_DEFINE_PRINT(fac_fq_check_mainvar)
     50TIMING_DEFINE_PRINT(fac_fq_compress)
    4051
    4152static inline
     
    894905{
    895906  int i= A.level();
    896   contentAi.append (myContent (A, i));
    897   contentAi.append (myContent (A, i - 1));
     907  CanonicalForm buf= A;
     908  contentAi.append (content (buf, i));
     909  buf /= contentAi.getLast();
     910  contentAi.append (content (buf, i - 1));
    898911  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
    899912  for (i= i - 2; i > 0; i--)
    900913  {
    901     contentAi.append (content (A, i));
     914    contentAi.append (content (buf, i));
     915    buf /= contentAi.getLast();
    902916    result= lcm (result, contentAi.getLast());
    903917  }
     
    13271341
    13281342  CanonicalForm F= G;
    1329   CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
     1343  CFFList sqrfFactorization;
     1344  if (getCharacteristic() > 0)
     1345    sqrfFactorization= squarefreeFactorization (F, alpha);
     1346  else
     1347    sqrfFactorization= sqrFree (F);
    13301348
    13311349  sqrfPartF= 1;
     
    13481366  {
    13491367    tmp= 1;
    1350     sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
     1368    if (getCharacteristic() > 0)
     1369      sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
     1370    else
     1371      sqrfFactors= sqrFree (i.getItem());
    13511372
    13521373    for (iter= sqrfFactors; iter.hasItem(); iter++)
     
    21892210    return CFList (F);
    21902211
     2212  TIMING_START (fac_fq_preprocess_and_content);
    21912213  // compress and find main Variable
    21922214  CFMap N;
     2215  TIMING_START (fac_fq_compress)
    21932216  CanonicalForm A= myCompress (F, N);
     2217  TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
    21942218
    21952219  A /= Lc (A); // make monic
     
    22252249
    22262250  // remove content
     2251  TIMING_START (fac_fq_content);
    22272252  CFList contentAi;
    22282253  CanonicalForm lcmCont= lcmContent (A, contentAi);
    22292254  A /= lcmCont;
     2255  TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
    22302256
    22312257  // trivial after content removal
     
    22532279
    22542280  // factorize content
     2281  TIMING_START (fac_fq_content);
    22552282  contentAFactors= multiFactorize (lcmCont, info);
     2283  TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
    22562284
    22572285  // univariate after content removal
     
    22662294
    22672295  // check main variable
     2296  TIMING_START (fac_fq_check_mainvar);
    22682297  int swapLevel= 0;
    22692298  CanonicalForm derivZ;
     
    23082337    }
    23092338  }
    2310 
     2339  TIMING_END_AND_PRINT (fac_fq_check_mainvar,
     2340                        "time to check main var over Fq: ");
     2341  TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
     2342                       "time to preprocess poly and extract content over Fq: ");
    23112343
    23122344  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
     
    23152347  int level;
    23162348  int factorNums= 3;
    2317   CanonicalForm bivarEval;
    23182349  CFList biFactors, bufBiFactors;
    23192350  CanonicalForm evalPoly;
     
    23292360  int differentSecondVar= 0;
    23302361  // several bivariate factorizations
     2362  TIMING_START (fac_fq_bifactor_total);
    23312363  for (int i= 0; i < factorNums; i++)
    23322364  {
     
    23342366    bufA= A;
    23352367    bufAeval= CFList();
     2368    TIMING_START (fac_fq_evaluation);
    23362369    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
     2370    TIMING_END_AND_PRINT (fac_fq_evaluation,
     2371                          "time to find evaluation point over Fq: ");
    23372372    evalPoly= 0;
    23382373
     
    23792414      break;
    23802415
    2381     bivarEval= bufEvaluation.getLast();
    2382 
     2416    TIMING_START (fac_fq_evaluation);
    23832417    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
     2418    TIMING_END_AND_PRINT (fac_fq_evaluation,
     2419                          "time for evaluation wrt diff second vars over Fq: ");
    23842420
    23852421    for (int j= 0; j < lengthAeval2; j++)
     
    24562492  int minFactorsLength;
    24572493  bool irred= false;
     2494  TIMING_START (fac_fq_bi_factorizer);
    24582495  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
    2459 
     2496  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
     2497             "time for bivariate factorization wrt diff second vars over Fq: ");
     2498
     2499  TIMING_END_AND_PRINT (fac_fq_bifactor_total,
     2500                        "total time for eval and bivar factors over Fq: ");
    24602501  if (irred)
    24612502  {
     
    25282569
    25292570  Variable v;
     2571  TIMING_START (fac_fq_precompute_leadcoeff);
    25302572  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
    25312573                                          evaluation, Aeval2, lengthAeval2, v);
     
    26272669    }
    26282670  }
     2671  TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
     2672                       "time to precompute LC over Fq: ");
     2673
     2674  TIMING_START (fac_fq_luckswang);
    26292675  CFList bufFactors= CFList();
    26302676  bool LCheuristic= false;
     
    26542700      delete [] index;
    26552701      delete [] Aeval2;
     2702      TIMING_END_AND_PRINT (fac_fq_luckswang,
     2703                            "time for successful LucksWang over Fq: ");
    26562704      return factors;
    26572705    }
     
    29933041    delete [] index;
    29943042  }
    2995 
     3043  TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
     3044
     3045  TIMING_START (fac_fq_lcheuristic);
    29963046  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
    29973047      && fdivides (getVars (LCmultiplier), testVars))
     
    31433193    }
    31443194  }
     3195  TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
    31453196
    31463197tryAgainWithoutHeu:
     3198  TIMING_START (fac_fq_shift_to_zero);
    31473199  A= shift2Zero (A, Aeval, evaluation);
    31483200
     
    31633215    }
    31643216  }
     3217  TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
     3218                        "time to shift evaluation point to zero: ");
    31653219
    31663220  CFArray Pi;
     
    31733227  Aeval.removeFirst();
    31743228  bool noOneToOne= false;
     3229  TIMING_START (fac_fq_hensel_lift);
    31753230  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
    31763231                               Pi, liftBounds, liftBoundsLength, noOneToOne);
     3232  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
     3233                        "time for non monic hensel lifting over Fq: ");
    31773234
    31783235  if (!noOneToOne)
     
    31803237    int check= factors.length();
    31813238    A= oldA;
     3239    TIMING_START (fac_fq_recover_factors);
    31823240    factors= recoverFactors (A, factors, evaluation);
     3241    TIMING_END_AND_PRINT (fac_fq_recover_factors,
     3242                          "time to recover factors over Fq: ");
    31833243    if (check != factors.length())
    31843244      noOneToOne= true;
     
    32393299                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
    32403300                    Aeval, biFactors, evaluation, info);
    3241     TIMING_END_AND_PRINT (fac_fq_hensel_lift, "time for hensel lifting: ");
     3301    TIMING_END_AND_PRINT (fac_fq_hensel_lift,
     3302                          "time for hensel lifting over Fq: ");
    32423303
    32433304    if (!extension)
  • factory/facFqFactorize.h

    rbecbea r1130ffc  
    1515#define FAC_FQ_FACTORIZE_H
    1616
    17 // #include "config.h"
     17#include "config.h"
     18#include "timing.h"
    1819
    1920#include "facFqBivar.h"
     
    2324#include "facFqSquarefree.h"
    2425#include "facFqBivarUtil.h"
     26
     27
     28TIMING_DEFINE_PRINT (fac_fq_squarefree)
     29TIMING_DEFINE_PRINT (fac_fq_factor_squarefree)
    2530
    2631/// Factorization over a finite field
     
    150155  Variable a= Variable (1);
    151156  CanonicalForm LcF= Lc (F);
     157  TIMING_START (fac_fq_squarefree);
    152158  CFFList sqrf= FpSqrf (F, false);
     159  TIMING_END_AND_PRINT (fac_fq_squarefree,
     160                        "time for squarefree factorization over Fq: ");
    153161  CFFList result;
    154162  CFList bufResult;
     
    157165  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
    158166  {
     167    TIMING_START (fac_fq_factor_squarefree);
    159168    bufResult= multiFactorize (iter.getItem().factor(), info);
     169    TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
     170                          "time to factorize sqrfree factor over Fq: ");
    160171    for (i= bufResult; i.hasItem(); i++)
    161172      result.append (CFFactor (i.getItem(), iter.getItem().exp()));
     
    227238  ExtensionInfo info= ExtensionInfo (alpha, false);
    228239  CanonicalForm LcF= Lc (F);
     240  TIMING_START (fac_fq_squarefree);
    229241  CFFList sqrf= FqSqrf (F, alpha, false);
     242  TIMING_END_AND_PRINT (fac_fq_squarefree,
     243                        "time for squarefree factorization over Fq: ");
    230244  CFFList result;
    231245  CFList bufResult;
     
    234248  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
    235249  {
     250    TIMING_START (fac_fq_factor_squarefree);
    236251    bufResult= multiFactorize (iter.getItem().factor(), info);
     252    TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
     253                          "time to factorize sqrfree factor over Fq: ");
    237254    for (i= bufResult; i.hasItem(); i++)
    238255      result.append (CFFactor (i.getItem(), iter.getItem().exp()));
     
    640657             );
    641658
     659/// computes a list l of length length(LCFFactors)+1 of polynomials such that
     660/// prod (l)=LCF, note that the first entry of l may be non constant. Intended
     661/// to be used to precompute coefficients of a polynomial f from its bivariate
     662/// factorizations.
     663///
     664/// @return see above
     665CFList
     666precomputeLeadingCoeff (const CanonicalForm& LCF,       ///<[in] a multivariate
     667                                                        ///< poly
     668                        const CFList& LCFFactors,       ///<[in] a list of
     669                                                        ///< univariate factors
     670                                                        ///< of LCF of level 2
     671                        const Variable& alpha,          ///<[in] algebraic var.
     672                        const CFList& evaluation,       ///<[in] an evaluation
     673                                                        ///< point having
     674                                                        ///< lSecondVarLCs+1
     675                                                        ///< components
     676                        CFList* & differentSecondVarLCs,///<[in] LCs of factors
     677                                                        ///< of f wrt different
     678                                                        ///< second variables
     679                        int lSecondVarLCs,              ///<[in] length of the
     680                                                        ///< above
     681                        Variable& y                     ///<[in,out] if y.level()
     682                                                        ///< is not 1 on output
     683                                                        ///< the second variable
     684                                                        ///< has been changed to
     685                                                        ///< y
     686                       );
     687
    642688#endif
    643689/* FAC_FQ_FACTORIZE_H */
  • factory/fac_ezgcd.cc

    rbecbea r1130ffc  
    1515#include "config.h"
    1616
     17#include "timing.h"
    1718#include "cf_assert.h"
    1819#include "debug.h"
     
    3031
    3132#ifdef HAVE_NTL
     33
     34TIMING_DEFINE_PRINT(ez_eval)
     35TIMING_DEFINE_PRINT(ez_compress)
     36TIMING_DEFINE_PRINT(ez_hensel_lift)
     37TIMING_DEFINE_PRINT(ez_content)
     38TIMING_DEFINE_PRINT(ez_termination)
     39
    3240static
    3341int compress4EZGCD (const CanonicalForm& F, const CanonicalForm& G, CFMap & M,
     
    432440    Off (SW_RATIONAL);
    433441
     442  TIMING_START (ez_compress)
    434443  CFMap M,N;
    435444  int smallestDegLev;
     
    444453  F= M (F);
    445454  G= M (G);
     455  TIMING_END_AND_PRINT (ez_compress, "time for compression in EZ: ")
    446456
    447457  DEBINCLEVEL( cerr, "ezgcd" );
    448458  DEBOUTLN( cerr, "FF = " << FF );
    449459  DEBOUTLN( cerr, "GG = " << GG );
     460  TIMING_START (ez_content)
    450461  f = content( F, x ); g = content( G, x ); d = gcd( f, g );
    451462  d /= icontent (d);
     
    453464  DEBOUTLN( cerr, "g = " << g );
    454465  F /= f; G /= g;
     466  TIMING_END_AND_PRINT (ez_content, "time to extract content in EZ: ")
    455467  if ( F.isUnivariate() && G.isUnivariate() )
    456468  {
     
    500512    DEBOUTLN( cerr, "F = " << F );
    501513    DEBOUTLN( cerr, "G = " << G );
     514    TIMING_START (ez_eval)
    502515    if (!findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count,
    503516                   o, 25, l))
     
    512525      return N (d*result);
    513526    }
     527    TIMING_END_AND_PRINT (ez_eval, "time to find eval point in EZ1: ")
    514528    DEBOUTLN( cerr, "found evaluation b = " << b );
    515529    DEBOUTLN( cerr, "F(b) = " << Fb );
     
    530544    {
    531545      bt = b;
     546      TIMING_START (ez_eval)
    532547      if (!findeval( F, G, Fbt, Gbt, Dbt, bt, delta, degF, degG, maxeval, count,
    533548                     o, 25,l ))
     
    542557        return N (d*result);
    543558      }
     559      TIMING_END_AND_PRINT (ez_eval, "time to find eval point in EZ2: ")
    544560      int dd=degree( Dbt );
    545561      if ( dd /*degree( Dbt )*/ == 0 )
     
    636652      DEBOUTLN( cerr, "(hensel) DD   = " << DD );
    637653      DEBOUTLN( cerr, "(hensel) lcDD = " << lcDD );
     654      TIMING_START (ez_hensel_lift)
    638655      gcdfound= Hensel (B*lcD, DD, b, lcDD);
     656      TIMING_END_AND_PRINT (ez_hensel_lift, "time to hensel lift in EZ: ")
    639657      DEBOUTLN( cerr, "(hensel finished) DD   = " << DD );
    640658
     
    653671      if (gcdfound)
    654672      {
     673        TIMING_START (ez_termination)
    655674        contcand= content (DD[2], Variable (1));
    656675        cand = DD[2] / contcand;
     
    659678        else
    660679          gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
     680        TIMING_END_AND_PRINT (ez_termination,
     681                              "time for termination test in EZ: ")
    661682      }
    662683      /// ---> A8 (gcdfound)
  • factory/libfac/factor/timing.h

    rbecbea r1130ffc  
    4343#if defined(WINNT) && ! defined(__GNUC__)
    4444
    45 #define TIMING_START(t) { clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
    46   timing_ ## t ## _start = clock();
     45#define TIMING_START(t) timing_ ## t ## _start = clock();
    4746#define TIMING_END(t) timing_ ## t ## _end = clock(); \
    48 timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
     47timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
    4948#define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
    5049  fprintf( stderr, "%s%.2f sec\n", msg, \
    5150           float( timing_ ## t ## _end - timing_ ## t ## _start ) / HZ ); \
    52   timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
    53 #define TIMING_DEFINE_PRINT(t) clock_t timing_ ## t ## _time; \
    54 void timing_print_ ## t ( char * msg ) { \
     51  timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
     52#define TIMING_DEFINE_PRINT(t) static clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
     53static clock_t timing_ ## t ## _time; \
     54static void timing_print_ ## t ( char * msg ) { \
    5555  fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
    5656} \
    57 void timing_reset_ ## t () { \
     57static void timing_reset_ ## t () { \
    5858  timing_ ## t ## _time = 0; \
    5959}
     
    6161#else /* ! WINNT */
    6262
    63 #define TIMING_START(t) { struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
    64   times( &timing_ ## t ## _start );
     63#define TIMING_START(t) times( &timing_ ## t ## _start );
    6564#define TIMING_END(t) times( &timing_ ## t ## _end ); \
    66   timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
     65  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
    6766#define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
    6867  fprintf( stderr, "%s%.2f sec\n", msg, \
    6968           float( timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime ) / HZ ); \
    70   timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
    71 #define TIMING_DEFINE_PRINT(t) long timing_ ## t ## _time; \
    72 void timing_print_ ## t ( char * msg ) { \
     69  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
     70#define TIMING_DEFINE_PRINT(t) static struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
     71static long timing_ ## t ## _time; \
     72static void timing_print_ ## t ( char * msg ) { \
    7373  fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
    7474} \
    75 void timing_reset_ ## t () { \
     75static void timing_reset_ ## t () { \
    7676  timing_ ## t ## _time = 0; \
    7777}
  • factory/timing.h

    rbecbea r1130ffc  
    4343#if defined(WINNT) && ! defined(__GNUC__)
    4444
    45 #define TIMING_START(t) { clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
    46   timing_ ## t ## _start = clock();
     45#define TIMING_START(t) timing_ ## t ## _start = clock();
    4746#define TIMING_END(t) timing_ ## t ## _end = clock(); \
    48 timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
     47timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
    4948#define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
    5049  fprintf( stderr, "%s%.2f sec\n", msg, \
    5150           float( timing_ ## t ## _end - timing_ ## t ## _start ) / HZ ); \
    52   timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start; }
    53 #define TIMING_DEFINE_PRINT(t) clock_t timing_ ## t ## _time; \
    54 void timing_print_ ## t ( char * msg ) { \
     51  timing_ ## t ## _time += timing_ ## t ## _end - timing_ ## t ## _start;
     52#define TIMING_DEFINE_PRINT(t) static clock_t timing_ ## t ## _start, timing_ ## t ## _end; \
     53static clock_t timing_ ## t ## _time; \
     54static void timing_print_ ## t ( char * msg ) { \
    5555  fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
    5656} \
    57 void timing_reset_ ## t () { \
     57static void timing_reset_ ## t () { \
    5858  timing_ ## t ## _time = 0; \
    5959}
     
    6161#else /* ! WINNT */
    6262
    63 #define TIMING_START(t) { struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
    64   times( &timing_ ## t ## _start );
     63#define TIMING_START(t) times( &timing_ ## t ## _start );
    6564#define TIMING_END(t) times( &timing_ ## t ## _end ); \
    66   timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
     65  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
    6766#define TIMING_END_AND_PRINT(t, msg) times( &timing_ ## t ## _end ); \
    6867  fprintf( stderr, "%s%.2f sec\n", msg, \
    6968           float( timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime ) / HZ ); \
    70   timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime; }
    71 #define TIMING_DEFINE_PRINT(t) long timing_ ## t ## _time; \
    72 void timing_print_ ## t ( char * msg ) { \
     69  timing_ ## t ## _time += timing_ ## t ## _end.tms_utime - timing_ ## t ## _start.tms_utime;
     70#define TIMING_DEFINE_PRINT(t) static struct tms timing_ ## t ## _start, timing_ ## t ## _end; \
     71static long timing_ ## t ## _time; \
     72static void timing_print_ ## t ( char * msg ) { \
    7373  fprintf( stderr, "%s%.2f sec\n", msg, float(timing_ ## t ## _time) / HZ ); \
    7474} \
    75 void timing_reset_ ## t () { \
     75static void timing_reset_ ## t () { \
    7676  timing_ ## t ## _time = 0; \
    7777}
Note: See TracChangeset for help on using the changeset viewer.