Loading...
Searching...
No Matches
facAlgFuncUtil.cc File Reference

This file provides utility functions to factorize polynomials over alg. More...

`#include "config.h"`
`#include "cf_assert.h"`
`#include "canonicalform.h"`
`#include "facAlgFuncUtil.h"`
`#include "cfCharSetsUtil.h"`
`#include "cf_random.h"`
`#include "cf_irred.h"`
`#include "cf_algorithm.h"`
`#include "cf_util.h"`
`#include "cf_iter.h"`

Go to the source code of this file.

## Functions

CFFList | append (const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList | merge (const CFFList &Inputlist1, const CFFList &Inputlist2)
Varlist | varsInAs (const Varlist &uord, const CFList &Astar)
CanonicalForm | generateMipo (int degOfExt)
CanonicalForm | alg_lc (const CanonicalForm &f)
CanonicalForm | alg_LC (const CanonicalForm &f, int lev)
CanonicalForm | subst (const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm | backSubst (const CanonicalForm &F, const CFList &a, const CFList &b)
void | deflateDegree (const CanonicalForm &F, int &pExp, int n)
CanonicalForm | deflatePoly (const CanonicalForm &F, int exp)
CanonicalForm | deflatePoly (const CanonicalForm &F, int exps, int n)
CanonicalForm | inflatePoly (const CanonicalForm &F, int exp)
CanonicalForm | inflatePoly (const CanonicalForm &F, int exps, int n)
void | multiplicity (CFFList &factors, const CanonicalForm &F, const CFList &as)
int | hasAlgVar (const CanonicalForm &f, const Variable &v)
int | hasVar (const CanonicalForm &f, const Variable &v)
int | hasAlgVar (const CanonicalForm &f)
void | psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, CanonicalForm &multiplier, const Variable &x)
| pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
CanonicalForm | Sprem (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &m, CanonicalForm &q)
CanonicalForm | divide (const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
bool | isInseparable (const CFList &Astar)
int | getDegOfExt (IntList &degreelist, int n)
CanonicalForm | QuasiInverse (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm | evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
CanonicalForm | evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH, const Variable &v)
| evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)

## Detailed Description

This file provides utility functions to factorize polynomials over alg.

function fields

Note
  some of the code is code from libfac or derived from code from libfac. Libfac is written by M. Messollen. See also COPYING for license information and README for general information on characteristic sets.

Author
  Martin Lee

Definition in file facAlgFuncUtil.cc.

## Function Documentation

## alg_LC()

CanonicalForm alg_LC | ( | const CanonicalForm & | f,
|  | int | lev )

Definition at line 110 of file facAlgFuncUtil.cc.

{
CanonicalForm result= f;
while (result.level() > lev)
result= LC (result);
return result;
}
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
f
FILE * f
Definition checklibs.c:9
CanonicalForm
factory's main class
Definition canonicalform.h:86
result
return result
Definition facAbsBiFact.cc:76

## alg_lc()

CanonicalForm alg_lc | ( | const CanonicalForm & | f | ) |

Definition at line 100 of file facAlgFuncUtil.cc.

{
if (f.level()>0)
{
return alg_lc(f.LC());
}
return f;
}
alg_lc
CanonicalForm alg_lc(const CanonicalForm &f)
Definition facAlgFuncUtil.cc:100

## append()

CFFList append | ( | const CFFList & | Inputlist,
|  | const CFFactor & | TheFactor )

Definition at line 32 of file facAlgFuncUtil.cc.

{
CFFList Outputlist;
CFFactor copy;
CFFListIterator i;
int exp=0;
for (i= Inputlist; i.hasItem() ; i++)
{
copy= i.getItem();
if (copy.factor() == TheFactor.factor())
exp += copy.exp();
else
Outputlist.append(copy);
}
Outputlist.append (CFFactor (TheFactor.factor(), exp + TheFactor.exp()));
return Outputlist;
}
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
i
int i
Definition cfEzgcd.cc:132
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::append
void append(const T &)
Definition ftmpl_list.cc:256
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition facFqBivarUtil.cc:364
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349

## backSubst()

CanonicalForm backSubst | ( | const CanonicalForm & | F,
|  | const CFList & | a,
|  | const CFList & | b )

Definition at line 178 of file facAlgFuncUtil.cc.

{
ASSERT (a.length() == b.length() - 1, "wrong length of lists in backSubst");
CanonicalForm result= F;
Variable tmp;
CFList tmp2= b;
tmp= tmp2.getLast().mvar();
tmp2.removeLast();
for (CFListIterator iter= a; iter.hasItem(); iter++)
{
result= result (tmp+iter.getItem()*tmp2.getLast().mvar(), tmp);
tmp= tmp2.getLast().mvar();
tmp2.removeLast();
}
return result;
}
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
b
CanonicalForm b
Definition cfModGcd.cc:4111
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
List::length
int length() const
Definition ftmpl_list.cc:273
Variable
factory's class for variables
Definition factory.h:127
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
tmp2
CFList tmp2
Definition facFqBivar.cc:75

## deflateDegree()

void deflateDegree | ( | const CanonicalForm & | F,
|  | int & | pExp,
|  | int | n )

Definition at line 195 of file facAlgFuncUtil.cc.

{
if (n == 0 || n > F.level())
{
pExp= -1;
return;
}
if (F.level() == n)
{
ASSERT (F.deriv().isZero(), "derivative of F is not zero");
CFIterator i= F;
int g= 0;
for (; i.hasTerms(); i++)
g= igcd (g, i.exp());
int count= 0;
int p= getCharacteristic();
while ((g >= p) && (g != 0) && (g % p == 0))
{
g /= p;
count++;
}
pExp= count;
}
else
{
CFIterator i= F;
deflateDegree (i.coeff(), pExp, n);
i++;
int tmp= pExp;
for (; i.hasTerms(); i++)
{
deflateDegree (i.coeff(), pExp, n);
if (tmp == -1)
tmp= pExp;
else if (tmp != -1 && pExp != -1)
pExp= (pExp < tmp) ? pExp : tmp;
else
pExp= tmp;
}
}
}
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
igcd
int igcd(int a, int b)
Definition cf_util.cc:56
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::deriv
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
Definition canonicalform.cc:1300
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
deflateDegree
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
Definition facAlgFuncUtil.cc:195
count
int status int void size_t count
Definition si_signals.h:69

## deflatePoly() [1/2]

CanonicalForm deflatePoly | ( | const CanonicalForm & | F,
|  | int | exp )

Definition at line 238 of file facAlgFuncUtil.cc.

{
if (exp == 0)
return F;
int p= getCharacteristic();
int pToExp= ipower (p, exp);
Variable x=F.mvar();
CanonicalForm result= 0;
for (CFIterator i= F; i.hasTerms(); i++)
result += i.coeff()*power (x, i.exp()/pToExp);
return result;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
x
Variable x
Definition cfModGcd.cc:4090
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
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

## deflatePoly() [2/2]

CanonicalForm deflatePoly | ( | const CanonicalForm & | F,
|  | int | exps,
|  | int | n )

Definition at line 251 of file facAlgFuncUtil.cc.

{
if (n == 0 || exps <= 0 || F.level() < n)
return F;
if (F.level() == n)
return deflatePoly (F, exps);
else
{
CanonicalForm result= 0;
for (CFIterator i= F; i.hasTerms(); i++)
result += deflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
return result;
}
}
deflatePoly
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
Definition facAlgFuncUtil.cc:238

## divide()

CanonicalForm divide | ( | const CanonicalForm & | ff,
|  | const CanonicalForm & | f,
|  | const CFList & | as )

Definition at line 496 of file facAlgFuncUtil.cc.

{
CanonicalForm r, m, q;
if (f.inCoeffDomain())
{
bool isRat= isOn(SW_RATIONAL);
if (getCharacteristic() == 0)
On(SW_RATIONAL);
q= ff/f;
if (!isRat && getCharacteristic() == 0)
Off(SW_RATIONAL);
}
else
r= Sprem (ff, f, m, q);
r= Prem (q, as);
return r;
}
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
Prem
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Definition cfCharSetsUtil.cc:616
m
int m
Definition cfEzgcd.cc:128
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
Sprem
CanonicalForm Sprem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &m, CanonicalForm &q)
Definition facAlgFuncUtil.cc:429

## evaluate() [1/2]

CanonicalForm evaluate | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const CanonicalForm & | h,
|  | const CanonicalForm & | powH )

