Changeset 1e5c50 in git


Ignore:
Timestamp:
Nov 12, 2012, 6:21:05 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b21a664aa22dc6e196223af8a74ad4885e83547c')
Children:
f6237dd32a31b0c8c58f56d6a808bda992e743fa
Parents:
6ea864278bd3cbb9e4869b30bd2abcd525d6ed30
git-author:
Martin Lee <martinlee84@web.de>2012-11-12 18:21:05+01:00
git-committer:
Martin Lee <martinlee84@web.de>2012-11-16 13:20:45+01:00
Message:
chg: faster divisibility test in univariate case in QGCD
chg: added newtonDivrem to header
Location:
factory
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/algext.cc

    r6ea864 r1e5c50  
    2626#include "cf_map.h"
    2727#include "cf_generator.h"
     28#include "facMul.h"
    2829
    2930#ifdef HAVE_NTL
     
    821822        equal= true; // modular image did not add any new information
    822823      TIMING_START (alg_termination)
     824#ifdef HAVE_FLINT
     825      if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
     826          && f.level() == tmp.level() && tmp.level() == g.level())
     827      {
     828        CanonicalForm Q, R, sf, sg, stmp;
     829        Variable x= Variable (1);
     830        sf= swapvar (f, f.mvar(), x);
     831        sg= swapvar (g, f.mvar(), x);
     832        stmp= swapvar (tmp, f.mvar(), x);
     833        newtonDivrem (sf, stmp, Q, R);
     834        if (R.isZero())
     835        {
     836          newtonDivrem (sg, stmp, Q, R);
     837          if (R.isZero())
     838          {
     839            Off (SW_RATIONAL);
     840            setReduce (a,true);
     841            if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
     842            TIMING_END_AND_PRINT (alg_termination,
     843                                 "time for successful termination test in alg gcd: ")
     844            return tmp*gcdcfcg;
     845          }
     846        }
     847      }
     848      else
     849#endif
    823850      if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
    824851      {
  • factory/facMul.h

    r6ea864 r1e5c50  
    155155         const CFList& M  ///< [in] contains only powers of Variables
    156156        );
     157
     158#ifdef HAVE_FLINT
     159/// division with remainder of univariate polynomials over Q and Q(a) using
     160/// Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
     161void
     162newtonDivrem (const CanonicalForm& F, ///<[in] univariate poly
     163              const CanonicalForm& G, ///<[in] univariate poly
     164              CanonicalForm& Q,       ///<[in, out] quotient
     165              CanonicalForm& R        ///<[in, out] remainder
     166             );
     167#endif
     168
    157169#endif
    158170/* FAC_MUL_H */
Note: See TracChangeset for help on using the changeset viewer.