My Project
Functions
cf_gcd.cc File Reference

gcd/content/lcm of polynomials More...

#include "config.h"
#include "timing.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_reval.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "cfEzgcd.h"
#include "cfGcdAlgExt.h"
#include "cfSubResGcd.h"
#include "cfModGcd.h"
#include "FLINTconvert.h"
#include "facAlgFuncUtil.h"
#include "templates/ftmpl_functions.h"
#include <NTL/ZZX.h>
#include "NTLconvert.h"

Go to the source code of this file.

Functions

bool isPurePoly (const CanonicalForm &)
 
void out_cf (const char *s1, const CanonicalForm &f, const char *s2)
 cf_algorithm.cc - simple mathematical algorithms. More...
 
static CanonicalForm icontent (const CanonicalForm &f, const CanonicalForm &c)
 static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c ) More...
 
CanonicalForm icontent (const CanonicalForm &f)
 CanonicalForm icontent ( const CanonicalForm & f ) More...
 
static CanonicalForm gcd_univar_flintp (const CanonicalForm &F, const CanonicalForm &G)
 
static CanonicalForm gcd_univar_flint0 (const CanonicalForm &F, const CanonicalForm &G)
 
static CanonicalForm balance_p (const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
 
static CanonicalForm balance_p (const CanonicalForm &f, const CanonicalForm &q)
 
static CanonicalForm gcd_poly_univar0 (const CanonicalForm &F, const CanonicalForm &G, bool primitive)
 
static CanonicalForm gcd_poly_p (const CanonicalForm &f, const CanonicalForm &g)
 
static CanonicalForm gcd_poly_0 (const CanonicalForm &f, const CanonicalForm &g)
 
CanonicalForm gcd_poly (const CanonicalForm &f, const CanonicalForm &g)
 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
static CanonicalForm cf_content (const CanonicalForm &f, const CanonicalForm &g)
 static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
CanonicalForm content (const CanonicalForm &f)
 CanonicalForm content ( const CanonicalForm & f ) More...
 
CanonicalForm content (const CanonicalForm &f, const Variable &x)
 CanonicalForm content ( const CanonicalForm & f, const Variable & x ) More...
 
CanonicalForm vcontent (const CanonicalForm &f, const Variable &x)
 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ) More...
 
CanonicalForm pp (const CanonicalForm &f)
 CanonicalForm pp ( const CanonicalForm & f ) More...
 
CanonicalForm gcd (const CanonicalForm &f, const CanonicalForm &g)
 
CanonicalForm lcm (const CanonicalForm &f, const CanonicalForm &g)
 CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g ) More...
 

Detailed Description

gcd/content/lcm of polynomials

To compute the GCD different variants are chosen automatically

Definition in file cf_gcd.cc.

Function Documentation

◆ balance_p() [1/2]

static CanonicalForm balance_p ( const CanonicalForm f,
const CanonicalForm q 
)
static

Definition at line 172 of file cf_gcd.cc.

173 {
174  CanonicalForm qh = q / 2;
175  return balance_p (f, q, qh);
176 }
static CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
Definition: cf_gcd.cc:149
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:86

◆ balance_p() [2/2]

static CanonicalForm balance_p ( const CanonicalForm f,
const CanonicalForm q,
const CanonicalForm qh 
)
static

Definition at line 149 of file cf_gcd.cc.

150 {
151  Variable x = f.mvar();
152  CanonicalForm result = 0;
153  CanonicalForm c;
154  CFIterator i;
155  for ( i = f; i.hasTerms(); i++ )
156  {
157  c = i.coeff();
158  if ( c.inCoeffDomain())
159  {
160  if ( c > qh )
161  result += power( x, i.exp() ) * (c - q);
162  else
163  result += power( x, i.exp() ) * c;
164  }
165  else
166  result += power( x, i.exp() ) * balance_p(c,q,qh);
167  }
168  return result;
169 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
bool inCoeffDomain() const
factory's class for variables
Definition: factory.h:127
return result
Definition: facAbsBiFact.cc:75

◆ cf_content()

static CanonicalForm cf_content ( const CanonicalForm f,
const CanonicalForm g 
)
static

static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )

cf_content() - return gcd(g, content(f)).

content(f) is calculated with respect to f's main variable.

See also
gcd(), content(), content( CF, Variable ).

Definition at line 578 of file cf_gcd.cc.

579 {
580  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
581  {
582  CFIterator i = f;
584  while ( i.hasTerms() && ! result.isOne() )
585  {
586  result = gcd( i.coeff(), result );
587  i++;
588  }
589  return result;
590  }
591  else
592  return abs( f );
593 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
g
Definition: cfModGcd.cc:4090
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:685
bool getReduce(const Variable &alpha)
Definition: variable.cc:232

◆ content() [1/2]

CanonicalForm content ( const CanonicalForm f)

CanonicalForm content ( const CanonicalForm & f )

content() - return content(f) with respect to main variable.

Normalizes result.

Definition at line 603 of file cf_gcd.cc.

604 {
605  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
606  {
607  CFIterator i = f;
608  CanonicalForm result = abs( i.coeff() );
609  i++;
610  while ( i.hasTerms() && ! result.isOne() )
611  {
612  result = gcd( i.coeff(), result );
613  i++;
614  }
615  return result;
616  }
617  else
618  return abs( f );
619 }

◆ content() [2/2]

CanonicalForm content ( const CanonicalForm f,
const Variable x 
)

CanonicalForm content ( const CanonicalForm & f, const Variable & x )

content() - return content(f) with respect to x.

x should be a polynomial variable.

Definition at line 629 of file cf_gcd.cc.

630 {
631  if (f.inBaseDomain()) return f;
632  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
633  Variable y = f.mvar();
634 
635  if ( y == x )
636  return cf_content( f, 0 );
637  else if ( y < x )
638  return f;
639  else
640  return swapvar( content( swapvar( f, y, x ), y ), y, x );
641 }
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:578
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int level() const
Definition: factory.h:143
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ gcd()

Definition at line 685 of file cf_gcd.cc.

686 {
687  bool b = f.isZero();
688  if ( b || g.isZero() )
689  {
690  if ( b )
691  return abs( g );
692  else
693  return abs( f );
694  }
695  if ( f.inPolyDomain() || g.inPolyDomain() )
696  {
697  if ( f.mvar() != g.mvar() )
698  {
699  if ( f.mvar() > g.mvar() )
700  return cf_content( f, g );
701  else
702  return cf_content( g, f );
703  }
704  if (isOn(SW_USE_QGCD))
705  {
706  Variable m;
707  if (
708  (getCharacteristic() == 0) &&
710  )
711  {
712  bool on_rational = isOn(SW_RATIONAL);
713  CanonicalForm r=QGCD(f,g);
714  On(SW_RATIONAL);
715  CanonicalForm cdF = bCommonDen( r );
716  if (!on_rational) Off(SW_RATIONAL);
717  return cdF*r;
718  }
719  }
720 
721  if ( f.inExtension() && getReduce( f.mvar() ) )
722  return CanonicalForm(1);
723  else
724  {
725  if ( fdivides( f, g ) )
726  return abs( f );
727  else if ( fdivides( g, f ) )
728  return abs( g );
729  if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
730  {
731  CanonicalForm d;
732  d = gcd_poly( f, g );
733  return abs( d );
734  }
735  else
736  {
737  CanonicalForm cdF = bCommonDen( f );
738  CanonicalForm cdG = bCommonDen( g );
739  CanonicalForm F = f * cdF, G = g * cdG;
740  Off( SW_RATIONAL );
741  CanonicalForm l = gcd_poly( F, G );
742  On( SW_RATIONAL );
743  return abs( l );
744  }
745  }
746  }
747  if ( f.inBaseDomain() && g.inBaseDomain() )
748  return bgcd( f, g );
749  else
750  return 1;
751 }
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition: cfGcdAlgExt.cc:730
CanonicalForm b
Definition: cfModGcd.cc:4103
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:43
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:492
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ gcd_poly()

CanonicalForm gcd_poly ( const CanonicalForm f,
const CanonicalForm g 
)

CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )

gcd_poly() - calculate polynomial gcd.

This is the dispatcher for polynomial gcd calculation. Different gcd variants get called depending the input, characteristic, and on switches (cf_defs.h)

With the current settings from Singular (i.e. SW_USE_EZGCD= on, SW_USE_EZGCD_P= on, SW_USE_CHINREM_GCD= on, the EZ GCD variants are the default algorithms for multivariate polynomial GCD computations)

See also
gcd(), cf_defs.h

Definition at line 492 of file cf_gcd.cc.

493 {
494  CanonicalForm fc, gc;
495  bool fc_isUnivariate=f.isUnivariate();
496  bool gc_isUnivariate=g.isUnivariate();
497  bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
498  fc = f;
499  gc = g;
500  int ch=getCharacteristic();
501  if ( ch != 0 )
502  {
503  if (0) {} // dummy, to be able to build without NTL and FLINT
504  #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
505  if ( isOn( SW_USE_FL_GCD_P)
507  #ifdef HAVE_NTL
508  && (ch>10) // if we have NTL: it is better for char <11
509  #endif
510  &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
511  {
512  return gcdFlintMP_Zp(fc,gc);
513  }
514  #endif
515  #ifdef HAVE_NTL
516  if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
517  {
518  fc= EZGCD_P (fc, gc);
519  }
520  #endif
521  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
522  else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
523  {
524  Variable a;
525  if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
526  fc=modGCDFq (fc, gc, a);
528  fc=modGCDGF (fc, gc);
529  else
530  fc=modGCDFp (fc, gc);
531  }
532  #endif
533  else
534  fc = gcd_poly_p( fc, gc );
535  }
536  else if (!fc_and_gc_Univariate) /* && char==0*/
537  {
538  #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
539  if (( isOn( SW_USE_FL_GCD_0) )
540  &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
541  {
542  return gcdFlintMP_QQ(fc,gc);
543  }
544  else
545  #endif
546  #ifdef HAVE_NTL
547  if ( isOn( SW_USE_EZGCD ) )
548  fc= ezgcd (fc, gc);
549  else
550  #endif
551  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
553  fc = modGCDZ( fc, gc);
554  else
555  #endif
556  {
557  fc = gcd_poly_0( fc, gc );
558  }
559  }
560  else
561  {
562  fc = gcd_poly_0( fc, gc );
563  }
564  if ((ch>0)&&(!hasAlgVar(fc))) fc/=fc.lc();
565  return fc;
566 }
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
Definition: cfEzgcd.cc:876
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:498
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition: cfModGcd.cc:478
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1223
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
Definition: cfModGcd.cc:872
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: cf_defs.h:41
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: cf_defs.h:47
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:37
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:45
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:35
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition: cf_defs.h:49
#define GaloisFieldDomain
Definition: cf_defs.h:18
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:417
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:264
static int gettype()
Definition: cf_factory.h:28
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
int hasAlgVar(const CanonicalForm &f, const Variable &v)

◆ gcd_poly_0()

static CanonicalForm gcd_poly_0 ( const CanonicalForm f,
const CanonicalForm g 
)
static

Definition at line 417 of file cf_gcd.cc.

418 {
419  CanonicalForm pi, pi1;
420  CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
421  int delta = degree( f ) - degree( g );
422 
423  if ( delta >= 0 )
424  {
425  pi = f; pi1 = g;
426  }
427  else
428  {
429  pi = g; pi1 = f; delta = -delta;
430  }
431  Ci = content( pi ); Ci1 = content( pi1 );
432  pi1 = pi1 / Ci1; pi = pi / Ci;
433  C = gcd( Ci, Ci1 );
434  int d= 0;
435  if ( pi.isUnivariate() && pi1.isUnivariate() )
436  {
437 #ifdef HAVE_FLINT
438  if (isPurePoly(pi) && isPurePoly(pi1) )
439  return gcd_univar_flint0(pi, pi1 ) * C;
440 #else
441 #ifdef HAVE_NTL
442  if ( isPurePoly(pi) && isPurePoly(pi1) )
443  return gcd_univar_ntl0(pi, pi1 ) * C;
444 #endif
445 #endif
446  return gcd_poly_univar0( pi, pi1, true ) * C;
447  }
448  else if ( gcd_test_one( pi1, pi, true, d ) )
449  return C;
450  Variable v = f.mvar();
451  Hi = power( LC( pi1, v ), delta );
452  if ( (delta+1) % 2 )
453  bi = 1;
454  else
455  bi = -1;
456  while ( degree( pi1, v ) > 0 )
457  {
458  pi2 = psr( pi, pi1, v );
459  pi2 = pi2 / bi;
460  pi = pi1; pi1 = pi2;
461  if ( degree( pi1, v ) > 0 )
462  {
463  delta = degree( pi, v ) - degree( pi1, v );
464  if ( (delta+1) % 2 )
465  bi = LC( pi, v ) * power( Hi, delta );
466  else
467  bi = -LC( pi, v ) * power( Hi, delta );
468  Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
469  }
470  }
471  if ( degree( pi1, v ) == 0 )
472  return C;
473  else
474  return C * pp( pi );
475 }
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition: cfGcdUtil.cc:25
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
static CanonicalForm gcd_poly_univar0(const CanonicalForm &F, const CanonicalForm &G, bool primitive)
Definition: cf_gcd.cc:178
bool isPurePoly(const CanonicalForm &)
Definition: cf_factor.cc:244
CanonicalForm pp(const CanonicalForm &f)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
static CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Definition: cf_gcd.cc:94
bool isUnivariate() const
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
#define pi
Definition: libparse.cc:1145
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160

◆ gcd_poly_p()

static CanonicalForm gcd_poly_p ( const CanonicalForm f,
const CanonicalForm g 
)
static

Definition at line 264 of file cf_gcd.cc.

265 {
266  if (f.inCoeffDomain() || g.inCoeffDomain()) //zero case should be caught by gcd
267  return 1;
268  CanonicalForm pi, pi1;
269  CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
270  bool bpure, ezgcdon= isOn (SW_USE_EZGCD_P);
271  int delta = degree( f ) - degree( g );
272 
273  if ( delta >= 0 )
274  {
275  pi = f; pi1 = g;
276  }
277  else
278  {
279  pi = g; pi1 = f; delta = -delta;
280  }
281  if (pi.isUnivariate())
282  Ci= 1;
283  else
284  {
285  if (!ezgcdon)
286  On (SW_USE_EZGCD_P);
287  Ci = content( pi );
288  if (!ezgcdon)
290  pi = pi / Ci;
291  }
292  if (pi1.isUnivariate())
293  Ci1= 1;
294  else
295  {
296  if (!ezgcdon)
297  On (SW_USE_EZGCD_P);
298  Ci1 = content( pi1 );
299  if (!ezgcdon)
301  pi1 = pi1 / Ci1;
302  }
303  C = gcd( Ci, Ci1 );
304  int d= 0;
305  if ( !( pi.isUnivariate() && pi1.isUnivariate() ) )
306  {
307  if ( gcd_test_one( pi1, pi, true, d ) )
308  {
309  C=abs(C);
310  //out_cf("GCD:",C,"\n");
311  return C;
312  }
313  bpure = false;
314  }
315  else
316  {
317  bpure = isPurePoly(pi) && isPurePoly(pi1);
318 #ifdef HAVE_FLINT
319  if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
320  return gcd_univar_flintp(pi,pi1)*C;
321 #else
322 #ifdef HAVE_NTL
323  if ( bpure && (CFFactory::gettype() != GaloisFieldDomain))
324  return gcd_univar_ntlp(pi, pi1 ) * C;
325 #endif
326 #endif
327  }
328  Variable v = f.mvar();
329  Hi = power( LC( pi1, v ), delta );
330  int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
331 
332  if (!(pi.isUnivariate() && pi1.isUnivariate()))
333  {
334  if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
335  {
337  C *= gcd (pi, pi1);
339  return C;
340  }
341  }
342 
343  if ( (delta+1) % 2 )
344  bi = 1;
345  else
346  bi = -1;
347  CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
348  while ( degree( pi1, v ) > 0 )
349  {
350  if (!(pi.isUnivariate() && pi1.isUnivariate()))
351  {
352  if (size (pi)/maxNumVars > 500 || size (pi1)/maxNumVars > 500)
353  {
355  C *= gcd (oldPi, oldPi1);
357  return C;
358  }
359  }
360  pi2 = psr( pi, pi1, v );
361  pi2 = pi2 / bi;
362  pi = pi1; pi1 = pi2;
363  maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
364  if (!pi1.isUnivariate() && (size (pi1)/maxNumVars > 500))
365  {
367  C *= gcd (oldPi, oldPi1);
369  return C;
370  }
371  if ( degree( pi1, v ) > 0 )
372  {
373  delta = degree( pi, v ) - degree( pi1, v );
374  powHi= power (Hi, delta-1);
375  if ( (delta+1) % 2 )
376  bi = LC( pi, v ) * powHi*Hi;
377  else
378  bi = -LC( pi, v ) * powHi*Hi;
379  Hi = power( LC( pi1, v ), delta ) / powHi;
380  if (!(pi.isUnivariate() && pi1.isUnivariate()))
381  {
382  if (size (Hi)*size (pi)/(maxNumVars*3) > 1500) //maybe this needs more tuning
383  {
385  C *= gcd (oldPi, oldPi1);
387  return C;
388  }
389  }
390  }
391  }
392  if ( degree( pi1, v ) == 0 )
393  {
394  C=abs(C);
395  //out_cf("GCD:",C,"\n");
396  return C;
397  }
398  if (!pi.isUnivariate())
399  {
400  if (!ezgcdon)
401  On (SW_USE_EZGCD_P);
402  Ci= gcd (LC (oldPi,v), LC (oldPi1,v));
403  pi /= LC (pi,v)/Ci;
404  Ci= content (pi);
405  pi /= Ci;
406  if (!ezgcdon)
408  }
409  if ( bpure )
410  pi /= pi.lc();
411  C=abs(C*pi);
412  //out_cf("GCD:",C,"\n");
413  return C;
414 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int maxNumVars
Definition: cfModGcd.cc:4130
static CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
Definition: cf_gcd.cc:81
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)

◆ gcd_poly_univar0()

static CanonicalForm gcd_poly_univar0 ( const CanonicalForm F,
const CanonicalForm G,
bool  primitive 
)
static

Definition at line 178 of file cf_gcd.cc.

179 {
180  CanonicalForm f, g, c, cg, cl, BB, B, M, q, Dp, newD, D, newq;
181  int p, i;
182 
183  if ( primitive )
184  {
185  f = F;
186  g = G;
187  c = 1;
188  }
189  else
190  {
191  CanonicalForm cF = content( F ), cG = content( G );
192  f = F / cF;
193  g = G / cG;
194  c = bgcd( cF, cG );
195  }
196  cg = gcd( f.lc(), g.lc() );
197  cl = ( f.lc() / cg ) * g.lc();
198 // B = 2 * cg * tmin(
199 // maxnorm(f)*power(CanonicalForm(2),f.degree())*isqrt(f.degree()+1),
200 // maxnorm(g)*power(CanonicalForm(2),g.degree())*isqrt(g.degree()+1)
201 // )+1;
202  M = tmin( maxNorm(f), maxNorm(g) );
203  BB = power(CanonicalForm(2),tmin(f.degree(),g.degree()))*M;
204  q = 0;
205  i = cf_getNumSmallPrimes() - 1;
206  while ( true )
207  {
208  B = BB;
209  while ( i >= 0 && q < B )
210  {
211  p = cf_getSmallPrime( i );
212  i--;
213  while ( i >= 0 && mod( cl, p ) == 0 )
214  {
215  p = cf_getSmallPrime( i );
216  i--;
217  }
218  setCharacteristic( p );
219  Dp = gcd( mapinto( f ), mapinto( g ) );
220  Dp = ( Dp / Dp.lc() ) * mapinto( cg );
221  setCharacteristic( 0 );
222  if ( Dp.degree() == 0 )
223  return c;
224  if ( q.isZero() )
225  {
226  D = mapinto( Dp );
227  q = p;
228  B = power(CanonicalForm(2),D.degree())*M+1;
229  }
230  else
231  {
232  if ( Dp.degree() == D.degree() )
233  {
234  chineseRemainder( D, q, mapinto( Dp ), p, newD, newq );
235  q = newq;
236  D = newD;
237  }
238  else if ( Dp.degree() < D.degree() )
239  {
240  // all previous p's are bad primes
241  q = p;
242  D = mapinto( Dp );
243  B = power(CanonicalForm(2),D.degree())*M+1;
244  }
245  // else p is a bad prime
246  }
247  }
248  if ( i >= 0 )
249  {
250  // now balance D mod q
251  D = pp( balance_p( D, q ) );
252  if ( fdivides( D, f ) && fdivides( D, g ) )
253  return D * c;
254  else
255  q = 0;
256  }
257  else
258  return gcd_poly( F, G );
259  DEBOUTLN( cerr, "another try ..." );
260  }
261 }
CanonicalForm mapinto(const CanonicalForm &f)
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int p
Definition: cfModGcd.cc:4078
cl
Definition: cfModGcd.cc:4100
CanonicalForm cg
Definition: cfModGcd.cc:4083
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition: cf_chinese.cc:57
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
CF_NO_INLINE bool isZero() const
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
b *CanonicalForm B
Definition: facBivar.cc:52
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
#define D(A)
Definition: gentable.cc:131
#define M
Definition: sirandom.c:25

◆ gcd_univar_flint0()

static CanonicalForm gcd_univar_flint0 ( const CanonicalForm F,
const CanonicalForm G 
)
static

Definition at line 94 of file cf_gcd.cc.

95 {
96  fmpz_poly_t F1, G1;
99  fmpz_poly_gcd (F1, F1, G1);
101  fmpz_poly_clear (F1);
102  fmpz_poly_clear (G1);
103  return result;
104 }
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int F1(int a1, int &r1)
F1.

◆ gcd_univar_flintp()

static CanonicalForm gcd_univar_flintp ( const CanonicalForm F,
const CanonicalForm G 
)
static

Definition at line 81 of file cf_gcd.cc.

82 {
83  nmod_poly_t F1, G1;
86  nmod_poly_gcd (F1, F1, G1);
89  nmod_poly_clear (G1);
90  return result;
91 }
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)

◆ icontent() [1/2]

CanonicalForm icontent ( const CanonicalForm f)

CanonicalForm icontent ( const CanonicalForm & f )

icontent() - return gcd over all coefficients of f which are in a coefficient domain.

Definition at line 74 of file cf_gcd.cc.

75 {
76  return icontent( f, 0 );
77 }
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition: cf_gcd.cc:49

◆ icontent() [2/2]

static CanonicalForm icontent ( const CanonicalForm f,
const CanonicalForm c 
)
static

static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )

icontent() - return gcd of c and all coefficients of f which are in a coefficient domain.

See also
icontent().

Definition at line 49 of file cf_gcd.cc.

50 {
51  if ( f.inBaseDomain() )
52  {
53  if (c.isZero()) return abs(f);
54  return bgcd( f, c );
55  }
56  //else if ( f.inCoeffDomain() )
57  // return gcd(f,c);
58  else
59  {
60  CanonicalForm g = c;
61  for ( CFIterator i = f; i.hasTerms() && ! g.isOne(); i++ )
62  g = icontent( i.coeff(), g );
63  return g;
64  }
65 }

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 244 of file cf_factor.cc.

245 {
246  if (f.level()<=0) return false;
247  for (CFIterator i=f;i.hasTerms();i++)
248  {
249  if (!(i.coeff().inBaseDomain())) return false;
250  }
251  return true;
252 }

◆ lcm()

CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )

lcm() - return least common multiple of f and g.

The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).

Returns zero if one of f or g equals zero.

Definition at line 763 of file cf_gcd.cc.

764 {
765  if ( f.isZero() || g.isZero() )
766  return 0;
767  else
768  return ( f / gcd( f, g ) ) * g;
769 }

◆ 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 99 of file cf_factor.cc.

100 {
101  printf("%s",s1);
102  if (f.isZero()) printf("+0");
103  //else if (! f.inCoeffDomain() )
104  else if (! f.inBaseDomain() )
105  {
106  int l = f.level();
107  for ( CFIterator i = f; i.hasTerms(); i++ )
108  {
109  int e=i.exp();
110  if (i.coeff().isOne())
111  {
112  printf("+");
113  if (e==0) printf("1");
114  else
115  {
116  printf("%c",'a'+l-1);
117  if (e!=1) printf("^%d",e);
118  }
119  }
120  else
121  {
122  out_cf("+(",i.coeff(),")");
123  if (e!=0)
124  {
125  printf("*%c",'a'+l-1);
126  if (e!=1) printf("^%d",e);
127  }
128  }
129  }
130  }
131  else
132  {
133  if ( f.isImm() )
134  {
136  {
137  long a= imm2int (f.getval());
138  if ( a == gf_q )
139  printf ("+%ld", a);
140  else if ( a == 0L )
141  printf ("+1");
142  else if ( a == 1L )
143  printf ("+%c",gf_name);
144  else
145  {
146  printf ("+%c",gf_name);
147  printf ("^%ld",a);
148  }
149  }
150  else
151  {
152  long l=f.intval();
153  if (l<0) printf("%ld",l);
154  else printf("+%ld",l);
155  }
156  }
157  else
158  {
159  #ifdef NOSTREAMIO
160  if (f.inZ())
161  {
162  mpz_t m;
163  gmp_numerator(f,m);
164  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
165  str = mpz_get_str( str, 10, m );
166  puts(str);
167  delete[] str;
168  mpz_clear(m);
169  }
170  else if (f.inQ())
171  {
172  mpz_t m;
173  gmp_numerator(f,m);
174  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
175  str = mpz_get_str( str, 10, m );
176  while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
177  puts(str);putchar('/');
178  delete[] str;
179  mpz_clear(m);
181  str = new char[mpz_sizeinbase( m, 10 ) + 2];
182  str = mpz_get_str( str, 10, m );
183  while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
184  puts(str);
185  delete[] str;
186  mpz_clear(m);
187  }
188  #else
189  std::cout << f;
190  #endif
191  }
192  //if (f.inZ()) printf("(Z)");
193  //else if (f.inQ()) printf("(Q)");
194  //else if (f.inFF()) printf("(FF)");
195  //else if (f.inPP()) printf("(PP)");
196  //else if (f.inGF()) printf("(PP)");
197  //else
198  if (f.inExtension()) printf("E(%d)",f.level());
199  }
200  printf("%s",s2);
201 }
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:99
void FACTORY_PUBLIC gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
void FACTORY_PUBLIC gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
VAR int gf_q
Definition: gfops.cc:47
VAR char gf_name
Definition: gfops.cc:52
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
char * str(leftv arg)
Definition: shared.cc:704

◆ pp()

CanonicalForm pp ( const CanonicalForm & f )

pp() - return primitive part of f.

Returns zero if f equals zero, otherwise f / content(f).

Definition at line 676 of file cf_gcd.cc.

677 {
678  if ( f.isZero() )
679  return f;
680  else
681  return f / content( f );
682 }

◆ vcontent()

CanonicalForm vcontent ( const CanonicalForm f,
const Variable x 
)

CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )

vcontent() - return content of f with repect to variables >= x.

The content is recursively calculated over all coefficients in f having level less than x. x should be a polynomial variable.

Definition at line 653 of file cf_gcd.cc.

654 {
655  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
656 
657  if ( f.mvar() <= x )
658  return content( f, x );
659  else {
660  CFIterator i;
661  CanonicalForm d = 0;
662  for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
663  d = gcd( d, vcontent( i.coeff(), x ) );
664  return d;
665  }
666 }
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
CF_NO_INLINE bool isOne() const