Functions
cf_algorithm.cc File Reference
#include "config.h"
#include "cf_assert.h"
#include "cf_factory.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_algorithm.h"
#include "variable.h"
#include "cf_iter.h"
#include "templates/ftmpl_functions.h"
#include "cfGcdAlgExt.h"

Go to the source code of this file.

Functions

void out_cf (const char *s1, const CanonicalForm &f, const char *s2)
 cf_algorithm.cc - simple mathematical algorithms. More...
 
CanonicalForm psr (const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
void psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x ) More...
 
static CanonicalForm internalBCommonDen (const CanonicalForm &f)
 static CanonicalForm internalBCommonDen ( const CanonicalForm & f ) More...
 
CanonicalForm bCommonDen (const CanonicalForm &f)
 CanonicalForm bCommonDen ( const CanonicalForm & f ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g)
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &quot)
 same as fdivides if true returns quotient quot of g by f otherwise quot == 0 More...
 
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 More...
 
CanonicalForm maxNorm (const CanonicalForm &f)
 CanonicalForm maxNorm ( const CanonicalForm & f ) More...
 
CanonicalForm euclideanNorm (const CanonicalForm &f)
 CanonicalForm euclideanNorm ( const CanonicalForm & f ) More...
 

Function Documentation

◆ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm f)

CanonicalForm bCommonDen ( const CanonicalForm & f )

bCommonDen() - calculate multivariate common denominator of coefficients of `f'.

The common denominator is calculated with respect to all coefficients of `f' which are in a base domain. In other words, common_den( `f' ) * `f' is guaranteed to have integer coefficients only. The common denominator of zero is one.

Returns something non-trivial iff the current domain is Q.

Type info:

f: CurrentPP

Definition at line 293 of file cf_algorithm.cc.

294 {
295  if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) {
296  // otherwise `bgcd()' returns one
297  Off( SW_RATIONAL );
299  On( SW_RATIONAL );
300  return result;
301  } else
302  return CanonicalForm( 1 );
303 }
void Off(int sw)
switches
factory's main class
Definition: canonicalform.h:77
int getCharacteristic()
Definition: cf_char.cc:51
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
return result
Definition: facAbsBiFact.cc:76

◆ euclideanNorm()

CanonicalForm euclideanNorm ( const CanonicalForm f)

CanonicalForm euclideanNorm ( const CanonicalForm & f )

euclideanNorm() - return Euclidean norm of `f'.

Returns the largest integer smaller or equal norm(`f') = sqrt(sum( `f'[i]^2 )).

Type info:

f: UVPoly( Z )

Definition at line 563 of file cf_algorithm.cc.

564 {
565  ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
566  "type error: univariate poly over Z expected" );
567 
568  CanonicalForm result = 0;
569  for ( CFIterator i = f; i.hasTerms(); i++ ) {
570  CanonicalForm coeff = i.coeff();
571  result += coeff*coeff;
572  }
573  return sqrt( result );
574 }
factory's main class
Definition: canonicalform.h:77
bool inBaseDomain() const
bool isUnivariate() const
gmp_float sqrt(const gmp_float &a)
Definition: mpr_complex.cc:327
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
bool inZ() const
predicates
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76
CanonicalForm LC() const

◆ fdivides() [1/2]

bool fdivides ( const CanonicalForm f,
const CanonicalForm g 
)

bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )

fdivides() - check whether `f' divides `g'.

Returns true iff `f' divides `g'. Uses some extra heuristic to avoid polynomial division. Without the heuristic, the test essentialy looks like `divremt(g, f, q, r) && r.isZero()'.

Type info:

f, g: Current

Elements from prime power domains (or polynomials over such domains) are admissible if `f' (or lc(`f'), resp.) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since divisibility is a well-defined notion in arbitrary rings. Hence, we decided not to declare the weaker type `CurrentPP'.

Developers note:

One may consider the the test `fdivides( f.LC(), g.LC() )' in the main `if'-test superfluous since `divremt()' in the `if'-body repeats the test. However, `divremt()' does not use any heuristic to do so.

