Loading...
Searching...
No Matches
fac_util.cc File Reference
`#include "config.h"`
`#include "cf_assert.h"`
`#include "cf_defs.h"`
`#include "canonicalform.h"`
`#include "cf_iter.h"`
`#include "fac_util.h"`
`#include "cfUnivarGcd.h"`

Go to the source code of this file.

## Functions

static CanonicalForm | mappk (const CanonicalForm &)
static CanonicalForm | mappksymmetric (const CanonicalForm &)
CanonicalForm | replaceLc (const CanonicalForm &f, const CanonicalForm &c)
CanonicalForm | remainder (const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
CanonicalForm | prod (const CFArray &a, int f, int l)
CanonicalForm | prod (const CFArray &a)
void | extgcd (const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)

## Variables

STATIC_INST_VAR CanonicalForm | PK
STATIC_INST_VAR CanonicalForm | PKHALF

## Function Documentation

## extgcd()

void extgcd | ( | const CanonicalForm & | a,
|  | const CanonicalForm & | b,
|  | CanonicalForm & | S,
|  | CanonicalForm & | T,
|  | const modpk & | pk )

Definition at line 183 of file fac_util.cc.

{
int p = pk.getp(), k = pk.getk(), j;
CanonicalForm amodp, bmodp, smodp, tmodp, s, t, sigma, tau, e;
CanonicalForm modulus = p, sigmat, taut, q;
setCharacteristic( p );
{
amodp = mapinto( a ); bmodp = mapinto( b );
(void)extgcd( amodp, bmodp, smodp, tmodp );
}
setCharacteristic( 0 );
s = mapinto( smodp ); t = mapinto( tmodp );
for ( j = 1; j < k; j++ ) {
e = ( 1 - s * a - t * b ) / modulus;
setCharacteristic( p );
{
e = mapinto( e );
sigmat = smodp * e;
taut = tmodp * e;
divrem( sigmat, bmodp, q, sigma );
tau = taut + q * amodp;
}
setCharacteristic( 0 );
s += mapinto( sigma ) * modulus;
t += mapinto( tau ) * modulus;
modulus *= p;
}
S = s; T = t;
}
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1032
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
b
CanonicalForm b
Definition cfModGcd.cc:4111
tau
void tau(int **points, int sizePoints, int k)
Definition cfNewtonPolygon.cc:461
CanonicalForm
factory's main class
Definition canonicalform.h:86
modpk::getk
int getk() const
Definition fac_util.h:36
modpk::getp
int getp() const
Definition fac_util.h:35
s
const CanonicalForm int s
Definition facAbsFact.cc:51
j
int j
Definition facHensel.cc:110
extgcd
void extgcd(const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
Definition fac_util.cc:183
T
STATIC_VAR jList * T
Definition janet.cc:30

## mappk()

CanonicalForm mappk | ( | const CanonicalForm & | f | ) |

static

Definition at line 109 of file fac_util.cc.

{
return mod( f, PK );
}
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
f
FILE * f
Definition checklibs.c:9
PK
STATIC_INST_VAR CanonicalForm PK
Definition fac_util.cc:15

## mappksymmetric()

CanonicalForm mappksymmetric | ( | const CanonicalForm & | f | ) |

static

Definition at line 99 of file fac_util.cc.

{
CanonicalForm result = mod( f, PK );
if ( result > PKHALF )
return result - PK;
else
return result;
}
result
return result
Definition facAbsBiFact.cc:76
PKHALF
STATIC_INST_VAR CanonicalForm PKHALF
Definition fac_util.cc:15

## prod() [1/2]

CanonicalForm prod | ( | const CFArray & | a | ) |

Definition at line 177 of file fac_util.cc.

{
return prod( a, a.min(), a.max() );
}
Array::max
int max() const
Definition ftmpl_array.cc:104
Array::min
int min() const
Definition ftmpl_array.cc:98
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100

## prod() [2/2]

CanonicalForm prod | ( | const CFArray & | a,
|  | int | f,
|  | int | l )

Definition at line 166 of file fac_util.cc.

{
if ( f < a.min() ) f = a.min();
if ( l > a.max() ) l = a.max();
CanonicalForm p = 1;
for ( int i = f; i <= l; i++ )
p *= a[i];
return p;
}
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132

## remainder()

CanonicalForm remainder | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const modpk & | pk )

Definition at line 115 of file fac_util.cc.

{
ASSERT( (f.inCoeffDomain() || f.isUnivariate()) && (g.inCoeffDomain() || g.isUnivariate()) && (f.inCoeffDomain() || g.inCoeffDomain() || f.mvar() == g.mvar()), "can not build remainder" );
if ( f.inCoeffDomain() )
if ( g.inCoeffDomain() )
return pk( f % g );
else
return pk( f );
else {
Variable x = f.mvar();
CanonicalForm result = f;
int degg = g.degree();
CanonicalForm invlcg = pk.inverse( g.lc() );
CanonicalForm gg = pk( g*invlcg );
if((gg.lc().isOne()))
{
while ( result.degree() >= degg )
{
result -= pk(lc( result ) * gg) * power( x, result.degree() - degg );
result=pk(result);
}
}
else
// no inverse found
{
CanonicalForm ic=icontent(g);
if (!ic.isOne())
{
gg=g/ic;
return remainder(f,gg,pk);
}
while ( result.degree() >= degg )
{
if (gg.lc().isZero()) return result;
CanonicalForm lcgf = result.lc() / gg.lc();
if (lcgf.inZ())
gg = pk( g*lcgf );
else
{
//printf("!\n\n");
return result;
}
result -= gg * power( x, result.degree() - degg );
result=pk(result);
}
}
return result;
}
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
x
Variable x
Definition cfModGcd.cc:4090
g
g
Definition cfModGcd.cc:4098
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inZ
bool inZ() const
predicates
Definition canonicalform.cc:69
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition canonicalform.cc:337
Variable
factory's class for variables
Definition factory.h:127
modpk::inverse
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition fac_util.cc:59
degg
int degg
Definition facAlgExt.cc:64
remainder
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition fac_util.cc:115

## replaceLc()

CanonicalForm replaceLc | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | c )

Definition at line 90 of file fac_util.cc.

{
if ( f.inCoeffDomain() )
return c;
else
return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310

## Variable Documentation

## PK

STATIC_INST_VAR CanonicalForm PK

Definition at line 15 of file fac_util.cc.

## PKHALF

STATIC_INST_VAR CanonicalForm PKHALF

Definition at line 15 of file fac_util.cc.