Definition at line 636 of file facAlgFuncUtil.cc.

{
if (f.inCoeffDomain())
return f;
CFIterator i= f;
int lastExp = i.exp();
CanonicalForm result = i.coeff()*powH;
i++;
while (i.hasTerms())
{
int i_exp= i.exp();
if ((lastExp - i_exp) == 1)
{
result *= g;
result /= h;
}
else
{
result *= power (g, lastExp - i_exp);
result /= power (h, lastExp - i_exp);
}
result += i.coeff()*powH;
lastExp = i_exp;
i++;
}
if (lastExp != 0)
{
result *= power (g, lastExp);
result /= power (h, lastExp);
}
return result;
}
h
STATIC_VAR Poly * h
Definition janet.cc:971

## evaluate() [2/2]

CanonicalForm evaluate | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const CanonicalForm & | h,
|  | const CanonicalForm & | powH,
|  | const Variable & | v )

evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)

Definition at line 673 of file facAlgFuncUtil.cc.

{
if (f.inCoeffDomain())
{
return f*powH;
}
Variable x = f.mvar();
if ( v > x )
return f*powH;
else if ( v == x )
return evaluate (f, g, h, powH);
// v is less than main variable of f
CanonicalForm result= 0;
for (CFIterator i= f; i.hasTerms(); i++)
result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
return result;
}
evaluate
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition cfModGcd.cc:2039
evaluate
CanonicalForm evaluate(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
Definition facAlgFuncUtil.cc:636
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39

## generateMipo()

CanonicalForm generateMipo | ( | int | degOfExt | ) |

Definition at line 90 of file facAlgFuncUtil.cc.

{
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
return randomIrredpoly (degOfExt, Variable (1));
#else
FFRandom gen;
return find_irreducible (degOfExt, gen, Variable (1));
#endif
}
randomIrredpoly
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
find_irreducible
CanonicalForm find_irreducible(int deg, CFRandom &gen, const Variable &x)
generate a random irreducible polynomial in x of degree deg
FFRandom
generate random elements in F_p
Definition cf_random.h:44

## getDegOfExt()

int getDegOfExt | ( | IntList & | degreelist,
|  | int | n )

Definition at line 539 of file facAlgFuncUtil.cc.

{
int charac= getCharacteristic();
setCharacteristic(0); // need it for k !
int k= 1, m= 1, length= degreelist.length();
IntListIterator i;
for (i= degreelist; i.hasItem(); i++)
m= m*i.getItem();
int q= charac;
while (q <= ((n*m)*(n*m)/2))
{
k= k+1;
q= q*charac;
}
int l= 0;
do
{
for (i= degreelist; i.hasItem(); i++)
{
l= l + 1;
if (igcd (k, i.getItem()) == 1)
{
if (l == length)
{
setCharacteristic (charac);
return k;
}
}
else
break;
}
k= k + 1;
l= 0;
}
while (1);
}
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
IntListIterator
ListIterator< int > IntListIterator
Definition canonicalform.h:402
l
int l
Definition cfEzgcd.cc:100
k
int k
Definition cfEzgcd.cc:99
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257

## hasAlgVar() [1/2]

int hasAlgVar | ( | const CanonicalForm & | f | ) |

Definition at line 370 of file facAlgFuncUtil.cc.

{
if (f.inBaseDomain())
return 0;
if (f.inExtension())
{
return 1;
}
if (f.inPolyDomain())
{
for (CFIterator i= f; i.hasTerms(); i++)
{
if (hasAlgVar (i.coeff()))
return 1;
}
}
return 0;
}
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:322

## hasAlgVar() [2/2]

int hasAlgVar | ( | const CanonicalForm & | f,
|  | const Variable & | v )

Definition at line 322 of file facAlgFuncUtil.cc.

{
if (f.inBaseDomain())
return 0;
if (f.inCoeffDomain())
{
if (f.mvar() == v)
return 1;
return hasAlgVar (f.LC(), v);
}
if (f.inPolyDomain())
{
if (hasAlgVar(f.LC(), v))
return 1;
for (CFIterator i= f; i.hasTerms(); i++)
{
if (hasAlgVar (i.coeff(), v))
return 1;
}
}
return 0;
}

## hasVar()

int hasVar | ( | const CanonicalForm & | f,
|  | const Variable & | v )

Definition at line 345 of file facAlgFuncUtil.cc.

{
if (f.inBaseDomain())
return 0;
if (f.inCoeffDomain())
{
if (f.mvar() == v)
return 1;
return hasAlgVar (f.LC(), v);
}
if (f.inPolyDomain())
{
if (f.mvar() == v)
return 1;
if (hasVar (f.LC(), v))
return 1;
for (CFIterator i= f; i.hasTerms(); i++)
{
if (hasVar (i.coeff(), v))
return 1;
}
}
return 0;
}
hasVar
int hasVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:345

## inflatePoly() [1/2]

CanonicalForm inflatePoly | ( | const CanonicalForm & | F,
|  | int | exp )

Definition at line 266 of file facAlgFuncUtil.cc.

{
if (exp == 0)
return F;
int p= getCharacteristic();
int pToExp= ipower (p, exp);
Variable x=F.mvar();
CanonicalForm result= 0;
for (CFIterator i= F; i.hasTerms(); i++)
result += i.coeff()*power (x, i.exp()*pToExp);
return result;
}

## inflatePoly() [2/2]

CanonicalForm inflatePoly | ( | const CanonicalForm & | F,
|  | int | exps,
|  | int | n )

Definition at line 279 of file facAlgFuncUtil.cc.

{
if (n == 0 || exps <= 0 || F.level() < n)
return F;
if (F.level() == n)
return inflatePoly (F, exps);
else
{
CanonicalForm result= 0;
for (CFIterator i= F; i.hasTerms(); i++)
result += inflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
return result;
}
}
inflatePoly
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
Definition facAlgFuncUtil.cc:266

## isInseparable()

bool isInseparable | ( | const CFList & | Astar | ) |

Definition at line 518 of file facAlgFuncUtil.cc.

{
CanonicalForm elem;
if (Astar.length() == 0)
return false;
for (CFListIterator i= Astar; i.hasItem(); i++)
{
elem= i.getItem();
if (elem.deriv().isZero())
return true;
}
return false;
}

## merge()

CFFList merge | ( | const CFFList & | Inputlist1,
|  | const CFFList & | Inputlist2 )

Definition at line 52 of file facAlgFuncUtil.cc.

{
CFFList Outputlist;
CFFListIterator i;
for (i= Inputlist1; i.hasItem(); i++)
Outputlist= append (Outputlist, i.getItem());
for (i= Inputlist2; i.hasItem() ; i++)
Outputlist= append (Outputlist, i.getItem());
return Outputlist;
}
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32

## multiplicity()

void multiplicity | ( | CFFList & | factors,
|  | const CanonicalForm & | F,
|  | const CFList & | as )

Definition at line 295 of file facAlgFuncUtil.cc.

{
CanonicalForm G= F;
Variable x= F.mvar();
CanonicalForm q, r;
int count= -1;
for (CFFListIterator iter=factors; iter.hasItem(); iter++)
{
count= -1;
if (iter.getItem().factor().inCoeffDomain())
continue;
while (1)
{
psqr (G, iter.getItem().factor(), q, r, x);
q= Prem (q, as);
r= Prem (r, as);
if (!r.isZero())
break;
count++;
G= q;
}
iter.getItem()= CFFactor (iter.getItem().factor(),
iter.getItem().exp() + count);
}
}
psqr
void psqr(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, CanonicalForm &multiplier, const Variable &x)
pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
Definition facAlgFuncUtil.cc:391
G
STATIC_VAR TreeM * G
Definition janet.cc:31

## psqr()

void psqr | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | CanonicalForm & | q,
|  | CanonicalForm & | r,
|  | CanonicalForm & | multiplier,
|  | const Variable & | x )

pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r

Definition at line 391 of file facAlgFuncUtil.cc.

{
ASSERT( x.level() > 0, "type error: polynomial variable expected" );
ASSERT( ! g.isZero(), "math error: division by zero" );
// swap variables such that x's level is larger or equal
// than both f's and g's levels.
Variable X;
if (f.level() > g.level())
X= f.mvar();
else
X= g.mvar();
if (X.level() < x.level())
X= x;
CanonicalForm F= swapvar (f, x, X);
CanonicalForm G= swapvar (g, x, X);
// now, we have to calculate the pseudo remainder of F and G
// w.r.t. X
int fDegree= degree (F, X);
int gDegree= degree (G, X);
if (fDegree < 0 || fDegree < gDegree)
{
q= 0;
r= f;
}
else
{
CanonicalForm LCG= LC (G, X);
multiplier= power (LCG, fDegree - gDegree + 1);
divrem (multiplier*F, G, q, r);
q= swapvar (q, x, X);
r= swapvar (r, x, X);
}
}
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1032
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
Variable::level
int level() const
Definition factory.h:143

## QuasiInverse()

CanonicalForm QuasiInverse | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const Variable & | x )

Definition at line 578 of file facAlgFuncUtil.cc.

{
CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
bool isRat= isOn (SW_RATIONAL);
pi= f;
pi1= g;
if (isRat)
{
pi *= bCommonDen (pi);
pi1 *= bCommonDen (pi1);
}
CanonicalForm m,tmp;
if (isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
pi= pi/content (pi,x);
pi1= pi1/content (pi1,x);
t0= 0;
t1= 1;
bi= 1;
int delta= degree (f, x) - degree (g, x);
Hi= power (LC (pi1, x), delta);
if ( (delta+1) % 2 )
bi = 1;
else
bi = -1;
while (degree (pi1,x) > 0)
{
psqr (pi, pi1, q, pi2, m, x);
pi2 /= bi;
tmp= t1;
t1= t0*m - t1*q;
t0= tmp;
t1 /= bi;
pi= pi1;
pi1= pi2;
if (degree (pi1, x) > 0)
{
delta= degree (pi, x) - degree (pi1, x);
if ((delta + 1) % 2)
bi= LC (pi, x)*power (Hi, delta);
else
bi= -LC (pi, x)*power (Hi, delta);
Hi= power (LC (pi1, x), delta)/power (Hi, delta - 1);
}
}
t1 /= gcd (pi1, t1);
if (isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
return t1;
}
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
pi
#define pi
Definition libparse.cc:1145
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## Sprem()

CanonicalForm Sprem | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | CanonicalForm & | m,
|  | CanonicalForm & | q )

Definition at line 429 of file facAlgFuncUtil.cc.

{
CanonicalForm ff, gg, l, test, retvalue;
int df, dg,n;
bool reord;
Variable vf, vg, v;
if ((vf = f.mvar()) < (vg = g.mvar()))
{
m= 0;
q= 0;
return f;
}
else
{
if ( vf == vg )
{
ff= f;
gg= g;
reord= false;
v= vg; // == x
}
else
{
v= Variable (f.level() + 1);
ff= swapvar (f, vg, v); // == r
gg= swapvar (g, vg, v); // == v
reord=true;
}
dg= degree (gg, v); // == dv
df= degree (ff, v); // == dr
if (dg <= df)
{
l= LC (gg);
gg= gg - LC(gg)*power(v,dg);
}
else
l = 1;
n= 0;
while ((dg <= df) && (!ff.isZero()))
{
test= gg*LC (ff)*power (v, df - dg);
if (df == 0)
ff= 0;
else
ff= ff - LC(ff)*power(v,df);
ff= l*ff - test;
df= degree (ff, v);
n++;
}
if (reord)
retvalue= swapvar (ff, vg, v);
else
retvalue= ff;
m= power (l, n);
if (fdivides (g, m*f - retvalue))
q= (m*f - retvalue)/g;
else
q= 0;
return retvalue;
}
}
test
CanonicalForm test
Definition cfModGcd.cc:4104
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
retvalue
static CanonicalForm * retvalue
Definition readcf.cc:126

## subst()

CanonicalForm subst | ( | const CanonicalForm & | f,
|  | const CFList & | a,
|  | const CFList & | b,
|  | const CanonicalForm & | Rstar,
|  | bool | isFunctionField )

Definition at line 120 of file facAlgFuncUtil.cc.

{
if (isFunctionField)
ASSERT ((a.length() - 1)*4 == b.length() || (a.length() == 1 && b.length() == 2), "wrong length of lists");
else
ASSERT ((a.length() - 1)*2 == b.length() || (a.length() == 1 && b.length() == 1), "lists of equal length expected");
CFListIterator j= b;
CanonicalForm result= f, tmp, powj, tmp3;
CFListIterator i= a;
CanonicalForm tmp1= i.getItem();
i++;
CanonicalForm tmp2= j.getItem();
j++;
for (;i.hasItem() && j.hasItem(); i++, j++)
{
if (!isFunctionField)
{
result= result (j.getItem(), i.getItem().mvar());
result= result (tmp2, tmp1.mvar());
tmp1= i.getItem();
j++;
if (j.hasItem())
tmp2= j.getItem();
}
else
{
tmp= j.getItem();
j++;
tmp3= j.getItem();
j++;
powj= power (j.getItem(), degree (result, i.getItem().mvar()));
result= evaluate (result, tmp3, j.getItem(), powj, i.getItem().mvar());
if (fdivides (powj, result, tmp3))
result= tmp3;
result /= vcontent (result, Variable (i.getItem().level() + 1));
powj= power (tmp, degree (result, tmp1.mvar()));
result= evaluate (result, tmp2, tmp, powj, tmp1.mvar());
if (fdivides (powj, result, tmp))
result= tmp;
result /= vcontent (result, Variable (tmp1.level() + 1));
tmp1= i.getItem();
j++;
if (j.hasItem())
tmp2= j.getItem();
}
}
result= Prem (result, CFList (Rstar));
result /= vcontent (result, Variable (Rstar.level() + 1));
return result;
}
vcontent
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ).
Definition cf_gcd.cc:653
tmp1
CFList tmp1
Definition facFqBivar.cc:75
j
int j
Definition facHensel.cc:110

## varsInAs()

Varlist varsInAs | ( | const Varlist & | uord,
|  | const CFList & | Astar )

Definition at line 66 of file facAlgFuncUtil.cc.

{
Varlist output;
CanonicalForm elem;
Variable x;
for (VarlistIterator i= uord; i.hasItem(); i++)
{
x= i.getItem();
for (CFListIterator j= Astar; j.hasItem(); j++ )
{
elem= j.getItem();
if (degree (elem, x) > 0) // x actually occures in Astar
{
output.append (x);
break;
}
}
}
return output;
}
VarlistIterator
ListIterator< Variable > VarlistIterator
Definition canonicalform.h:404
Varlist
List< Variable > Varlist
Definition canonicalform.h:403