My Project
Functions | Variables
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.

184 {
185  int p = pk.getp(), k = pk.getk(), j;
186  CanonicalForm amodp, bmodp, smodp, tmodp, s, t, sigma, tau, e;
187  CanonicalForm modulus = p, sigmat, taut, q;
188 
189  setCharacteristic( p );
190  {
191  amodp = mapinto( a ); bmodp = mapinto( b );
192  (void)extgcd( amodp, bmodp, smodp, tmodp );
193  }
194  setCharacteristic( 0 );
195  s = mapinto( smodp ); t = mapinto( tmodp );
196 
197  for ( j = 1; j < k; j++ ) {
198  e = ( 1 - s * a - t * b ) / modulus;
199  setCharacteristic( p );
200  {
201  e = mapinto( e );
202  sigmat = smodp * e;
203  taut = tmodp * e;
204  divrem( sigmat, bmodp, q, sigma );
205  tau = taut + q * amodp;
206  }
207  setCharacteristic( 0 );
208  s += mapinto( sigma ) * modulus;
209  t += mapinto( tau ) * modulus;
210  modulus *= p;
211  }
212  S = s; T = t;
213 }
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm mapinto(const CanonicalForm &f)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
void tau(int **points, int sizePoints, int k)
factory's main class
Definition: canonicalform.h:86
int getk() const
Definition: fac_util.h:36
int getp() const
Definition: fac_util.h:35
const CanonicalForm int s
Definition: facAbsFact.cc:51
int j
Definition: facHensel.cc:110
void extgcd(const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
Definition: fac_util.cc:183
STATIC_VAR jList * T
Definition: janet.cc:30

◆ mappk()

CanonicalForm mappk ( const CanonicalForm f)
static

Definition at line 109 of file fac_util.cc.

110 {
111  return mod( f, PK );
112 }
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
FILE * f
Definition: checklibs.c:9
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.

100 {
101  CanonicalForm result = mod( f, PK );
102  if ( result > PKHALF )
103  return result - PK;
104  else
105  return result;
106 }
return result
Definition: facAbsBiFact.cc:75
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.

178 {
179  return prod( a, a.min(), a.max() );
180 }
int max() const
Definition: ftmpl_array.cc:104
int min() const
Definition: ftmpl_array.cc:98
CanonicalForm prod(const CFArray &a, int f, int l)
Definition: fac_util.cc:166

◆ prod() [2/2]

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

Definition at line 166 of file fac_util.cc.

167 {
168  if ( f < a.min() ) f = a.min();
169  if ( l > a.max() ) l = a.max();
170  CanonicalForm p = 1;
171  for ( int i = f; i <= l; i++ )
172  p *= a[i];
173  return p;
174 }
int l
Definition: cfEzgcd.cc:100
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.

116 {
117  ASSERT( (f.inCoeffDomain() || f.isUnivariate()) && (g.inCoeffDomain() || g.isUnivariate()) && (f.inCoeffDomain() || g.inCoeffDomain() || f.mvar() == g.mvar()), "can not build remainder" );
118  if ( f.inCoeffDomain() )
119  if ( g.inCoeffDomain() )
120  return pk( f % g );
121  else
122  return pk( f );
123  else {
124  Variable x = f.mvar();
126  int degg = g.degree();
127  CanonicalForm invlcg = pk.inverse( g.lc() );
128  CanonicalForm gg = pk( g*invlcg );
129  if((gg.lc().isOne()))
130  {
131  while ( result.degree() >= degg )
132  {
133  result -= pk(lc( result ) * gg) * power( x, result.degree() - degg );
134  result=pk(result);
135  }
136  }
137  else
138  // no inverse found
139  {
141  if (!ic.isOne())
142  {
143  gg=g/ic;
144  return remainder(f,gg,pk);
145  }
146  while ( result.degree() >= degg )
147  {
148  if (gg.lc().isZero()) return result;
149  CanonicalForm lcgf = result.lc() / gg.lc();
150  if (lcgf.inZ())
151  gg = pk( g*lcgf );
152  else
153  {
154  //printf("!\n\n");
155  return result;
156  }
157  result -= gg * power( x, result.degree() - degg );
158  result=pk(result);
159  }
160  }
161  return result;
162  }
163 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CF_NO_INLINE bool isZero() const
CF_NO_INLINE bool isOne() const
bool inZ() const
predicates
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
factory's class for variables
Definition: factory.h:127
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:59
int degg
Definition: facAlgExt.cc:64
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.

91 {
92  if ( f.inCoeffDomain() )
93  return c;
94  else
95  return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
96 }
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

Variable Documentation

◆ PK

Definition at line 15 of file fac_util.cc.

◆ PKHALF

Definition at line 15 of file fac_util.cc.