It seems not reasonable to call `fdivides()' from `divremt()' to check divisibility of leading coefficients. `fdivides()' is on a relatively high level compared to `divremt()'.

Definition at line 338 of file cf_algorithm.cc.

339 {
340  // trivial cases
341  if ( g.isZero() )
342  return true;
343  else if ( f.isZero() )
344  return false;
345 
346  if ( (f.inCoeffDomain() || g.inCoeffDomain())
347  && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
348  || (getCharacteristic() > 0) ))
349  {
350  // if we are in a field all elements not equal to zero are units
351  if ( f.inCoeffDomain() )
352  return true;
353  else
354  // g.inCoeffDomain()
355  return false;
356  }
357 
358  // we may assume now that both levels either equal LEVELBASE
359  // or are greater zero
360  int fLevel = f.level();
361  int gLevel = g.level();
362  if ( (gLevel > 0) && (fLevel == gLevel) )
363  // f and g are polynomials in the same main variable
364  if ( degree( f ) <= degree( g )
365  && fdivides( f.tailcoeff(), g.tailcoeff() )
366  && fdivides( f.LC(), g.LC() ) )
367  {
368  CanonicalForm q, r;
369  return divremt( g, f, q, r ) && r.isZero();
370  }
371  else
372  return false;
373  else if ( gLevel < fLevel )
374  // g is a coefficient w.r.t. f
375  return false;
376  else
377  {
378  // either f is a coefficient w.r.t. polynomial g or both
379  // f and g are from a base domain (should be Z or Z/p^n,
380  // then)
381  CanonicalForm q, r;
382  return divremt( g, f, q, r ) && r.isZero();
383  }
384 }
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
int getCharacteristic()
Definition: cf_char.cc:51
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
bool inCoeffDomain() const
CanonicalForm LC() const

◆ fdivides() [2/2]

bool fdivides ( const CanonicalForm f,
const CanonicalForm g,
CanonicalForm quot 
)

same as fdivides if true returns quotient quot of g by f otherwise quot == 0

Definition at line 388 of file cf_algorithm.cc.

389 {
390  quot= 0;
391  // trivial cases
392  if ( g.isZero() )
393  return true;
394  else if ( f.isZero() )
395  return false;
396 
397  if ( (f.inCoeffDomain() || g.inCoeffDomain())
398  && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
399  || (getCharacteristic() > 0) ))
400  {
401  // if we are in a field all elements not equal to zero are units
402  if ( f.inCoeffDomain() )
403  {
404  quot= g/f;
405  return true;
406  }
407  else
408  // g.inCoeffDomain()
409  return false;
410  }
411 
412  // we may assume now that both levels either equal LEVELBASE
413  // or are greater zero
414  int fLevel = f.level();
415  int gLevel = g.level();
416  if ( (gLevel > 0) && (fLevel == gLevel) )
417  // f and g are polynomials in the same main variable
418  if ( degree( f ) <= degree( g )
419  && fdivides( f.tailcoeff(), g.tailcoeff() )
420  && fdivides( f.LC(), g.LC() ) )
421  {
422  CanonicalForm q, r;
423  if (divremt( g, f, q, r ) && r.isZero())
424  {
425  quot= q;
426  return true;
427  }
428  else
429  return false;
430  }
431  else
432  return false;
433  else if ( gLevel < fLevel )
434  // g is a coefficient w.r.t. f
435  return false;
436  else
437  {
438  // either f is a coefficient w.r.t. polynomial g or both
439  // f and g are from a base domain (should be Z or Z/p^n,
440  // then)
441  CanonicalForm q, r;
442  if (divremt( g, f, q, r ) && r.isZero())
443  {
444  quot= q;
445  return true;
446  }
447  else
448  return false;
449  }
450 }
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
int getCharacteristic()
Definition: cf_char.cc:51
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
FILE * f
Definition: checklibs.c:9
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
bool inCoeffDomain() const
CanonicalForm LC() const

◆ internalBCommonDen()

static CanonicalForm internalBCommonDen ( const CanonicalForm f)
static

static CanonicalForm internalBCommonDen ( const CanonicalForm & f )

internalBCommonDen() - recursively calculate multivariate common denominator of coefficients of `f'.

