Loading...
Searching...
No Matches
cf_gcd.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
/**
* @file cf_gcd.cc
*
* gcd/content/lcm of polynomials
*
* To compute the GCD different variants are chosen automatically
**/
#include "config.h"
#include "timing.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_reval.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "cfEzgcd.h"
#include "cfGcdAlgExt.h"
#include "cfSubResGcd.h"
#include "cfModGcd.h"
#include "FLINTconvert.h"
#include "facAlgFuncUtil.h"
#include "templates/ftmpl_functions.h"
#ifdef HAVE_NTL
#include <NTL/ZZX.h>
#include "NTLconvert.h"
bool isPurePoly(const CanonicalForm & );
#endif
void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
/** static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
*
* icontent() - return gcd of c and all coefficients of f which
* are in a coefficient domain.
*
* @sa icontent().
*
**/
static CanonicalForm
icontent ( const CanonicalForm & f, const CanonicalForm & c )
{
if ( f.inBaseDomain() )
{
if (c.isZero()) return abs(f);
return bgcd( f, c );
}
//else if ( f.inCoeffDomain() )
// return gcd(f,c);
else
{
CanonicalForm g = c;
for ( CFIterator i = f; i.hasTerms() && ! g.isOne(); i++ )
g = icontent( i.coeff(), g );
return g;
}
}
/** CanonicalForm icontent ( const CanonicalForm & f )
*
* icontent() - return gcd over all coefficients of f which are
* in a coefficient domain.
*
**/
CanonicalForm
icontent ( const CanonicalForm & f )
{
return icontent( f, 0 );
}
#ifdef HAVE_FLINT
static CanonicalForm
gcd_univar_flintp (const CanonicalForm& F, const CanonicalForm& G)
{
nmod_poly_t F1, G1;
convertFacCF2nmod_poly_t (F1, F);
convertFacCF2nmod_poly_t (G1, G);
nmod_poly_gcd (F1, F1, G1);
CanonicalForm result= convertnmod_poly_t2FacCF (F1, F.mvar());
nmod_poly_clear (F1);
nmod_poly_clear (G1);
return result;
}
static CanonicalForm
gcd_univar_flint0( const CanonicalForm & F, const CanonicalForm & G )
{
fmpz_poly_t F1, G1;
convertFacCF2Fmpz_poly_t(F1, F);
convertFacCF2Fmpz_poly_t(G1, G);
fmpz_poly_gcd (F1, F1, G1);
CanonicalForm result= convertFmpz_poly_t2FacCF (F1, F.mvar());
fmpz_poly_clear (F1);
fmpz_poly_clear (G1);
return result;
}
#endif
#ifdef HAVE_NTL
#ifndef HAVE_FLINT
static CanonicalForm
gcd_univar_ntl0( const CanonicalForm & F, const CanonicalForm & G )
{
ZZX F1=convertFacCF2NTLZZX(F);
ZZX G1=convertFacCF2NTLZZX(G);
ZZX R=GCD(F1,G1);
return convertNTLZZX2CF(R,F.mvar());
}
static CanonicalForm
gcd_univar_ntlp( const CanonicalForm & F, const CanonicalForm & G )
{
int ch=getCharacteristic();
if (fac_NTL_char!=ch)
{
fac_NTL_char=ch;
zz_p::init(ch);
}
zz_pX F1=convertFacCF2NTLzzpX(F);
zz_pX G1=convertFacCF2NTLzzpX(G);
zz_pX R=GCD(F1,G1);
return convertNTLzzpX2CF(R,F.mvar());
}
#endif
#endif
//{{{ static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q )
//{{{ docu
//
// balance_p() - map f from positive to symmetric representation
// mod q.
//
// This makes sense for univariate polynomials over Z only.
// q should be an integer.
//
// Used by gcd_poly_univar0().
//
//}}}
static CanonicalForm
balance_p ( const CanonicalForm & f, const CanonicalForm & q, const CanonicalForm & qh )
{
Variable x = f.mvar();
CanonicalForm result = 0;
CanonicalForm c;
CFIterator i;
for ( i = f; i.hasTerms(); i++ )
{
c = i.coeff();
if ( c.inCoeffDomain())
{
if ( c > qh )
result += power( x, i.exp() ) * (c - q);
else
result += power( x, i.exp() ) * c;
}
else
result += power( x, i.exp() ) * balance_p(c,q,qh);
}
return result;
}
static CanonicalForm
balance_p ( const CanonicalForm & f, const CanonicalForm & q )
{
CanonicalForm qh = q / 2;
return balance_p (f, q, qh);
}
static CanonicalForm gcd_poly_univar0( const CanonicalForm & F, const CanonicalForm & G, bool primitive )
{
CanonicalForm f, g, c, cg, cl, BB, B, M, q, Dp, newD, D, newq;
int p, i;
if ( primitive )
{
f = F;
g = G;
c = 1;
}
else
{
CanonicalForm cF = content( F ), cG = content( G );
f = F / cF;
g = G / cG;
c = bgcd( cF, cG );
}
cg = gcd( f.lc(), g.lc() );
cl = ( f.lc() / cg ) * g.lc();
// B = 2 * cg * tmin(
// maxnorm(f)*power(CanonicalForm(2),f.degree())*isqrt(f.degree()+1),
// maxnorm(g)*power(CanonicalForm(2),g.degree())*isqrt(g.degree()+1)
// )+1;
M = tmin( maxNorm(f), maxNorm(g) );
BB = power(CanonicalForm(2),tmin(f.degree(),g.degree()))*M;
q = 0;
i = cf_getNumSmallPrimes() - 1;
while ( true )
{
B = BB;
while ( i >= 0 && q < B )
{
p = cf_getSmallPrime( i );
i--;
while ( i >= 0 && mod( cl, p ) == 0 )
{
p = cf_getSmallPrime( i );
i--;
}
setCharacteristic( p );
Dp = gcd( mapinto( f ), mapinto( g ) );
Dp = ( Dp / Dp.lc() ) * mapinto( cg );
setCharacteristic( 0 );
if ( Dp.degree() == 0 )
return c;
if ( q.isZero() )
{
D = mapinto( Dp );
q = p;
B = power(CanonicalForm(2),D.degree())*M+1;
}
else
{
if ( Dp.degree() == D.degree() )
{
chineseRemainder( D, q, mapinto( Dp ), p, newD, newq );
q = newq;
D = newD;
}
else if ( Dp.degree() < D.degree() )
{
// all previous p's are bad primes
q = p;
D = mapinto( Dp );
B = power(CanonicalForm(2),D.degree())*M+1;
}
// else p is a bad prime
}
}
if ( i >= 0 )
{
// now balance D mod q
D = pp( balance_p( D, q ) );
if ( fdivides( D, f ) && fdivides( D, g ) )
return D * c;
else
q = 0;
}
else
return gcd_poly( F, G );
DEBOUTLN( cerr, "another try ..." );
}
}
static CanonicalForm
gcd_poly_p( const CanonicalForm & f, const CanonicalForm & g )
{
if (f.inCoeffDomain() || g.inCoeffDomain()) //zero case should be caught by gcd
return 1;
CanonicalForm pi, pi1;
CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
bool bpure, ezgcdon= isOn (SW_USE_EZGCD_P);
int delta = degree( f ) - degree( g );
if ( delta >= 0 )
{
pi = f; pi1 = g;
}
else
{
pi = g; pi1 = f; delta = -delta;
}
if (pi.isUnivariate())
Ci= 1;
else
{
if (!ezgcdon)
On (SW_USE_EZGCD_P);
Ci = content( pi );
if (!ezgcdon)
Off (SW_USE_EZGCD_P);
pi = pi / Ci;
}
if (pi1.isUnivariate())
Ci1= 1;
else
{
if (!ezgcdon)
On (SW_USE_EZGCD_P);
Ci1 = content( pi1 );
if (!ezgcdon)
Off (SW_USE_EZGCD_P);
pi1 = pi1 / Ci1;
}
C = gcd( Ci, Ci1 );
int d= 0;
if ( !( pi.isUnivariate() && pi1.isUnivariate() ) )
{
if ( gcd_test_one( pi1, pi, true, d ) )
{
C=abs(C);
//out_cf("GCD:",C,"\n");
return C;
}
bpure = false;
}
else
{
bpure = isPurePoly(pi) && isPurePoly(pi1);
#ifdef HAVE_FLINT
if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
return gcd_univar_flintp(pi,pi1)*C;
#else
#ifdef HAVE_NTL
if ( bpure && (CFFactory::gettype() != GaloisFieldDomain))
return gcd_univar_ntlp(pi, pi1 ) * C;
#endif
#endif
}
Variable v = f.mvar();
Hi = power( LC( pi1, v ), delta );
int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
if (!(pi.isUnivariate() && pi1.isUnivariate()))
{
if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (pi, pi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
}
if ( (delta+1) % 2 )
bi = 1;
else
bi = -1;
CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
while ( degree( pi1, v ) > 0 )
{
if (!(pi.isUnivariate() && pi1.isUnivariate()))
{
if (size (pi)/maxNumVars > 500 || size (pi1)/maxNumVars > 500)
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (oldPi, oldPi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
}
pi2 = psr( pi, pi1, v );
pi2 = pi2 / bi;
pi = pi1; pi1 = pi2;
maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
if (!pi1.isUnivariate() && (size (pi1)/maxNumVars > 500))
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (oldPi, oldPi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
if ( degree( pi1, v ) > 0 )
{
delta = degree( pi, v ) - degree( pi1, v );
powHi= power (Hi, delta-1);
if ( (delta+1) % 2 )
bi = LC( pi, v ) * powHi*Hi;
else
bi = -LC( pi, v ) * powHi*Hi;
Hi = power( LC( pi1, v ), delta ) / powHi;
if (!(pi.isUnivariate() && pi1.isUnivariate()))
{
if (size (Hi)*size (pi)/(maxNumVars*3) > 1500) //maybe this needs more tuning
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (oldPi, oldPi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
}
}
}
if ( degree( pi1, v ) == 0 )
{
C=abs(C);
//out_cf("GCD:",C,"\n");
return C;
}
if (!pi.isUnivariate())
{
if (!ezgcdon)
On (SW_USE_EZGCD_P);
Ci= gcd (LC (oldPi,v), LC (oldPi1,v));
pi /= LC (pi,v)/Ci;
Ci= content (pi);
pi /= Ci;
if (!ezgcdon)
Off (SW_USE_EZGCD_P);
}
if ( bpure )
pi /= pi.lc();
C=abs(C*pi);
//out_cf("GCD:",C,"\n");
return C;
}
static CanonicalForm
gcd_poly_0( const CanonicalForm & f, const CanonicalForm & g )
{
CanonicalForm pi, pi1;
CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
int delta = degree( f ) - degree( g );
if ( delta >= 0 )
{
pi = f; pi1 = g;
}
else
{
pi = g; pi1 = f; delta = -delta;
}
Ci = content( pi ); Ci1 = content( pi1 );
pi1 = pi1 / Ci1; pi = pi / Ci;
C = gcd( Ci, Ci1 );
int d= 0;
if ( pi.isUnivariate() && pi1.isUnivariate() )
{
#ifdef HAVE_FLINT
if (isPurePoly(pi) && isPurePoly(pi1) )
return gcd_univar_flint0(pi, pi1 ) * C;
#else
#ifdef HAVE_NTL
if ( isPurePoly(pi) && isPurePoly(pi1) )
return gcd_univar_ntl0(pi, pi1 ) * C;
#endif
#endif
return gcd_poly_univar0( pi, pi1, true ) * C;
}
else if ( gcd_test_one( pi1, pi, true, d ) )
return C;
Variable v = f.mvar();
Hi = power( LC( pi1, v ), delta );
if ( (delta+1) % 2 )
bi = 1;
else
bi = -1;
while ( degree( pi1, v ) > 0 )
{
pi2 = psr( pi, pi1, v );
pi2 = pi2 / bi;
pi = pi1; pi1 = pi2;
if ( degree( pi1, v ) > 0 )
{
delta = degree( pi, v ) - degree( pi1, v );
if ( (delta+1) % 2 )
bi = LC( pi, v ) * power( Hi, delta );
else
bi = -LC( pi, v ) * power( Hi, delta );
Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
}
}
if ( degree( pi1, v ) == 0 )
return C;
else
return C * pp( pi );
}
/** CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
*
* gcd_poly() - calculate polynomial gcd.
*
* This is the dispatcher for polynomial gcd calculation.
* Different gcd variants get called depending the input, characteristic, and
* on switches (cf_defs.h)
*
* With the current settings from Singular (i.e. SW_USE_EZGCD= on,
* SW_USE_EZGCD_P= on, SW_USE_CHINREM_GCD= on, the EZ GCD variants are the
* default algorithms for multivariate polynomial GCD computations)
*
* @sa gcd(), cf_defs.h
*
**/
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
{
CanonicalForm fc, gc;
bool fc_isUnivariate=f.isUnivariate();
bool gc_isUnivariate=g.isUnivariate();
bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
fc = f;
gc = g;
int ch=getCharacteristic();
if ( ch != 0 )
{
if (0) {} // dummy, to be able to build without NTL and FLINT
#if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
if ( isOn( SW_USE_FL_GCD_P)
&& (CFFactory::gettype() != GaloisFieldDomain)
#ifdef HAVE_NTL
&& (ch>10) // if we have NTL: it is better for char <11
#endif
&&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
{
return gcdFlintMP_Zp(fc,gc);
}
#endif
#ifdef HAVE_NTL
if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
{
fc= EZGCD_P (fc, gc);
}
#endif
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
{
Variable a;
if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
fc=modGCDFq (fc, gc, a);
else if (CFFactory::gettype() == GaloisFieldDomain)
fc=modGCDGF (fc, gc);
else
fc=modGCDFp (fc, gc);
}
#endif
else
fc = gcd_poly_p( fc, gc );
}
else if (!fc_and_gc_Univariate) /* && char==0*/
{
#if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
if (( isOn( SW_USE_FL_GCD_0) )
&&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
{
return gcdFlintMP_QQ(fc,gc);
}
else
#endif
#ifdef HAVE_NTL
if ( isOn( SW_USE_EZGCD ) )
fc= ezgcd (fc, gc);
else
#endif
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
if (isOn(SW_USE_CHINREM_GCD))
fc = modGCDZ( fc, gc);
else
#endif
{
fc = gcd_poly_0( fc, gc );
}
}
else
{
fc = gcd_poly_0( fc, gc );
}
if ((ch>0)&&(!hasAlgVar(fc))) fc/=fc.lc();
return fc;
}
/** static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
*
* cf_content() - return gcd(g, content(f)).
*
* content(f) is calculated with respect to f's main variable.
*
* @sa gcd(), content(), content( CF, Variable ).
*
**/
static CanonicalForm
cf_content ( const CanonicalForm & f, const CanonicalForm & g )
{
if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
{
CFIterator i = f;
CanonicalForm result = g;
while ( i.hasTerms() && ! result.isOne() )
{
result = gcd( i.coeff(), result );
i++;
}
return result;
}
else
return abs( f );
}
/** CanonicalForm content ( const CanonicalForm & f )
*
* content() - return content(f) with respect to main variable.
*
* Normalizes result.
*
**/
CanonicalForm
content ( const CanonicalForm & f )
{
if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
{
CFIterator i = f;
CanonicalForm result = abs( i.coeff() );
i++;
while ( i.hasTerms() && ! result.isOne() )
{
result = gcd( i.coeff(), result );
i++;
}
return result;
}
else
return abs( f );
}
/** CanonicalForm content ( const CanonicalForm & f, const Variable & x )
*
* content() - return content(f) with respect to x.
*
* x should be a polynomial variable.
*
**/
CanonicalForm
content ( const CanonicalForm & f, const Variable & x )
{
if (f.inBaseDomain()) return f;
ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
Variable y = f.mvar();
if ( y == x )
return cf_content( f, 0 );
else if ( y < x )
return f;
else
return swapvar( content( swapvar( f, y, x ), y ), y, x );
}
/** CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
*
* vcontent() - return content of f with repect to variables >= x.
*
* The content is recursively calculated over all coefficients in
* f having level less than x. x should be a polynomial
* variable.
*
**/
CanonicalForm
vcontent ( const CanonicalForm & f, const Variable & x )
{
ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
if ( f.mvar() <= x )
return content( f, x );
else {
CFIterator i;
CanonicalForm d = 0;
for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
d = gcd( d, vcontent( i.coeff(), x ) );
return d;
}
}
/** CanonicalForm pp ( const CanonicalForm & f )
*
* pp() - return primitive part of f.
*
* Returns zero if f equals zero, otherwise f / content(f).
*
**/
CanonicalForm
pp ( const CanonicalForm & f )
{
if ( f.isZero() )
return f;
else
return f / content( f );
}
CanonicalForm
gcd ( const CanonicalForm & f, const CanonicalForm & g )
{
bool b = f.isZero();
if ( b || g.isZero() )
{
if ( b )
return abs( g );
else
return abs( f );
}
if ( f.inPolyDomain() || g.inPolyDomain() )
{
if ( f.mvar() != g.mvar() )
{
if ( f.mvar() > g.mvar() )
return cf_content( f, g );
else
return cf_content( g, f );
}
if (isOn(SW_USE_QGCD))
{
Variable m;
if (
(getCharacteristic() == 0) &&
(hasFirstAlgVar(f,m) || hasFirstAlgVar(g,m))
)
{
bool on_rational = isOn(SW_RATIONAL);
CanonicalForm r=QGCD(f,g);
On(SW_RATIONAL);
CanonicalForm cdF = bCommonDen( r );
if (!on_rational) Off(SW_RATIONAL);
return cdF*r;
}
}
if ( f.inExtension() && getReduce( f.mvar() ) )
return CanonicalForm(1);
else
{
if ( fdivides( f, g ) )
return abs( f );
else if ( fdivides( g, f ) )
return abs( g );
if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
{
CanonicalForm d;
d = gcd_poly( f, g );
return abs( d );
}
else
{
CanonicalForm cdF = bCommonDen( f );
CanonicalForm cdG = bCommonDen( g );
CanonicalForm F = f * cdF, G = g * cdG;
Off( SW_RATIONAL );
CanonicalForm l = gcd_poly( F, G );
On( SW_RATIONAL );
return abs( l );
}
}
}
if ( f.inBaseDomain() && g.inBaseDomain() )
return bgcd( f, g );
else
return 1;
}
/** CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
*
* lcm() - return least common multiple of f and g.
*
* The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).
*
* Returns zero if one of f or g equals zero.
*
**/
CanonicalForm
lcm ( const CanonicalForm & f, const CanonicalForm & g )
{
if ( f.isZero() || g.isZero() )
return 0;
else
return ( f / gcd( f, g ) ) * g;
}
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition FLINTconvert.cc:208
convertFmpz_poly_t2FacCF
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
Definition FLINTconvert.cc:172
convertFacCF2Fmpz_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition FLINTconvert.cc:146
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition NTLconvert.cc:691
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition NTLconvert.cc:285
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
NTLconvert.h
Conversion to and from NTL.
bgcd
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ).
Definition canonicalform.cc:1648
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
EZGCD_P
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
Definition cfEzgcd.cc:876
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition cfEzgcd.cc:498
i
int i
Definition cfEzgcd.cc:132
cfEzgcd.h
Extended Zassenhaus GCD over finite fields and Z.
QGCD
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition cfGcdAlgExt.cc:731
cfGcdAlgExt.h
GCD over Q(a).
gcd_test_one
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition cfGcdUtil.cc:25
modGCDFq
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition cfModGcd.cc:479
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
cl
cl
Definition cfModGcd.cc:4108
g
g
Definition cfModGcd.cc:4098
maxNumVars
int maxNumVars
Definition cfModGcd.cc:4138
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition cfModGcd.cc:1224
modGCDGF
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms forComputer Algebra" by Geddes...
Definition cfModGcd.cc:873
b
CanonicalForm b
Definition cfModGcd.cc:4111
cg
CanonicalForm cg
Definition cfModGcd.cc:4091
cfModGcd.h
modular and sparse modular GCD algorithms over finite fields and Z.
modGCDZ
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
cfSubResGcd.h
subresultant pseudo remainder sequence GCD over finite fields and Z
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_algorithm.cc:536
cf_algorithm.h
declarations of higher level algorithms.
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
chineseRemainder
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,...
Definition cf_chinese.cc:57
psr
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
cf_assert.h
assertions for Factory
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
cf_defs.h
factory switches.
SW_USE_QGCD
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition cf_defs.h:43
SW_USE_CHINREM_GCD
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition cf_defs.h:41
SW_USE_FL_GCD_P
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition cf_defs.h:47
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition cf_defs.h:37
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
SW_USE_FF_MOD_GCD
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition cf_defs.h:45
SW_USE_EZGCD
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition cf_defs.h:35
SW_USE_FL_GCD_0
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition cf_defs.h:49
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
gcd_poly_0
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:417
cf_content
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_gcd.cc:578
gcd_univar_flintp
static CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
Definition cf_gcd.cc:81
gcd_poly_univar0
static CanonicalForm gcd_poly_univar0(const CanonicalForm &F, const CanonicalForm &G, bool primitive)
Definition cf_gcd.cc:178
content
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
balance_p
static CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
Definition cf_gcd.cc:149
gcd_poly
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g ).
Definition cf_gcd.cc:492
isPurePoly
bool isPurePoly(const CanonicalForm &)
Definition cf_factor.cc:248
vcontent
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ).
Definition cf_gcd.cc:653
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
Definition cf_factor.cc:103
gcd
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:685
icontent
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition cf_gcd.cc:49
pp
CanonicalForm pp(const CanonicalForm &f)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
gcd_poly_p
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:264
lcm
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g ).
Definition cf_gcd.cc:763
gcd_univar_flint0
static CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Definition cf_gcd.cc:94
cf_iter.h
Iterators for CanonicalForm's.
cf_getNumSmallPrimes
int cf_getNumSmallPrimes()
Definition cf_primes.cc:34
cf_getSmallPrime
int cf_getSmallPrime(int i)
Definition cf_primes.cc:28
cf_primes.h
access to prime tables
cf_reval.h
generate random evaluation points
f
FILE * f
Definition checklibs.c:9
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition canonicalform.cc:414
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition canonicalform.cc:337
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
Variable
factory's class for variables
Definition factory.h:127
debug.h
functions to print debug output
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
result
return result
Definition facAbsBiFact.cc:76
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:322
facAlgFuncUtil.h
Utility functions for factorization over algebraic function fields.
B
b *CanonicalForm B
Definition facBivar.cc:52
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
ftmpl_functions.h
some useful template functions.
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
D
#define D(A)
Definition gentable.cc:128
G
STATIC_VAR TreeM * G
Definition janet.cc:31
pi
#define pi
Definition libparse.cc:1145
R
#define R
Definition sirandom.c:27
M
#define M
Definition sirandom.c:25
timing.h
getReduce
bool getReduce(const Variable &alpha)
Definition variable.cc:232