Changeset 1ade96 in git


Ignore:
Timestamp:
Feb 16, 2012, 4:35:20 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '648d28f488f6ff08f5607ff229b9ad9e4a5b93c2')
Children:
f9bd3df575b00ad6b5b1f49bf42ebe194e4bb7b2
Parents:
667ba13dd7bcac6f144c71d80aad80c7fe86c3cd
git-author:
Martin Lee <martinlee84@web.de>2012-02-16 16:35:20+01:00
git-committer:
Martin Lee <martinlee84@web.de>2012-04-04 14:42:26+02:00
Message:
chg: use coeff bound in bivariate poly factorization over Q
File:
1 edited

Legend:

Unmodified
Added
Removed
  • factory/facBivar.cc

    r667ba1 r1ade96  
    2424#include "facHensel.h"
    2525#include "facMul.h"
     26#include "cf_primes.h"
    2627
    2728#ifdef HAVE_NTL
    2829TIMING_DEFINE_PRINT(uni_factorize)
    2930TIMING_DEFINE_PRINT(hensel_lift12)
     31
     32static modpk
     33coeffBound ( const CanonicalForm & f, int p )
     34{
     35    int * degs = degrees( f );
     36    int M = 0, i, k = f.level();
     37    for ( i = 1; i <= k; i++ )
     38        M += degs[i];
     39    CanonicalForm b = 2 * maxNorm( f ) * power( CanonicalForm( 3 ), M );
     40    CanonicalForm B = p;
     41    k = 1;
     42    while ( B < b ) {
     43        B *= p;
     44        k++;
     45    }
     46    return modpk( p, k );
     47}
     48
     49static
     50void find_good_prime(const CanonicalForm &f, int &start)
     51{
     52  if (! f.inBaseDomain() )
     53  {
     54    CFIterator i = f;
     55    for(;;)
     56    {
     57      if  ( i.hasTerms() )
     58      {
     59        find_good_prime(i.coeff(),start);
     60        if (0==cf_getSmallPrime(start)) return;
     61        if((i.exp()!=0) && ((i.exp() % cf_getSmallPrime(start))==0))
     62        {
     63          start++;
     64          i=f;
     65        }
     66        else  i++;
     67      }
     68      else break;
     69    }
     70  }
     71  else
     72  {
     73    if (f.inZ())
     74    {
     75      if (0==cf_getSmallPrime(start)) return;
     76      while((!f.isZero()) && (mod(f,cf_getSmallPrime(start))==0))
     77      {
     78        start++;
     79        if (0==cf_getSmallPrime(start)) return;
     80      }
     81    }
     82  }
     83}
    3084
    3185CFList conv (const CFFList& L)
     
    528582  }
    529583
    530   if (!extension)
    531   {
    532     for (CFListIterator i= uniFactors; i.hasItem(); i++)
    533       i.getItem() /= lc (i.getItem());
    534   }
    535 
    536584  A= A (y + evaluation, y);
    537585
    538586  int liftBound= degree (A, y) + 1;
     587
     588  modpk b= modpk();
     589  if ( !extension)
     590  {
     591    Off (SW_RATIONAL);
     592    int i= 0;
     593    do
     594    {
     595      find_good_prime(F,i);
     596      find_good_prime(Aeval,i);
     597      find_good_prime(A,i);
     598      setCharacteristic (cf_getSmallPrime(i));
     599      if (gcd (Aeval.mapinto(), deriv (Aeval,x).mapinto()).inCoeffDomain())
     600      {
     601        setCharacteristic (0);
     602        break;
     603      }
     604      else
     605        i++;
     606      if (i > cf_getNumSmallPrimes())
     607      {
     608        printf ("out of primes\n");
     609        break;
     610      }
     611    } while (1);
     612
     613    int p=cf_getSmallPrime(i);
     614    b = coeffBound( A, p );
     615    modpk bb= coeffBound (Aeval, p);
     616    if (bb.getk() > b.getk() ) b=bb;
     617      bb= coeffBound (F, p);
     618    if (bb.getk() > b.getk() ) b=bb;
     619  }
    539620
    540621  ExtensionInfo dummy= ExtensionInfo (false);
     
    545626  uniFactors= henselLiftAndEarly
    546627              (A, earlySuccess, earlyFactors, degs, liftBound,
    547                uniFactors, dummy, evaluation);
     628               uniFactors, dummy, evaluation, b);
    548629  TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
    549630  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
     
    552633
    553634  factors= factorRecombination (uniFactors, A, MODl, degs, 1,
    554                                 uniFactors.length()/2);
     635                                uniFactors.length()/2, b);
     636
     637  if (!extension)
     638    On (SW_RATIONAL);
    555639
    556640  if (earlySuccess)
Note: See TracChangeset for help on using the changeset viewer.