Used by: bCommonDen()

Type info:

f: Poly( Q ) Switches: isOff( SW_RATIONAL )

Definition at line 262 of file cf_algorithm.cc.

263 {
264  if ( f.inBaseDomain() )
265  return f.den();
266  else {
267  CanonicalForm result = 1;
268  for ( CFIterator i = f; i.hasTerms(); i++ )
269  result = blcm( result, internalBCommonDen( i.coeff() ) );
270  return result;
271  }
272 }
factory&#39;s main class
Definition: canonicalform.h:77
bool inBaseDomain() const
CanonicalForm blcm(const CanonicalForm &f, const CanonicalForm &g)
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm den() const
den() returns the denominator of CO if CO is a rational number, 1 (from the current domain!) otherwis...
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
return result
Definition: facAbsBiFact.cc:76

◆ maxNorm()

CanonicalForm maxNorm ( const CanonicalForm f)

CanonicalForm maxNorm ( const CanonicalForm & f )

maxNorm() - return maximum norm of `f'.

That is, the base coefficient of `f' with the largest absolute value.

Valid for arbitrary polynomials over arbitrary domains, but most useful for multivariate polynomials over Z.

Type info:

f: CurrentPP

Definition at line 534 of file cf_algorithm.cc.

535 {
536  if ( f.inBaseDomain() )
537  return abs( f );
538  else {
539  CanonicalForm result = 0;
540  for ( CFIterator i = f; i.hasTerms(); i++ ) {
541  CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
542  if ( coeffMaxNorm > result )
543  result = coeffMaxNorm;
544  }
545  return result;
546  }
547 }
factory&#39;s main class
Definition: canonicalform.h:77
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool inBaseDomain() const
int i
Definition: cfEzgcd.cc:125
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
return result
Definition: facAbsBiFact.cc:76

◆ out_cf()

void out_cf ( const char *  s1,
const CanonicalForm f,
const char *  s2 
)

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in `cf_ops.cc', which are structural algorithms.

Definition at line 90 of file cf_factor.cc.

91 {
92  printf("%s",s1);
93  if (f.isZero()) printf("+0");
94  //else if (! f.inCoeffDomain() )
95  else if (! f.inBaseDomain() )
96  {
97  int l = f.level();
98  for ( CFIterator i = f; i.hasTerms(); i++ )
99  {
100  int e=i.exp();
101  if (i.coeff().isOne())
102  {
103  printf("+");
104  if (e==0) printf("1");
105  else
106  {
107  printf("v(%d)",l);
108  if (e!=1) printf("^%d",e);
109  }
110  }
111  else
112  {
113  out_cf("+(",i.coeff(),")");
114  if (e!=0)
115  {
116  printf("*v(%d)",l);
117  if (e!=1) printf("^%d",e);
118  }
119  }
120  }
121  }
122  else
123  {
124  if ( f.isImm() )
125  {
127  {
128  long a= imm2int (f.getval());
129  if ( a == gf_q )
130  printf ("+%ld", a);
131  else if ( a == 0L )
132  printf ("+1");
133  else if ( a == 1L )
134  printf ("+%c",gf_name);
135  else
136  {
137  printf ("+%c",gf_name);
138  printf ("^%ld",a);
139  }
140  }
141  else
142  printf("+%ld",f.intval());
143  }
144  else
145  {
146  #ifdef NOSTREAMIO
147  if (f.inZ())
148  {
149  mpz_t m;
150  gmp_numerator(f,m);
151  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
152  str = mpz_get_str( str, 10, m );
153  puts(str);
154  delete[] str;
155  mpz_clear(m);
156  }
157  else if (f.inQ())
158  {
159  mpz_t m;
160  gmp_numerator(f,m);
161  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
162  str = mpz_get_str( str, 10, m );
163  puts(str);putchar('/');
164  delete[] str;
165  mpz_clear(m);
166  gmp_denominator(f,m);
167  str = new char[mpz_sizeinbase( m, 10 ) + 2];
168  str = mpz_get_str( str, 10, m );
169  puts(str);
170  delete[] str;
171  mpz_clear(m);
172  }
173  #else
174  std::cout << f;
175  #endif
176  }
177  //if (f.inZ()) printf("(Z)");
178  //else if (f.inQ()) printf("(Q)");
179  //else if (f.inFF()) printf("(FF)");
180  //else if (f.inPP()) printf("(PP)");
181  //else if (f.inGF()) printf("(PP)");
182  //else
183  if (f.inExtension()) printf("E(%d)",f.level());
184  }
185  printf("%s",s2);
186 }
long intval() const
conversion functions
bool isImm() const
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
char gf_name
Definition: gfops.cc:52
int gf_q
Definition: gfops.cc:47
bool inBaseDomain() const
int m
Definition: cfEzgcd.cc:121
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
bool inExtension() const
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
static int gettype()
Definition: cf_factory.h:28
bool inQ() const
bool inZ() const
predicates
#define GaloisFieldDomain
Definition: cf_defs.h:22
int level() const
level() returns the level of CO.
InternalCF * getval() const
int l
Definition: cfEzgcd.cc:93
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40

◆ psq()

CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

psq() - return pseudo quotient of `f' and `g' with respect to `x'.

`g' must not equal zero.

