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:75
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
FILE * f
Definition: checklibs.c:9
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:75
gmp_float sqrt(const gmp_float &a)
Definition: mpr_complex.cc:329
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76

◆ 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)
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int getCharacteristic()
Definition: cf_char.cc:51
const ring r
Definition: syzextra.cc:208
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
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int degree(const CanonicalForm &f)

◆ 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)
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int getCharacteristic()
Definition: cf_char.cc:51
const ring r
Definition: syzextra.cc:208
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
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int degree(const CanonicalForm &f)

◆ 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:75
CanonicalForm blcm(const CanonicalForm &f, const CanonicalForm &g)
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
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:75
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
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  printf("%s",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  printf("%s/",str);
164  delete[] str;
165  mpz_clear(m);
167  str = new char[mpz_sizeinbase( m, 10 ) + 2];
168  str = mpz_get_str( str, 10, m );
169  printf("%s",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 }
const poly a
Definition: syzextra.cc:212
char gf_name
Definition: gfops.cc:52
int gf_q
Definition: gfops.cc:47
int m
Definition: cfEzgcd.cc:119
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
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
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
long imm2int(const InternalCF *const imm)
Definition: imm.h:66
static int gettype()
Definition: cf_factory.h:28
#define GaloisFieldDomain
Definition: cf_defs.h:22
int l
Definition: cfEzgcd.cc:94
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:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
static TreeM * G
Definition: janet.cc:38
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:132
FILE * f
Definition: checklibs.c:9
Variable x
Definition: cfModGcd.cc:4023
#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:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
static TreeM * G
Definition: janet.cc:38
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const ring r
Definition: syzextra.cc:208
int level() const
Definition: factory.h:132
FILE * f
Definition: checklibs.c:9
Variable x
Definition: cfModGcd.cc:4023
#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
static CanonicalForm * retvalue
Definition: readcf.cc:121
factory&#39;s main class
Definition: canonicalform.h:75
const ring r
Definition: syzextra.cc:208
CanonicalForm test
Definition: cfModGcd.cc:4037
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:94

◆ 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 }
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:219
#define M
Definition: sirandom.c:24
const ring r
Definition: syzextra.cc:208
FILE * f
Definition: checklibs.c:9
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 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 ...