13#elif defined(HAVE_IOSTREAM)
62 for (
int i = 0;
i <= n;
i++)
77 for (
int i= 1;
i <= n;
i++)
106 for (
int i= 1;
i <= n;
i++)
141 while (min_max_deg == 0)
150 for (
int j=
i + 1;
j <=
m;
j++)
197 for (
int i= 1;
i <= n;
i++)
276 for (
int i= degA -degB;
i >= 0;
i--)
292 if(
A.inCoeffDomain())
368 interPoly= oldInterPoly+
reduce ((u - oldInterPoly (
alpha,
x))*inv*newtonPoly,
M);
375 if(
f.inCoeffDomain())
476 zz_pE::init (NTLMipo);
517 tryEuclid(
cf,
cg,
M,c,fail);
522 f.tryDiv (
cf,
M, fail);
526 g.tryDiv (
cg,
M, fail);
530 if(
f.inCoeffDomain())
538 if(
g.inCoeffDomain())
548 for(
int i=2;
i<=mv;
i++)
567 for(
int i=2;
i<=mv;
i++)
572 for(
int i=2;
i<=mv;
i++)
589 "time for recursive calls in alg gcd mod p: ")
601 for(
int i=2;
i<=mv;
i++)
611 g_image *= gamma_image;
616 "time for Newton interpolation in alg gcd mod p: ")
623 if((
firstLC(gnew) == gamma) || (gnew == gm))
646 "time for successful termination test in alg gcd mod p: ")
651 "time for unsuccessful termination test in alg gcd mod p: ")
657 if(
isLess(L, dg_im, 2, mv))
663 for(
int i=2;
i<=mv;
i++)
673#if defined(HAVE_NTL) || defined(HAVE_FLINT)
674 if (
f.isOne() || c.
isOne())
687 fmpz_poly_t FLINTf, FLINTc;
690 fmpz_poly_gcd (FLINTc, FLINTc, FLINTf);
692 if (
f.inCoeffDomain())
696 fmpz_poly_clear (FLINTc);
697 fmpz_poly_clear (FLINTf);
702 NTLc= GCD (NTLc, NTLf);
703 if (
f.inCoeffDomain())
723#if defined(HAVE_NTL) || defined(HAVE_FLINT)
794 int mv =
f.level();
i =
g.level();
798 bound =
new int[mv+1];
799 other =
new int[mv+1];
800 for(
int i=1;
i<=mv;
i++)
804 for(
int i=1;
i<=mv;
i++)
845 for(
int i=1;
i<=mv;
i++)
863 "time for rational reconstruction in alg gcd: ")
874 &&
f.level() == tmp.
level() && tmp.
level() ==
g.level())
887 "time for successful termination test in alg gcd: ")
903 "time for successful termination test in alg gcd: ")
909 "time for unsuccessful termination test in alg gcd: ")
919 for(
int i=1;
i<=mv;
i++)
935bool isLess(
int *a,
int *
b,
int lower,
int upper)
937 for(
int i=upper;
i>=lower;
i--)
948 for(
int i=lower;
i<=upper;
i++)
958 while(ret.
level() > 1)
1037 ASSERT(
x.
level() > 0,
"cannot calculate content with respect to algebraic variable" );
1049 ASSERT(
x.
level() > 0,
"cannot calculate vcontent with respect to algebraic variable" );
1050 if (
f.mvar() <=
x )
1054 for (
i =
f;
i.hasTerms() && ! d.
isOne() && ! fail;
i++ )
1068 if (
f.inPolyDomain() || (
f.inExtension() && !
getReduce(
f.mvar() ) ) )
1072 while (
i.hasTerms() && ! tmp.
isOne() && ! fail )
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational abs(const Rational &a)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Conversion to and from NTL.
const CanonicalForm CFMap CFMap & N
bool isLess(int *a, int *b, int lower, int upper)
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
static void leadDeg(const CanonicalForm &f, int degs[])
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
static CanonicalForm trycontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
const CanonicalForm CFMap CFMap bool topLevel
bool isEqual(int *a, int *b, int lower, int upper)
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
static CanonicalForm trycf_content(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
const CanonicalForm CFMap & M
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
CanonicalForm firstLC(const CanonicalForm &f)
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
void tryNTLGCD(zz_pEX &x, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the GCD x of a and b, fail is set to true if a zero divisor is encountered
This file defines functions for univariate GCD and extended GCD over Z/p[t]/(f)[x] for reducible f.
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
declarations of higher level algorithms.
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
#define ASSERT(expression, message)
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
static const int SW_RATIONAL
set to 1 for computations over Q
generate integers, elements of finite fields
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
int cf_getBigPrime(int i)
class to iterate through CanonicalForm's
generate all elements in F_p starting from 0
CanonicalForm item() const
factory's class for variables
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
const Variable & v
< [in] a sqrfree bivariate poly
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
This file defines functions for fast multiplication and division with remainder.
bool isZero(const CFArray &A)
checks if entries of A are zero
static number Farey(number, number, const coeffs)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)
void setReduce(const Variable &alpha, bool reduce)
bool getReduce(const Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)