Type info:

f, g: Current x: Polynomial

Developers note:

This is not an optimal implementation. Better would have been an implementation in `InternalPoly' avoiding the exponentiation of the leading coefficient of `g'. It seemed not worth to do so.

See also
psr(), psqr()

Definition at line 172 of file cf_algorithm.cc.

173 {
174  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
175  ASSERT( ! g.isZero(), "math error: division by zero" );
176 
177  // swap variables such that x's level is larger or equal
178  // than both f's and g's levels.
179  Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
180  CanonicalForm F = swapvar( f, x, X );
181  CanonicalForm G = swapvar( g, x, X );
182 
183  // now, we have to calculate the pseudo remainder of F and G
184  // w.r.t. X
185  int fDegree = degree( F, X );
186  int gDegree = degree( G, X );
187  if ( fDegree < 0 || fDegree < gDegree )
188  return 0;
189  else {
190  CanonicalForm result = (power( LC( G, X ), fDegree-gDegree+1 ) * F) / G;
191  return swapvar( result, x, X );
192  }
193 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:31
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level() const
Definition: factory.h:134
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

◆ psqr()

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

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

psqr() - calculate pseudo quotient and remainder of `f' and `g' with respect to `x'.

Returns the pseudo quotient of `f' and `g' in `q', the pseudo remainder in `r'. `g' must not equal zero.

See `psr()' for more detailed information.

Type info:

f, g: Current q, r: Anything x: Polynomial

Developers note:

This is not an optimal implementation. Better would have been an implementation in `InternalPoly' avoiding the exponentiation of the leading coefficient of `g'. It seemed not worth to do so.

See also
psr(), psq()

Definition at line 223 of file cf_algorithm.cc.

224 {
225  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
226  ASSERT( ! g.isZero(), "math error: division by zero" );
227 
228  // swap variables such that x's level is larger or equal
229  // than both f's and g's levels.
230  Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
231  CanonicalForm F = swapvar( f, x, X );
232  CanonicalForm G = swapvar( g, x, X );
233 
234  // now, we have to calculate the pseudo remainder of F and G
235  // w.r.t. X
236  int fDegree = degree( F, X );
237  int gDegree = degree( G, X );
238  if ( fDegree < 0 || fDegree < gDegree ) {
239  q = 0; r = f;
240  } else {
241  divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r );
242  q = swapvar( q, x, X );
243  r = swapvar( r, x, X );
244  }
245 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:31
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level() const
Definition: factory.h:134
FILE * f
Definition: checklibs.c:9
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)

◆ psr()

CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

psr() - return pseudo remainder of `f' and `g' with respect to `x'.

