My Project
cf_gcd.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file cf_gcd.cc
5  *
6  * gcd/content/lcm of polynomials
7  *
8  * To compute the GCD different variants are chosen automatically
9 **/
10 
11 #include "config.h"
12 
13 
14 #include "timing.h"
15 #include "cf_assert.h"
16 #include "debug.h"
17 
18 #include "cf_defs.h"
19 #include "canonicalform.h"
20 #include "cf_iter.h"
21 #include "cf_reval.h"
22 #include "cf_primes.h"
23 #include "cf_algorithm.h"
24 #include "cfEzgcd.h"
25 #include "cfGcdAlgExt.h"
26 #include "cfSubResGcd.h"
27 #include "cfModGcd.h"
28 #include "FLINTconvert.h"
29 #include "facAlgFuncUtil.h"
31 
32 #ifdef HAVE_NTL
33 #include <NTL/ZZX.h>
34 #include "NTLconvert.h"
35 bool isPurePoly(const CanonicalForm & );
36 #endif
37 
38 void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
39 
40 /** static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
41  *
42  * icontent() - return gcd of c and all coefficients of f which
43  * are in a coefficient domain.
44  *
45  * @sa icontent().
46  *
47 **/
48 static CanonicalForm
49 icontent ( const CanonicalForm & f, const CanonicalForm & c )
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 }
66 
67 /** CanonicalForm icontent ( const CanonicalForm & f )
68  *
69  * icontent() - return gcd over all coefficients of f which are
70  * in a coefficient domain.
71  *
72 **/
75 {
76  return icontent( f, 0 );
77 }
78 
79 #ifdef HAVE_FLINT
80 static CanonicalForm
82 {
83  nmod_poly_t F1, G1;
86  nmod_poly_gcd (F1, F1, G1);
88  nmod_poly_clear (F1);
89  nmod_poly_clear (G1);
90  return result;
91 }
92 
93 static CanonicalForm
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 }
105 #endif
106 
107 #ifdef HAVE_NTL
108 #ifndef HAVE_FLINT
109 static CanonicalForm
110 gcd_univar_ntl0( const CanonicalForm & F, const CanonicalForm & G )
111 {
112  ZZX F1=convertFacCF2NTLZZX(F);
113  ZZX G1=convertFacCF2NTLZZX(G);
114  ZZX R=GCD(F1,G1);
115  return convertNTLZZX2CF(R,F.mvar());
116 }
117 
118 static CanonicalForm
119 gcd_univar_ntlp( const CanonicalForm & F, const CanonicalForm & G )
120 {
121  int ch=getCharacteristic();
122  if (fac_NTL_char!=ch)
123  {
124  fac_NTL_char=ch;
125  zz_p::init(ch);
126  }
127  zz_pX F1=convertFacCF2NTLzzpX(F);
128  zz_pX G1=convertFacCF2NTLzzpX(G);
129  zz_pX R=GCD(F1,G1);
130  return convertNTLzzpX2CF(R,F.mvar());
131 }
132 #endif
133 #endif
134 
135 //{{{ static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q )
136 //{{{ docu
137 //
138 // balance_p() - map f from positive to symmetric representation
139 // mod q.
140 //
141 // This makes sense for univariate polynomials over Z only.
142 // q should be an integer.
143 //
144 // Used by gcd_poly_univar0().
145 //
146 //}}}
147 
148 static CanonicalForm
149 balance_p ( const CanonicalForm & f, const CanonicalForm & q, const CanonicalForm & qh )
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 }
170 
171 static CanonicalForm
172 balance_p ( const CanonicalForm & f, const CanonicalForm & q )
173 {
174  CanonicalForm qh = q / 2;
175  return balance_p (f, q, qh);
176 }
177 
178 static CanonicalForm gcd_poly_univar0( const CanonicalForm & F, const CanonicalForm & G, bool primitive )
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 }
262 
263 static CanonicalForm
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 }
415 
416 static CanonicalForm
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 }
476 
477 /** CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
478  *
479  * gcd_poly() - calculate polynomial gcd.
480  *
481  * This is the dispatcher for polynomial gcd calculation.
482  * Different gcd variants get called depending the input, characteristic, and
483  * on switches (cf_defs.h)
484  *
485  * With the current settings from Singular (i.e. SW_USE_EZGCD= on,
486  * SW_USE_EZGCD_P= on, SW_USE_CHINREM_GCD= on, the EZ GCD variants are the
487  * default algorithms for multivariate polynomial GCD computations)
488  *
489  * @sa gcd(), cf_defs.h
490  *
491 **/
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 }
567 
568 /** static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
569  *
570  * cf_content() - return gcd(g, content(f)).
571  *
572  * content(f) is calculated with respect to f's main variable.
573  *
574  * @sa gcd(), content(), content( CF, Variable ).
575  *
576 **/
577 static CanonicalForm
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 }
594 
595 /** CanonicalForm content ( const CanonicalForm & f )
596  *
597  * content() - return content(f) with respect to main variable.
598  *
599  * Normalizes result.
600  *
601 **/
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 }
620 
621 /** CanonicalForm content ( const CanonicalForm & f, const Variable & x )
622  *
623  * content() - return content(f) with respect to x.
624  *
625  * x should be a polynomial variable.
626  *
627 **/
629 content ( const CanonicalForm & f, const Variable & x )
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 }
642 
643 /** CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
644  *
645  * vcontent() - return content of f with repect to variables >= x.
646  *
647  * The content is recursively calculated over all coefficients in
648  * f having level less than x. x should be a polynomial
649  * variable.
650  *
651 **/
653 vcontent ( const CanonicalForm & f, const Variable & x )
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 }
667 
668 /** CanonicalForm pp ( const CanonicalForm & f )
669  *
670  * pp() - return primitive part of f.
671  *
672  * Returns zero if f equals zero, otherwise f / content(f).
673  *
674 **/
676 pp ( const CanonicalForm & f )
677 {
678  if ( f.isZero() )
679  return f;
680  else
681  return f / content( f );
682 }
683 
685 gcd ( const CanonicalForm & f, const CanonicalForm & g )
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 }
752 
753 /** CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
754  *
755  * lcm() - return least common multiple of f and g.
756  *
757  * The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).
758  *
759  * Returns zero if one of f or g equals zero.
760  *
761 **/
763 lcm ( const CanonicalForm & f, const CanonicalForm & g )
764 {
765  if ( f.isZero() || g.isZero() )
766  return 0;
767  else
768  return ( f / gcd( f, g ) ) * g;
769 }
770 
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
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
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:285
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
Conversion to and from NTL.
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
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm mapinto(const CanonicalForm &f)
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
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
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
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:498
int i
Definition: cfEzgcd.cc:132
Extended Zassenhaus GCD over finite fields and Z.
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition: cfGcdAlgExt.cc:716
GCD over Q(a)
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 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:480
Variable x
Definition: cfModGcd.cc:4084
int p
Definition: cfModGcd.cc:4080
cl
Definition: cfModGcd.cc:4102
g
Definition: cfModGcd.cc:4092
int maxNumVars
Definition: cfModGcd.cc:4132
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1225
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:874
CanonicalForm b
Definition: cfModGcd.cc:4105
CanonicalForm cg
Definition: cfModGcd.cc:4085
modular and sparse modular GCD algorithms over finite fields and Z.
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
subresultant pseudo remainder sequence GCD over finite fields and Z
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
declarations of higher level algorithms.
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
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:42
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: cf_defs.h:40
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: cf_defs.h:46
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:36
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:44
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:34
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition: cf_defs.h:48
#define GaloisFieldDomain
Definition: cf_defs.h:24
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:417
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
static CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
Definition: cf_gcd.cc:81
static CanonicalForm gcd_poly_univar0(const CanonicalForm &F, const CanonicalForm &G, bool primitive)
Definition: cf_gcd.cc:178
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
static CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
Definition: cf_gcd.cc:149
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:492
bool isPurePoly(const CanonicalForm &)
Definition: cf_factor.cc:244
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:99
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:685
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition: cf_gcd.cc:49
CanonicalForm pp(const CanonicalForm &f)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:264
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:763
static CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Definition: cf_gcd.cc:94
Iterators for CanonicalForm's.
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
access to prime tables
generate random evaluation points
FILE * f
Definition: checklibs.c:9
static int gettype()
Definition: cf_factory.h:28
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
bool isUnivariate() const
factory's class for variables
Definition: factory.h:134
int level() const
Definition: factory.h:150
functions to print debug output
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Utility functions for factorization over algebraic function fields.
b *CanonicalForm B
Definition: facBivar.cc:52
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
#define D(A)
Definition: gentable.cc:131
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define pi
Definition: libparse.cc:1145
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void init()
Definition: lintree.cc:864
#define R
Definition: sirandom.c:27
#define M
Definition: sirandom.c:25
bool getReduce(const Variable &alpha)
Definition: variable.cc:232