11 #ifdef HAVE_IOSTREAM_H
13 #elif defined(HAVE_IOSTREAM)
59 int n=
tmax (F.level(), G.level());
63 for (
int i = 0;
i <=
n;
i++)
64 degsf[
i]= degsg[
i]= 0;
76 for (
int i= 1;
i <=
n;
i++)
78 if (degsf[
i] != 0 && degsg[
i] != 0)
83 if (degsf[
i] == 0 && degsg[
i] != 0 &&
i <= G.level())
88 if (degsg[
i] == 0 && degsf[
i] &&
i <= F.level())
95 if (both_non_zero == 0)
105 for (
int i= 1;
i <=
n;
i++)
107 if (degsf[
i] != 0 && degsg[
i] == 0 &&
i <= F.level())
109 if (k + both_non_zero !=
i)
116 if (degsf[
i] == 0 && degsg[
i] != 0 &&
i <= G.level())
118 if (l + g_zero + both_non_zero !=
i)
129 int m=
tmax (F.level(), G.level());
136 if (degsf [i] != 0 && degsg [i] != 0)
137 min_max_deg=
tmax (degsf[i], degsg[i]);
140 while (min_max_deg == 0)
143 min_max_deg=
tmax (degsf[i], degsg[i]);
144 if (degsf [i] != 0 && degsg [i] != 0)
145 min_max_deg=
tmax (degsf[i], degsg[i]);
149 for (
int j= i + 1;
j <=
m;
j++)
151 if (
tmax (degsf[
j],degsg[j]) <= min_max_deg && degsf[j] != 0 && degsg [j] != 0)
153 min_max_deg=
tmax (degsf[j], degsg[j]);
196 for (
int i= 1;
i <=
n;
i++)
198 if (degsf[
i] == 0 && degsg[
i] == 0)
275 for (
int i= degA -degB;
i >= 0;
i--)
323 result=
reduce (result, M);
331 tryDivrem (P, result, Q, rem, inv, M, fail);
337 result=
reduce (result, M);
353 bool isLess(
int *
a,
int *
b,
int lower,
int upper);
354 bool isEqual(
int *
a,
int *
b,
int lower,
int upper);
368 tryInvert (newtonPoly (alpha, x), M, inv, fail);
372 interPoly= oldInterPoly+
reduce ((u - oldInterPoly (alpha, x))*inv*newtonPoly, M);
400 result=
reduce (result, M);
419 result=
reduce (result, M);
465 zz_pE::init (NTLMipo);
481 tryEuclid(f,g,M,result,fail);
486 result= NN (
reduce (result, M));
506 tryEuclid(cf,cg,M,c,fail);
535 int *L =
new int[mv+1];
536 int *N =
new int[mv+1];
537 for(
int i=2;
i<=mv;
i++)
556 for(
int i=2;
i<=mv;
i++)
560 int *dg_im =
new int[mv+1];
561 for(
int i=2; i<=mv; i++)
572 gamma_image =
reduce(gamma(alpha, x),M);
576 tryBrownGCD(
f(alpha, x),
g(alpha, x), M, g_image, fail,
false );
578 "time for recursive calls in alg gcd mod p: ")
581 g_image =
reduce(g_image, M);
590 for(
int i=2; i<=mv; i++)
592 dg_im =
leadDeg(g_image, dg_im);
600 g_image *= gamma_image;
601 g_image=
reduce (g_image, M);
605 "time for Newton interpolation in alg gcd mod p: ")
612 if((
firstLC(gnew) == gamma) || (gnew == gm))
620 g_image.
tryDiv (cf, M, fail);
633 result = NN(
reduce (c*g_image, M));
635 "time for successful termination test in alg gcd mod p: ")
640 "time for unsuccessful termination test in alg gcd mod p: ")
646 if(
isLess(L, dg_im, 2, mv))
652 for(
int i=2; i<=mv; i++)
676 fmpz_poly_t FLINTf, FLINTc;
679 fmpz_poly_gcd (FLINTc, FLINTc, FLINTf);
685 fmpz_poly_clear (FLINTc);
686 fmpz_poly_clear (FLINTf);
691 NTLc= GCD (NTLc, NTLf);
771 tmp = gcdcfcg*
gcd( f, g );
788 bound =
new int[mv+1];
789 other =
new int[mv+1];
790 for(
int i=1; i<=mv; i++)
791 bound[i] = other[i] = 0;
794 for(
int i=1; i<=mv; i++)
795 if(other[i] < bound[i])
798 cl =
lc(M) *
lc(f) *
lc(g);
830 for(
int i=1; i<=mv; i++)
834 if(
isEqual(bound, other, 1, mv))
848 "time for rational reconstruction in alg gcd: ")
872 "time for successful termination test in alg gcd: ")
886 "time for successful termination test in alg gcd: ")
890 "time for unsuccessful termination test in alg gcd: ")
895 if(
isLess(bound, other, 1, mv) )
900 for(
int i=1; i<=mv; i++)
906 D = gcdcfcg*
gcd( f, g );
932 for(
int i=upper;
i>=lower;
i--)
943 for(
int i=lower;
i<=upper;
i++)
953 while(ret.
level() > 1)
988 P = F; result =
G; s=v=0; t=u=1;
992 P =
G; result = F; s=v=1; t=u=0;
998 tryDivrem (P, result, q, rem, inv, M, fail);
1008 result=
reduce (result, M);
1032 ASSERT( x.
level() > 0,
"cannot calculate content with respect to algebraic variable" );
1044 ASSERT( x.
level() > 0,
"cannot calculate vcontent with respect to algebraic variable" );
1045 if ( f.
mvar() <=
x )
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
const CanonicalForm int s
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
const CanonicalForm int const CFList const Variable & y
Conversion to and from NTL.
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
static CanonicalForm bound(const CFMatrix &M)
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
some useful template functions.
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
void setReduce(const Variable &alpha, bool reduce)
#define TIMING_END_AND_PRINT(t, msg)
factory's class for variables
const CanonicalForm CFMap & M
generate all elements in F_p starting from 0
const CanonicalForm CFMap CFMap int &both_non_zero int n
static CanonicalForm trycf_content(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
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 ...
CanonicalForm item() const
const CanonicalForm CFMap CFMap bool topLevel
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Rational abs(const Rational &a)
TIMING_DEFINE_PRINT(alg_content_p) TIMING_DEFINE_PRINT(alg_content) TIMING_DEFINE_PRINT(alg_compress) TIMING_DEFINE_PRINT(alg_termination) TIMING_DEFINE_PRINT(alg_termination_p) TIMING_DEFINE_PRINT(alg_reconstruction) TIMING_DEFINE_PRINT(alg_newton_p) TIMING_DEFINE_PRINT(alg_recursion_p) TIMING_DEFINE_PRINT(alg_gcd_p) TIMING_DEFINE_PRINT(alg_euclid_p) static int myCompress(const CanonicalForm &F
compressing two polynomials F and G, M is used for compressing, N to reverse the compression ...
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
bool isLess(int *a, int *b, int lower, int upper)
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
generate integers, elements of finite fields
This file defines functions for fast multiplication and division with remainder.
const CanonicalForm CFMap CFMap & N
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm firstLC(const CanonicalForm &f)
bool getReduce(const Variable &alpha)
static const int SW_RATIONAL
set to 1 for computations over Q
Iterators for CanonicalForm's.
int * leadDeg(const CanonicalForm &f, int *degs)
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, satisfying F=G*Q+R, deg(R) < deg(G)
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
declarations of higher level algorithms.
This file defines functions for univariate GCD and extended GCD over Z/p[t]/(f)[x] for reducible f...
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
bool isEqual(int *a, int *b, int lower, int upper)
class to iterate through CanonicalForm's
void 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...
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
static CanonicalForm trycontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
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 ...
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
int cf_getBigPrime(int i)
bool isZero(const CFArray &A)
checks if entries of A are zero
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 ...
#define ASSERT(expression, message)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
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 ...
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)