`g' must not equal zero.

For f and g in R[x], R an arbitrary ring, g != 0, there is a representation

LC(g)^s*f = g*q + r

with r = 0 or deg(r) < deg(g) and s = 0 if f = 0 or s = max( 0, deg(f)-deg(g)+1 ) otherwise. r = psr(f, g) and q = psq(f, g) are called "pseudo remainder" and "pseudo quotient", resp. They are uniquely determined if LC(g) is not a zero divisor in R.

See H.-J. Reiffen/G. Scheja/U. Vetter - "Algebra", 2nd ed., par. 15, for a reference.

Type info:

f, g: Current x: Polynomial

Polynomials over prime power domains are admissible if lc(LC(`g',`x')) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since pseudo remainder and quotient are well-defined if LC(`g',`x') is not a zero divisor.

For example, psr(y^2, (13*x+1)*y) is well-defined in (Z/13^2[x])[y] since (13*x+1) is not a zero divisor. But calculating it with Factory would fail since 13 is a zero divisor in Z/13^2.

Due to this inconsistency with mathematical notion, we decided not to declare type `CurrentPP' for `f' and `g'.

Developers note:

This is not an optimal implementation. Better would have been an implementation in `InternalPoly' avoiding the exponentiation of the leading coefficient of `g'. In contrast to `psq()' and `psqr()' it definitely seems worth to implement the pseudo remainder on the internal level.

See also
psq(), psqr()

Definition at line 117 of file cf_algorithm.cc.

118 {
119  CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue;
120  int dr, dv, d,n=0;
121 
122 
123  dr = degree( r, x );
124  if (dr>0)
125  {
126  dv = degree( v, x );
127  if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);}
128  else { l = 1; }
129  d= dr-dv+1;
130  //out_cf("psr(",rr," ");
131  //out_cf("",vv," ");
132  //printf(" var=%d\n",x.level());
133  while ( ( dv <= dr ) && ( !r.isZero()) )
134  {
135  test = power(x,dr-dv)*v*LC(r,x);
136  if ( dr == 0 ) { r= CanonicalForm(0); }
137  else { r= r - LC(r,x)*power(x,dr); }
138  r= l*r -test;
139  dr= degree(r,x);
140  n+=1;
141  }
142  r= power(l, d-n)*r;
143  }
144  return r;
145 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
CanonicalForm test
Definition: cfModGcd.cc:4037
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:93

◆ tryFdivides()

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

Definition at line 454 of file cf_algorithm.cc.

455 {
456  fail= false;
457  // trivial cases
458  if ( g.isZero() )
459  return true;
460  else if ( f.isZero() )
461  return false;
462 
463  if (f.inCoeffDomain() || g.inCoeffDomain())
464  {
465  // if we are in a field all elements not equal to zero are units
466  if ( f.inCoeffDomain() )
467  {
468  CanonicalForm inv;
469  tryInvert (f, M, inv, fail);
470  return !fail;
471  }
472  else
473  {
474  return false;
475  }
476  }
477 
478  // we may assume now that both levels either equal LEVELBASE
479  // or are greater zero
480  int fLevel = f.level();
481  int gLevel = g.level();
482  if ( (gLevel > 0) && (fLevel == gLevel) )
483  {
484  if (degree( f ) > degree( g ))
485  return false;
486  bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
487 
488  if (fail || !dividestail)
489  return false;
490  bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail);
491  if (fail || !dividesLC)
492  return false;
493  CanonicalForm q,r;
494  bool divides= tryDivremt (g, f, q, r, M, fail);
495  if (fail || !divides)
496  return false;
497  return r.isZero();
498  }
499  else if ( gLevel < fLevel )
500  {
501  // g is a coefficient w.r.t. f
502  return false;
503  }
504  else
505  {
506  // either f is a coefficient w.r.t. polynomial g or both
507  // f and g are from a base domain (should be Z or Z/p^n,
508  // then)
509  CanonicalForm q, r;
510  bool divides= tryDivremt (g, f, q, r, M, fail);
511  if (fail || !divides)
512  return false;
513  return r.isZero();
514  }
515 }
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:221
#define M
Definition: sirandom.c:24
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
bool tryDivremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const CanonicalForm &M, bool &fail)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible ...
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
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 ...
bool inCoeffDomain() const
CanonicalForm LC() const