My Project  debian-1:4.1.2-p1+ds-2
canonicalform.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #include "cf_assert.h"
8 #include "cf_factory.h"
9 
10 #include "cf_defs.h"
11 #include "cf_globals.h"
12 #include "canonicalform.h"
13 #include "cf_iter.h"
14 #include "int_cf.h"
15 #include "cf_algorithm.h"
16 #include "imm.h"
17 #include "gfops.h"
18 #include "facMul.h"
19 #include "FLINTconvert.h"
20 
21 #ifndef NOSTREAMIO
23 #endif /* NOSTREAMIO */
24 
25 /** constructors, destructors, selectors **/
26 CanonicalForm::CanonicalForm( const char * str, const int base ) : value( CFFactory::basic( str, base ) )
27 {
28 }
29 
32 {
33  if ( is_imm( value ) )
34  return value;
35  else
36  return value->copyObject();
37 }
38 
41 {
42  if ( is_imm( value ) )
43  return *this;
44  else
45  return CanonicalForm( value->deepCopyObject() );
46 }
47 
48 void
49 CanonicalForm::mpzval(mpz_t val) const
50 {
51  ASSERT (!is_imm (value) && value->levelcoeff() == IntegerDomain, "non-immediate integer expected");
52  getmpi (value, val);
53 }
54 
55 
56 /** predicates **/
57 #if 0
58 bool
60 {
61  return is_imm( value );
62 }
63 #endif
64 
65 bool
67 {
68  if ( is_imm( value ) == INTMARK )
69  return true;
70  else if ( is_imm( value ) )
71  return false;
72  else
73  return value->levelcoeff() == IntegerDomain;
74 }
75 
76 bool
78 {
79  if ( is_imm( value ) == INTMARK )
80  return true;
81  else if ( is_imm( value ) )
82  return false;
83  else
84  return value->levelcoeff() == IntegerDomain ||
86 }
87 
88 bool
90 {
91  return is_imm( value ) == FFMARK;
92 }
93 
94 bool
96 {
97  return is_imm( value ) == GFMARK;
98 }
99 
100 bool
102 {
103  if ( is_imm( value ) )
104  return true;
105  else
106  return value->inBaseDomain();
107 }
108 
109 bool
111 {
112  if ( is_imm( value ) )
113  return false;
114  else
115  return value->inExtension();
116 }
117 
118 bool
120 {
121  if ( is_imm( value ) )
122  return true;
123  else
124  return value->inCoeffDomain();
125 }
126 
127 bool
129 {
130  if ( is_imm( value ) )
131  return false;
132  else
133  return value->inPolyDomain();
134 }
135 
136 bool
138 {
139  if ( is_imm( value ) )
140  return false;
141  else
142  return value->inQuotDomain();
143 }
144 
145 bool
147 {
148  return is_imm( value ) == GFMARK && gf_isff( imm2int( value ) );
149 }
150 
151 bool
153 {
154  if ( is_imm( value ) )
155  return false;
156  else
157  return value->isUnivariate();
158 }
159 
160 // is_homogeneous returns 1 iff f is homogeneous, 0 otherwise//
161 bool
163 {
164  if (this->isZero()) return true;
165  else if (this->inCoeffDomain()) return true;
166  else
167  {
168 #if 0
169  CFIterator i;
170  int cdeg = -2, dummy;
171  for ( i = *this; i.hasTerms(); i++ )
172  {
173  if (!(i.coeff().isHomogeneous())) return false;
174  if ( (dummy = totaldegree( i.coeff() ) + i.exp()) != cdeg )
175  {
176  if (cdeg == -2) cdeg = dummy;
177  else return false;
178  }
179  }
180  return true;
181 #else
182  CFList termlist= get_Terms(*this);
184  int deg= totaldegree(termlist.getFirst());
185 
186  for ( i=termlist; i.hasItem(); i++ )
187  if ( totaldegree(i.getItem()) != deg ) return false;
188  return true;
189 #endif
190  }
191 }
192 
193 
194 
195 /** conversion functions **/
196 long
198 {
199  if ( is_imm( value ) )
200  return imm_intval( value );
201  else
202  return value->intval();
203 }
204 
207 {
208  //ASSERT( is_imm( value ) || ! value->inExtension(), "cannot map into different Extension" );
209  if ( is_imm( value ) )
210  if ( getCharacteristic() == 0 )
211  if ( is_imm( value ) == FFMARK )
212  return CanonicalForm( int2imm( ff_symmetric( imm2int( value ) ) ) );
213  else if ( is_imm( value ) == GFMARK )
214  return CanonicalForm( int2imm( ff_symmetric( gf_gf2ff( imm2int( value ) ) ) ) );
215  else
216  return *this;
217  else if ( getGFDegree() == 1 )
218  return CanonicalForm( int2imm_p( ff_norm( imm2int( value ) ) ) );
219  else
220  return CanonicalForm( int2imm_gf( gf_int2gf( imm2int( value ) ) ) );
221  else if ( value->inBaseDomain() )
222  if ( getCharacteristic() == 0 )
223  return *this;
224  else
225  {
226  int val;
227  if ( value->levelcoeff() == IntegerDomain )
228  val = value->intmod( ff_prime );
229  else if ( value->levelcoeff() == RationalDomain )
230  return num().mapinto() / den().mapinto();
231  else {
232  ASSERT( 0, "illegal domain" );
233  return 0;
234  }
235  if ( getGFDegree() > 1 )
236  return CanonicalForm( int2imm_gf( gf_int2gf( val ) ) );
237  else
238  return CanonicalForm( int2imm_p( val ) );
239  }
240  else
241  {
242  Variable x = value->variable();
244  for ( CFIterator i = *this; i.hasTerms(); i++ )
245  result += (power( x, i.exp() ) * i.coeff().mapinto());
246  return result;
247  }
248 }
249 
250 /** CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const
251  *
252  * lc(), Lc(), LC() - leading coefficient functions.
253  *
254  * All methods return CO if CO is in a base domain.
255  *
256  * lc() returns the leading coefficient of CO with respect to
257  * lexicographic ordering. Elements in an algebraic extension
258  * are considered polynomials so lc() always returns a leading
259  * coefficient in a base domain. This method is useful to get
260  * the base domain over which CO is defined.
261  *
262  * Lc() returns the leading coefficient of CO with respect to
263  * lexicographic ordering. In contrast to lc() elements in an
264  * algebraic extension are considered coefficients so Lc() always
265  * returns a leading coefficient in a coefficient domain.
266  *
267  * LC() returns the leading coefficient of CO where CO is
268  * considered a univariate polynomial in its main variable. An
269  * element of an algebraic extension is considered an univariate
270  * polynomial, too.
271  *
272  * LC( v ) returns the leading coefficient of CO where CO is
273  * considered an univariate polynomial in the polynomial variable
274  * v.
275  * Note: If v is less than the main variable of CO we have to
276  * swap variables which may be quite expensive.
277  *
278  * Examples:
279  * > Let x < y be polynomial variables, a an algebraic variable.
280  *
281  * > (3*a*x*y^2+y+x).lc() = 3
282  *
283  * > (3*a*x*y^2+y+x).Lc() = 3*a
284  *
285  * > (3*a*x*y^2+y+x).LC() = 3*a*x
286  *
287  * > (3*a*x*y^2+y+x).LC( x ) = 3*a*y^2+1
288  *
289  *
290  * > (3*a^2+4*a).lc() = 3
291  *
292  * > (3*a^2+4*a).Lc() = 3*a^2+4*a
293  *
294  * > (3*a^2+4*a).LC() = 3
295  *
296  * > (3*a^2+4*a).LC( x ) = 3*a^2+4*a
297  *
298  * @sa InternalCF::lc(), InternalCF::Lc(), InternalCF::LC(),
299  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
300  * ::lc(), ::Lc(), ::LC(), ::LC( v )
301  *
302 **/
305 {
306  if ( is_imm( value ) )
307  return *this;
308  else
309  return value->lc();
310 }
311 
312 /**
313  * @sa CanonicalForm::lc(), CanonicalForm::LC(), InternalCF::lc(),
314  * InternalCF::Lc(), InternalCF::LC(),
315  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
316  * ::lc(), ::Lc(), ::LC(), ::LC( v )
317 **/
320 {
321  if ( is_imm( value ) || value->inCoeffDomain() )
322  return *this;
323  else
324  return value->Lc();
325 }
326 
327 /**
328  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), InternalCF::lc(),
329  * InternalCF::Lc(), InternalCF::LC(),
330  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
331  * ::lc(), ::Lc(), ::LC(), ::LC( v )
332 **/
335 {
336  if ( is_imm( value ) )
337  return *this;
338  else
339  return value->LC();
340 }
341 
342 /**
343  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), InternalCF::lc(),
344  * InternalCF::Lc(), InternalCF::LC(),
345  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
346  * ::lc(), ::Lc(), ::LC(), ::LC( v )
347 **/
349 CanonicalForm::LC ( const Variable & v ) const
350 {
351  if ( is_imm( value ) || value->inCoeffDomain() )
352  return *this;
353 
354  Variable x = value->variable();
355  if ( v > x )
356  return *this;
357  else if ( v == x )
358  return value->LC();
359  else {
360  CanonicalForm f = swapvar( *this, v, x );
361  if ( f.mvar() == x )
362  return swapvar( f.value->LC(), v, x );
363  else
364  // v did not occur in f
365  return *this;
366  }
367 }
368 
369 /**
370  * Returns -1 for the zero polynomial and 0 if
371  * CO is in a base domain.
372  *
373  * degree() returns the degree of CO in its main variable.
374  * Elements in an algebraic extension are considered polynomials.
375  *
376  * @sa InternalCF::degree(), InternalPoly::degree(),
377  * ::degree(), ::degree( v )
378  *
379 **/
380 int
382 {
383  int what = is_imm( value );
384  if ( what )
385  if ( what == FFMARK )
386  return imm_iszero_p( value ) ? -1 : 0;
387  else if ( what == INTMARK )
388  return imm_iszero( value ) ? -1 : 0;
389  else
390  return imm_iszero_gf( value ) ? -1 : 0;
391  else
392  return value->degree();
393 }
394 
395 /**
396  * returns -1 for the zero polynomial and 0 if
397  * CO is in a base domain.
398  *
399  * degree( v ) returns the degree of CO with respect to v.
400  * Elements in an algebraic extension are considered polynomials,
401  * and v may be algebraic.
402  *
403  * @sa InternalCF::degree(), InternalPoly::degree(),
404  * ::degree(), ::degree( v )
405 **/
406 int
408 {
409  int what = is_imm( value );
410 #if 0
411  if ( what )
412  if ( what == FFMARK )
413  return imm_iszero_p( value ) ? -1 : 0;
414  else if ( what == INTMARK )
415  return imm_iszero( value ) ? -1 : 0;
416  else
417  return imm_iszero_gf( value ) ? -1 : 0;
418  else if ( value->inBaseDomain() )
419  return value->degree();
420 #else
421  switch(what)
422  {
423  case FFMARK: return imm_iszero_p( value ) ? -1 : 0;
424  case INTMARK: return imm_iszero( value ) ? -1 : 0;
425  case GFMARK: return imm_iszero_gf( value ) ? -1 : 0;
426  case 0: if ( value->inBaseDomain() )
427  return value->degree();
428  break;
429  }
430 #endif
431 
432  Variable x = value->variable();
433  if ( v == x )
434  return value->degree();
435  else if ( v > x )
436  // relatively to v, f is in a coefficient ring
437  return 0;
438  else {
439  int coeffdeg, result = 0;
440  // search for maximum of coefficient degree
441  for ( CFIterator i = *this; i.hasTerms(); i++ ) {
442  coeffdeg = i.coeff().degree( v );
443  if ( coeffdeg > result )
444  result = coeffdeg;
445  }
446  return result;
447  }
448 }
449 
450 /**
451  *
452  * tailcoeff() - return least coefficient
453  *
454  * tailcoeff() returns the coefficient of the term with the least
455  * degree in CO where CO is considered an univariate polynomial
456  * in its main variable. Elements in an algebraic extension are
457  * considered coefficients.
458  *
459  * @sa CanonicalForm::taildegree(), InternalCF::tailcoeff(), InternalCF::tailcoeff(),
460  * InternalPoly::tailcoeff(), InternalPoly::taildegree,
461  * ::tailcoeff(), ::taildegree()
462  *
463 **/
466 {
467  if ( is_imm( value ) || value->inCoeffDomain() )
468  return *this;
469  else
470  return value->tailcoeff();
471 }
472 
473 /**
474  * tailcoeff( v ) returns the tail coefficient of CO where CO is
475  * considered an univariate polynomial in the polynomial variable
476  * v.
477  * Note: If v is less than the main variable of CO we have to
478  * swap variables which may be quite expensive.
479  *
480  * @sa CanonicalForm::taildegree(), InternalCF::tailcoeff(), InternalCF::tailcoeff(),
481  * InternalPoly::tailcoeff(), InternalPoly::taildegree,
482  * ::tailcoeff(), ::taildegree()
483 **/
486 {
487  if ( is_imm( value ) || value->inCoeffDomain() )
488  return *this;
489 
490  Variable x = value->variable();
491  if ( v > x )
492  return *this;
493  else if ( v == x )
494  return value->tailcoeff();
495  else {
496  CanonicalForm f = swapvar( *this, v, x );
497  if ( f.mvar() == x )
498  return swapvar( f.value->tailcoeff(), v, x );
499  else
500  // v did not occur in f
501  return *this;
502  }
503 }
504 
505 
506 /**
507  * taildegree() returns -1 for the zero polynomial, 0 if CO is in
508  * a base domain, otherwise the least degree of CO where CO is
509  * considered a univariate polynomial in its main variable. In
510  * contrast to tailcoeff(), elements in an algebraic extension
511  * are considered polynomials, not coefficients, and such may
512  * have a taildegree larger than zero.
513  *
514  * @sa CanonicalForm::tailcoeff(), InternalCF::tailcoeff(), InternalCF::tailcoeff(),
515  * InternalPoly::tailcoeff(), InternalPoly::taildegree,
516  * ::tailcoeff(), ::taildegree()
517 **/
518 int
520 {
521  int what = is_imm( value );
522  if ( what )
523  if ( what == FFMARK )
524  return imm_iszero_p( value ) ? -1 : 0;
525  else if ( what == INTMARK )
526  return imm_iszero( value ) ? -1 : 0;
527  else
528  return imm_iszero_gf( value ) ? -1 : 0;
529  else
530  return value->taildegree();
531 }
532 
533 /**
534  * level() returns the level of CO. For a list of the levels and
535  * their meanings, see cf_defs.h.
536  *
537  * @sa InternalCF::level(), InternalCF::variable(),
538  * InternalPoly::level(), InternalPoly::variable(), ::level(),
539  * ::mvar()
540  *
541 **/
542 int
544 {
545  if ( is_imm( value ) )
546  return LEVELBASE;
547  else
548  return value->level();
549 }
550 
551 /**
552  * mvar() returns the main variable of CO or Variable() if CO is
553  * in a base domain.
554  *
555  * @sa InternalCF::level(), InternalCF::variable(),
556  * InternalPoly::level(), InternalPoly::variable(), ::level(),
557  * ::mvar()
558 **/
559 Variable
561 {
562  if ( is_imm( value ) )
563  return Variable();
564  else
565  return value->variable();
566 }
567 
568 /**
569  * num() returns the numerator of CO if CO is a rational number,
570  * CO itself otherwise.
571  *
572  * @sa InternalCF::num(), InternalCF::den(),
573  * InternalRational::num(), InternalRational::den(), ::num(),
574  * ::den()
575  *
576 **/
579 {
580  if ( is_imm( value ) )
581  return *this;
582  else
583  return CanonicalForm( value->num() );
584 }
585 
586 /**
587  * den() returns the denominator of CO if CO is a rational
588  * number, 1 (from the current domain!) otherwise.
589  *
590  * @sa InternalCF::num(), InternalCF::den(),
591  * InternalRational::num(), InternalRational::den(), ::num(),
592  * ::den()
593 **/
596 {
597  if ( is_imm( value ) )
598  return CanonicalForm( 1 );
599  else
600  return CanonicalForm( value->den() );
601 }
602 
603 /** assignment operators **/
606 {
607  int what = is_imm( value );
608  if ( what ) {
609  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
610  if ( (what = is_imm( cf.value )) == FFMARK )
611  value = imm_add_p( value, cf.value );
612  else if ( what == GFMARK )
613  value = imm_add_gf( value, cf.value );
614  else if ( what )
615  value = imm_add( value, cf.value );
616  else {
617  InternalCF * dummy = cf.value->copyObject();
618  value = dummy->addcoeff( value );
619  }
620  }
621  else if ( is_imm( cf.value ) )
622  value = value->addcoeff( cf.value );
623  else if ( value->level() == cf.value->level() ) {
624  if ( value->levelcoeff() == cf.value->levelcoeff() )
625  value = value->addsame( cf.value );
626  else if ( value->levelcoeff() > cf.value->levelcoeff() )
627  value = value->addcoeff( cf.value );
628  else {
629  InternalCF * dummy = cf.value->copyObject();
630  dummy = dummy->addcoeff( value );
631  if ( value->deleteObject() ) delete value;
632  value = dummy;
633  }
634  }
635  else if ( level() > cf.level() )
636  value = value->addcoeff( cf.value );
637  else {
638  InternalCF * dummy = cf.value->copyObject();
639  dummy = dummy->addcoeff( value );
640  if ( value->deleteObject() ) delete value;
641  value = dummy;
642  }
643  return *this;
644 }
645 
648 {
649  int what = is_imm( value );
650  if ( what ) {
651  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
652  if ( (what = is_imm( cf.value )) == FFMARK )
653  value = imm_sub_p( value, cf.value );
654  else if ( what == GFMARK )
655  value = imm_sub_gf( value, cf.value );
656  else if ( what )
657  value = imm_sub( value, cf.value );
658  else {
659  InternalCF * dummy = cf.value->copyObject();
660  value = dummy->subcoeff( value, true );
661  }
662  }
663  else if ( is_imm( cf.value ) )
664  value = value->subcoeff( cf.value, false );
665  else if ( value->level() == cf.value->level() ) {
666  if ( value->levelcoeff() == cf.value->levelcoeff() )
667  value = value->subsame( cf.value );
668  else if ( value->levelcoeff() > cf.value->levelcoeff() )
669  value = value->subcoeff( cf.value, false );
670  else {
671  InternalCF * dummy = cf.value->copyObject();
672  dummy = dummy->subcoeff( value, true );
673  if ( value->deleteObject() ) delete value;
674  value = dummy;
675  }
676  }
677  else if ( level() > cf.level() )
678  value = value->subcoeff( cf.value, false );
679  else {
680  InternalCF * dummy = cf.value->copyObject();
681  dummy = dummy->subcoeff( value, true );
682  if ( value->deleteObject() ) delete value;
683  value = dummy;
684  }
685  return *this;
686 }
687 
690 {
691  int what = is_imm( value );
692  if ( what ) {
693  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
694  if ( (what = is_imm( cf.value )) == FFMARK )
695  value = imm_mul_p( value, cf.value );
696  else if ( what == GFMARK )
697  value = imm_mul_gf( value, cf.value );
698  else if ( what )
699  value = imm_mul( value, cf.value );
700  else {
701  InternalCF * dummy = cf.value->copyObject();
702  value = dummy->mulcoeff( value );
703  }
704  }
705  else if ( is_imm( cf.value ) )
706  value = value->mulcoeff( cf.value );
707  else if ( value->level() == cf.value->level() ) {
708 #if (HAVE_NTL && HAVE_FLINT && __FLINT_RELEASE >= 20400)
709  if (value->levelcoeff() == cf.value->levelcoeff() && cf.isUnivariate() && (*this).isUnivariate())
710  {
711  if (value->level() < 0 || CFFactory::gettype() == GaloisFieldDomain || (size (cf) <= 10 || size (*this) <= 10) )
712  value = value->mulsame( cf.value );
713  else
714  *this= mulNTL (*this, cf);
715  }
716  else if (value->levelcoeff() == cf.value->levelcoeff() && (!cf.isUnivariate() || !(*this).isUnivariate()))
717  value = value->mulsame( cf.value );
718 #else
719  if ( value->levelcoeff() == cf.value->levelcoeff() )
720  value = value->mulsame( cf.value );
721 #endif
722  else if ( value->levelcoeff() > cf.value->levelcoeff() )
723  value = value->mulcoeff( cf.value );
724  else {
725  InternalCF * dummy = cf.value->copyObject();
726  dummy = dummy->mulcoeff( value );
727  if ( value->deleteObject() ) delete value;
728  value = dummy;
729  }
730  }
731  else if ( level() > cf.level() )
732  value = value->mulcoeff( cf.value );
733  else {
734  InternalCF * dummy = cf.value->copyObject();
735  dummy = dummy->mulcoeff( value );
736  if ( value->deleteObject() ) delete value;
737  value = dummy;
738  }
739  return *this;
740 }
741 
744 {
745  int what = is_imm( value );
746  if ( what ) {
747  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
748  if ( (what = is_imm( cf.value )) == FFMARK )
749  value = imm_div_p( value, cf.value );
750  else if ( what == GFMARK )
751  value = imm_div_gf( value, cf.value );
752  else if ( what )
753  value = imm_divrat( value, cf.value );
754  else {
755  InternalCF * dummy = cf.value->copyObject();
756  value = dummy->dividecoeff( value, true );
757  }
758  }
759  else if ( is_imm( cf.value ) )
760  value = value->dividecoeff( cf.value, false );
761  else if ( value->level() == cf.value->level() ) {
762 #if (HAVE_NTL && HAVE_FLINT && __FLINT_RELEASE >= 20400)
763  if ( value->levelcoeff() == cf.value->levelcoeff() && (*this).isUnivariate() && cf.isUnivariate())
764  {
765  if (value->level() < 0 || CFFactory::gettype() == GaloisFieldDomain)
766  value = value->dividesame( cf.value );
767  else
768  *this= divNTL (*this, cf);
769  }
770  else if (value->levelcoeff() == cf.value->levelcoeff() && (!cf.isUnivariate() || !(*this).isUnivariate()))
771  value = value->dividesame( cf.value );
772 #else
773  if (value->levelcoeff() == cf.value->levelcoeff() )
774  value = value->dividesame( cf.value );
775 #endif
776  else if ( value->levelcoeff() > cf.value->levelcoeff() )
777  value = value->dividecoeff( cf.value, false );
778  else {
779  InternalCF * dummy = cf.value->copyObject();
780  dummy = dummy->dividecoeff( value, true );
781  if ( value->deleteObject() ) delete value;
782  value = dummy;
783  }
784  }
785  else if ( level() > cf.level() )
786  value = value->dividecoeff( cf.value, false );
787  else {
788  InternalCF * dummy = cf.value->copyObject();
789  dummy = dummy->dividecoeff( value, true );
790  if ( value->deleteObject() ) delete value;
791  value = dummy;
792  }
793  return *this;
794 }
795 
798 {
799  int what = is_imm( value );
800  if ( what ) {
801  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
802  if ( (what = is_imm( cf.value )) == FFMARK )
803  value = imm_div_p( value, cf.value );
804  else if ( what == GFMARK )
805  value = imm_div_gf( value, cf.value );
806  else if ( what )
807  value = imm_div( value, cf.value );
808  else {
809  InternalCF * dummy = cf.value->copyObject();
810  value = dummy->divcoeff( value, true );
811  }
812  }
813  else if ( is_imm( cf.value ) )
814  value = value->divcoeff( cf.value, false );
815  else if ( value->level() == cf.value->level() ) {
816  if ( value->levelcoeff() == cf.value->levelcoeff() )
817  value = value->divsame( cf.value );
818  else if ( value->levelcoeff() > cf.value->levelcoeff() )
819  value = value->divcoeff( cf.value, false );
820  else {
821  InternalCF * dummy = cf.value->copyObject();
822  dummy = dummy->divcoeff( value, true );
823  if ( value->deleteObject() ) delete value;
824  value = dummy;
825  }
826  }
827  else if ( level() > cf.level() )
828  value = value->divcoeff( cf.value, false );
829  else {
830  InternalCF * dummy = cf.value->copyObject();
831  dummy = dummy->divcoeff( value, true );
832  if ( value->deleteObject() ) delete value;
833  value = dummy;
834  }
835  return *this;
836 }
837 
838 ///same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
840 CanonicalForm::tryDiv ( const CanonicalForm & cf, const CanonicalForm& M, bool& fail )
841 {
842  ASSERT (getCharacteristic() > 0, "expected positive characteristic");
843  ASSERT (!getReduce (M.mvar()), "do not reduce modulo M");
844  fail= false;
845  int what = is_imm( value );
846  if ( what ) {
847  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
848  if ( (what = is_imm( cf.value )) == FFMARK )
849  value = imm_div_p( value, cf.value );
850  else if ( what == GFMARK )
851  value = imm_div_gf( value, cf.value );
852  else {
853  InternalCF * dummy = cf.value->copyObject();
854  value = dummy->divcoeff( value, true );
855  }
856  }
857  else if ( is_imm( cf.value ) )
858  value = value->tryDivcoeff (cf.value, false, M, fail);
859  else if ( value->level() == cf.value->level() ) {
860  if ( value->levelcoeff() == cf.value->levelcoeff() )
861  value = value->tryDivsame( cf.value, M, fail );
862  else if ( value->levelcoeff() > cf.value->levelcoeff() )
863  value = value->tryDivcoeff( cf.value, false, M, fail );
864  else {
865  InternalCF * dummy = cf.value->copyObject();
866  dummy = dummy->tryDivcoeff( value, true, M, fail );
867  if ( value->deleteObject() ) delete value;
868  value = dummy;
869  }
870  }
871  else if ( level() > cf.level() )
872  value = value->tryDivcoeff( cf.value, false, M, fail );
873  else {
874  InternalCF * dummy = cf.value->copyObject();
875  dummy = dummy->tryDivcoeff( value, true, M, fail );
876  if ( value->deleteObject() ) delete value;
877  value = dummy;
878  }
879  return *this;
880 }
881 
884 {
885  int what = is_imm( value );
886  if ( what ) {
887  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
888  if ( (what = is_imm( cf.value )) == FFMARK )
889  value = imm_mod_p( value, cf.value );
890  else if ( what == GFMARK )
891  value = imm_mod_gf( value, cf.value );
892  else if ( what )
893  value = imm_mod( value, cf.value );
894  else {
895  InternalCF * dummy = cf.value->copyObject();
896  value = dummy->modulocoeff( value, true );
897  }
898  }
899  else if ( is_imm( cf.value ) )
900  value = value->modulocoeff( cf.value, false );
901  else if ( value->level() == cf.value->level() ) {
902  if ( value->levelcoeff() == cf.value->levelcoeff() )
903  value = value->modulosame( cf.value );
904  else if ( value->levelcoeff() > cf.value->levelcoeff() )
905  value = value->modulocoeff( cf.value, false );
906  else {
907  InternalCF * dummy = cf.value->copyObject();
908  dummy = dummy->modulocoeff( value, true );
909  if ( value->deleteObject() ) delete value;
910  value = dummy;
911  }
912  }
913  else if ( level() > cf.level() )
914  value = value->modulocoeff( cf.value, false );
915  else {
916  InternalCF * dummy = cf.value->copyObject();
917  dummy = dummy->modulocoeff( value, true );
918  if ( value->deleteObject() ) delete value;
919  value = dummy;
920  }
921  return *this;
922 }
923 
926 {
927  int what = is_imm( value );
928  if ( what ) {
929  ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" );
930  if ( (what = is_imm( cf.value )) == FFMARK )
931  value = imm_mod_p( value, cf.value );
932  else if ( what == GFMARK )
933  value = imm_mod_gf( value, cf.value );
934  else if ( what )
935  value = imm_mod( value, cf.value );
936  else {
937  InternalCF * dummy = cf.value->copyObject();
938  value = dummy->modcoeff( value, true );
939  }
940  }
941  else if ( is_imm( cf.value ) )
942  value = value->modcoeff( cf.value, false );
943  else if ( value->level() == cf.value->level() ) {
944  if ( value->levelcoeff() == cf.value->levelcoeff() )
945  value = value->modsame( cf.value );
946  else if ( value->levelcoeff() > cf.value->levelcoeff() )
947  value = value->modcoeff( cf.value, false );
948  else {
949  InternalCF * dummy = cf.value->copyObject();
950  dummy = dummy->modcoeff( value, true );
951  if ( value->deleteObject() ) delete value;
952  value = dummy;
953  }
954  }
955  else if ( level() > cf.level() )
956  value = value->modcoeff( cf.value, false );
957  else {
958  InternalCF * dummy = cf.value->copyObject();
959  dummy = dummy->modcoeff( value, true );
960  if ( value->deleteObject() ) delete value;
961  value = dummy;
962  }
963  return *this;
964 }
965 
966 void
968 {
969  InternalCF * qq = 0, * rr = 0;
970  int what = is_imm( f.value );
971  if ( what )
972  if ( is_imm( g.value ) ) {
973  if ( what == FFMARK )
974  imm_divrem_p( f.value, g.value, qq, rr );
975  else if ( what == GFMARK )
976  imm_divrem_gf( f.value, g.value, qq, rr );
977  else
978  imm_divrem( f.value, g.value, qq, rr );
979  }
980  else
981  g.value->divremcoeff( f.value, qq, rr, true );
982  else if ( (what=is_imm( g.value )) )
983  f.value->divremcoeff( g.value, qq, rr, false );
984  else if ( f.value->level() == g.value->level() )
985  if ( f.value->levelcoeff() == g.value->levelcoeff() )
986  f.value->divremsame( g.value, qq, rr );
987  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
988  f.value->divremcoeff( g.value, qq, rr, false );
989  else
990  g.value->divremcoeff( f.value, qq, rr, true );
991  else if ( f.value->level() > g.value->level() )
992  f.value->divremcoeff( g.value, qq, rr, false );
993  else
994  g.value->divremcoeff( f.value, qq, rr, true );
995  ASSERT( qq != 0 && rr != 0, "error in divrem" );
996  q = CanonicalForm( qq );
997  r = CanonicalForm( rr );
998 }
999 
1000 bool
1002 {
1003  InternalCF * qq = 0, * rr = 0;
1004  int what = is_imm( f.value );
1005  bool result = true;
1006  if ( what )
1007  if ( is_imm( g.value ) ) {
1008  if ( what == FFMARK )
1009  imm_divrem_p( f.value, g.value, qq, rr );
1010  else if ( what == GFMARK )
1011  imm_divrem_gf( f.value, g.value, qq, rr );
1012  else
1013  imm_divrem( f.value, g.value, qq, rr );
1014  }
1015  else
1016  result = g.value->divremcoefft( f.value, qq, rr, true );
1017  else if ( (what=is_imm( g.value )) )
1018  result = f.value->divremcoefft( g.value, qq, rr, false );
1019  else if ( f.value->level() == g.value->level() )
1020  if ( f.value->levelcoeff() == g.value->levelcoeff() )
1021  result = f.value->divremsamet( g.value, qq, rr );
1022  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1023  result = f.value->divremcoefft( g.value, qq, rr, false );
1024  else
1025  result = g.value->divremcoefft( f.value, qq, rr, true );
1026  else if ( f.value->level() > g.value->level() )
1027  result = f.value->divremcoefft( g.value, qq, rr, false );
1028  else
1029  result = g.value->divremcoefft( f.value, qq, rr, true );
1030  if ( result ) {
1031  ASSERT( qq != 0 && rr != 0, "error in divrem" );
1032  q = CanonicalForm( qq );
1033  r = CanonicalForm( rr );
1034  }
1035  else {
1036  q = 0; r = 0;
1037  }
1038  return result;
1039 }
1040 
1041 ///same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
1042 bool
1043 tryDivremt ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const CanonicalForm& M, bool& fail )
1044 {
1045  ASSERT (getCharacteristic() > 0, "expected positive characteristic");
1046  ASSERT (!getReduce (M.mvar()), "do not reduce modulo M");
1047  fail= false;
1048  InternalCF * qq = 0, * rr = 0;
1049  int what = is_imm( f.value );
1050  bool result = true;
1051  if ( what )
1052  if ( is_imm( g.value ) ) {
1053  if ( what == FFMARK )
1054  imm_divrem_p( f.value, g.value, qq, rr );
1055  else if ( what == GFMARK )
1056  imm_divrem_gf( f.value, g.value, qq, rr );
1057  }
1058  else
1059  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1060  else if ( (what=is_imm( g.value )) )
1061  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1062  else if ( f.value->level() == g.value->level() )
1063  if ( f.value->levelcoeff() == g.value->levelcoeff() )
1064  result = f.value->tryDivremsamet( g.value, qq, rr, M, fail );
1065  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1066  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1067  else
1068  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1069  else if ( f.value->level() > g.value->level() )
1070  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1071  else
1072  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1073  if (fail)
1074  {
1075  q= 0;
1076  r= 0;
1077  return false;
1078  }
1079  if ( result ) {
1080  ASSERT( qq != 0 && rr != 0, "error in divrem" );
1081  q = CanonicalForm( qq );
1082  r = CanonicalForm( rr );
1083  q= reduce (q, M);
1084  r= reduce (r, M);
1085  }
1086  else {
1087  q = 0; r = 0;
1088  }
1089  return result;
1090 }
1091 
1092 /**
1093  *
1094  * operator ()() - evaluation operator.
1095  *
1096  * Returns CO if CO is in a base domain.
1097  *
1098  * operator () ( f ) returns CO with f inserted for the main
1099  * variable. Elements in an algebraic extension are considered
1100  * polynomials.
1101  *
1102 **/
1105 {
1106  if ( is_imm( value ) || value->inBaseDomain() )
1107  return *this;
1108  else {
1109 #if 0
1110  CFIterator i = *this;
1111  int lastExp = i.exp();
1112  CanonicalForm result = i.coeff();
1113  i++;
1114  while ( i.hasTerms() ) {
1115  if ( (lastExp - i.exp()) == 1 )
1116  result *= f;
1117  else
1118  result *= power( f, lastExp - i.exp() );
1119  result += i.coeff();
1120  lastExp = i.exp();
1121  i++;
1122  }
1123  if ( lastExp != 0 )
1124  result *= power( f, lastExp );
1125 #else
1126  CFIterator i = *this;
1127  int lastExp = i.exp();
1128  CanonicalForm result = i.coeff();
1129  i++;
1130  while ( i.hasTerms() )
1131  {
1132  int i_exp=i.exp();
1133  if ( (lastExp - i_exp /* i.exp()*/) == 1 )
1134  result *= f;
1135  else
1136  result *= power( f, lastExp - i_exp /*i.exp()*/ );
1137  result += i.coeff();
1138  lastExp = i_exp /*i.exp()*/;
1139  i++;
1140  }
1141  if ( lastExp != 0 )
1142  result *= power( f, lastExp );
1143 #endif
1144  return result;
1145  }
1146 }
1147 
1148 /**
1149  * Returns CO if CO is in a base domain.
1150  *
1151  * operator () ( f, v ) returns CO with f inserted for v.
1152  * Elements in an algebraic extension are considered polynomials
1153  * and v may be an algebraic variable.
1154 **/
1157 {
1158  if ( is_imm( value ) || value->inBaseDomain() )
1159  return *this;
1160 
1161  Variable x = value->variable();
1162  if ( v > x )
1163  return *this;
1164  else if ( v == x )
1165  return (*this)( f );
1166  else {
1167  // v is less than main variable of f
1168  CanonicalForm result = 0;
1169  for ( CFIterator i = *this; i.hasTerms(); i++ )
1170  result += i.coeff()( f, v ) * power( x, i.exp() );
1171  return result;
1172  }
1173 }
1174 
1175 /**
1176  *
1177  * operator []() - return i'th coefficient from CO.
1178  *
1179  * Returns CO if CO is in a base domain and i equals zero.
1180  * Returns zero (from the current domain) if CO is in a base
1181  * domain and i is larger than zero. Otherwise, returns the
1182  * coefficient to x^i in CO (if x denotes the main variable of
1183  * CO) or zero if CO does not contain x^i. Elements in an
1184  * algebraic extension are considered polynomials. i should be
1185  * larger or equal zero.
1186  *
1187  * Note: Never use a loop like
1188  *
1189 ~~~~~~~~~~~~~~~~~~~~~{.c}
1190  for ( int i = degree( f ); i >= 0; i-- )
1191  foo( i, f[ i ] );
1192 ~~~~~~~~~~~~~~~~~~~~~
1193  *
1194  * which is much slower than
1195  *
1196 ~~~~~~~~~~~~~~~~~~~~~{.c}
1197  * for ( int i = degree( f ), CFIterator I = f; I.hasTerms(); I++ ) {
1198  * // fill gap with zeroes
1199  * for ( ; i > I.exp(); i-- )
1200  * foo( i, 0 );
1201  * // at this point, i == I.exp()
1202  * foo( i, i.coeff() );
1203  * i--;
1204  * }
1205  * // work through trailing zeroes
1206  * for ( ; i >= 0; i-- )
1207  * foo( i, 0 );
1208 ~~~~~~~~~~~~~~~~~~~~~
1209  *
1210 **/
1213 {
1214  ASSERT( i >= 0, "index to operator [] less than zero" );
1215  if ( is_imm( value ) )
1216  if ( i == 0 )
1217  return *this;
1218  else
1219  return CanonicalForm( 0 );
1220  else
1221  return value->coeff( i );
1222 }
1223 
1224 /**
1225  *
1226  * deriv() - return the formal derivation of CO.
1227  *
1228  * deriv() derives CO with respect to its main variable. Returns
1229  * zero from the current domain if f is in a coefficient domain.
1230  *
1231  * @sa CanonicalForm::deriv ( const Variable & x )
1232  *
1233 **/
1236 {
1237  if ( is_imm( value ) || value->inCoeffDomain() )
1238  return CanonicalForm( 0 );
1239  else {
1240  CanonicalForm result = 0;
1241  Variable x = value->variable();
1242  for ( CFIterator i = *this; i.hasTerms(); i++ )
1243  if ( i.exp() > 0 )
1244  result += power( x, i.exp()-1 ) * i.coeff() * i.exp();
1245  return result;
1246  }
1247 }
1248 
1249 /**
1250  * deriv( x ) derives CO with respect to x. x should be a
1251  * polynomial variable. Returns zero from the current domain if
1252  * f is in a coefficient domain.
1253 **/
1256 {
1257  ASSERT( x.level() > 0, "cannot derive with respect to algebraic variables" );
1258  if ( is_imm( value ) || value->inCoeffDomain() )
1259  return CanonicalForm( 0 );
1260 
1261  Variable y = value->variable();
1262  if ( x > y )
1263  return CanonicalForm( 0 );
1264  else if ( x == y )
1265  return deriv();
1266  else {
1267  CanonicalForm result = 0;
1268  for ( CFIterator i = *this; i.hasTerms(); i++ )
1269  result += i.coeff().deriv( x ) * power( y, i.exp() );
1270  return result;
1271  }
1272 }
1273 
1274 /** int CanonicalForm::sign () const
1275  *
1276  * sign() - return sign of CO.
1277  *
1278  * If CO is an integer or a rational number, the sign is defined
1279  * as usual. If CO is an element of a prime power domain or of
1280  * FF(p) and SW_SYMMETRIC_FF is on, the sign of CO is the sign of
1281  * the symmetric representation of CO. If CO is in GF(q) or in
1282  * FF(p) and SW_SYMMETRIC_FF is off, the sign of CO is zero iff
1283  * CO is zero, otherwise the sign is one.
1284  *
1285  * If CO is a polynomial or in an extension of one of the base
1286  * domains, the sign of CO is the sign of its leading
1287  * coefficient.
1288  *
1289  * @sa InternalCF::sign(), InternalInteger::sign(),
1290  * InternalRational::sign(),
1291  * InternalPoly::sign(), imm_sign(), gf_sign()
1292  *
1293 **/
1294 int
1296 {
1297  if ( is_imm( value ) )
1298  return imm_sign( value );
1299  else
1300  return value->sign();
1301 }
1302 
1303 /** CanonicalForm CanonicalForm::sqrt () const
1304  *
1305  * sqrt() - calculate integer square root.
1306  *
1307  * CO has to be an integer greater or equal zero. Returns the
1308  * largest integer less or equal sqrt(CO).
1309  *
1310  * In the immediate case, we use the newton method to find the
1311  * root. The algorithm is from H. Cohen - 'A Course in
1312  * Computational Algebraic Number Theory', ch. 1.7.1.
1313  *
1314  * @sa InternalCF::sqrt(), InternalInteger::sqrt(), ::sqrt()
1315  *
1316 **/
1319 {
1320  if ( is_imm( value ) ) {
1321  ASSERT( is_imm( value ) == INTMARK, "sqrt() not implemented" );
1322  long n = imm2int( value );
1323  ASSERT( n >= 0, "arg to sqrt() less than zero" );
1324  if ( n == 0 || n == 1 )
1325  return CanonicalForm( n );
1326  else {
1327  long x, y = n;
1328  do {
1329  x = y;
1330  // the intermediate result may not fit into an
1331  // integer, but the result does
1332  y = (unsigned long)(x + n/x)/2;
1333  } while ( y < x );
1334  return CanonicalForm( x );
1335  }
1336  }
1337  else
1338  return CanonicalForm( value->sqrt() );
1339 }
1340 
1341 /** int CanonicalForm::ilog2 () const
1342  *
1343  * ilog2() - integer logarithm to base 2.
1344  *
1345  * Returns the largest integer less or equal logarithm of CO to
1346  * base 2. CO should be a positive integer.
1347  *
1348  * @sa InternalCF::ilog2(), InternalInteger::ilog2(), ::ilog2()
1349  *
1350 **/
1351 int
1353 {
1354  if ( is_imm( value ) )
1355  {
1356  ASSERT( is_imm( value ) == INTMARK, "ilog2() not implemented" );
1357  long a = imm2int( value );
1358  ASSERT( a > 0, "arg to ilog2() less or equal zero" );
1359  int n = -1;
1360  while ( a > 0 )
1361  {
1362  n++;
1363  a /=2;
1364  }
1365  return n;
1366  }
1367  else
1368  return value->ilog2();
1369 }
1370 
1371 /**
1372  *
1373  * operator ==() - compare canonical forms on
1374  * (in)equality.
1375  *
1376  * operator ==() returns true iff lhs equals rhs.
1377  *
1378  * This is the point in factory where we essentially use that
1379  * CanonicalForms in fact are canonical. There must not be two
1380  * different representations of the same mathematical object,
1381  * otherwise, such (in)equality will not be recognized by these
1382  * operators. In other word, we rely on the fact that structural
1383  * different factory objects in any case represent different
1384  * mathematical objects.
1385  *
1386  * So we use the following procedure to test on equality (and
1387  * analogously on inequality). First, we check whether lhs.value
1388  * equals rhs.value. If so we are ready and return true.
1389  * Second, if one of the operands is immediate, but the other one
1390  * not, we return false. Third, if the operand's levels differ
1391  * we return false. Fourth, if the operand's levelcoeffs differ
1392  * we return false. At last, we call the corresponding internal
1393  * method to compare both operands.
1394  *
1395  * Both operands should have coefficients from the same base domain.
1396  *
1397  * Note: To compare with the zero or the unit of the current domain,
1398  * you better use the methods `CanonicalForm::isZero()' or
1399  * `CanonicalForm::isOne()', resp., than something like `f == 0',
1400  * since the latter is quite a lot slower.
1401  *
1402  * @sa CanonicalForm::operator !=(), InternalCF::comparesame(),
1403  * InternalInteger::comparesame(), InternalRational::comparesame(),
1404  * InternalPoly::comparesame()
1405  *
1406 **/
1407 bool
1408 operator == ( const CanonicalForm & lhs, const CanonicalForm & rhs )
1409 {
1410  if ( lhs.value == rhs.value )
1411  return true;
1412  else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
1413  ASSERT( ! is_imm( rhs.value ) ||
1414  ! is_imm( lhs.value ) ||
1415  is_imm( rhs.value ) == is_imm( lhs.value ),
1416  "incompatible operands" );
1417  return false;
1418  }
1419  else if ( lhs.value->level() != rhs.value->level() )
1420  return false;
1421  else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
1422  return false;
1423  else
1424  return rhs.value->comparesame( lhs.value ) == 0;
1425 }
1426 
1427 /**
1428  * operator !=() returns true iff lhs does not equal rhs.
1429  *
1430  * @sa CanonicalForm::operator ==()
1431 **/
1432 bool
1433 operator != ( const CanonicalForm & lhs, const CanonicalForm & rhs )
1434 {
1435  if ( lhs.value == rhs.value )
1436  return false;
1437  else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
1438  ASSERT( ! is_imm( rhs.value ) ||
1439  ! is_imm( lhs.value ) ||
1440  is_imm( rhs.value ) == is_imm( lhs.value ),
1441  "incompatible operands" );
1442  return true;
1443  }
1444  else if ( lhs.value->level() != rhs.value->level() )
1445  return true;
1446  else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
1447  return true;
1448  else return rhs.value->comparesame( lhs.value ) != 0;
1449 }
1450 
1451 /**
1452  *
1453  * operator >() - compare canonical forms. on size or
1454  * level.
1455  *
1456  * The most common and most useful application of these operators
1457  * is to compare two integers or rationals, of course. However,
1458  * these operators are defined on all other base domains and on
1459  * polynomials, too. From a mathematical point of view this may
1460  * seem meaningless, since there is no ordering on finite fields
1461  * or on polynomials respecting the algebraic structure.
1462  * Nevertheless, from a programmer's point of view it may be
1463  * sensible to order these objects, e.g. to sort them.
1464  *
1465  * Therefore, the ordering defined by these operators in any case
1466  * is a total ordering which fulfills the law of trichotomy.
1467  *
1468  * It is clear how this is done in the case of the integers and
1469  * the rationals. For finite fields, all you can say is that
1470  * zero is the minimal element w.r.t. the ordering, the other
1471  * elements are ordered in an arbitrary (but total!) way. For
1472  * polynomials, you have an ordering derived from the
1473  * lexicographical ordering of monomials. E.g. if lm(f) < lm(g)
1474  * w.r.t. lexicographic ordering, then f < g. For more details,
1475  * refer to the documentation of `InternalPoly::operator <()'.
1476  *
1477  * Both operands should have coefficients from the same base domain.
1478  *
1479  * The scheme how both operators are implemented is allmost the
1480  * same as for the assignment operators (check for immediates,
1481  * then check levels, then check levelcoeffs, then call the
1482  * appropriate internal comparesame()/comparecoeff() method).
1483  * For more information, confer to the overview for the
1484  * arithmetic operators.
1485  *
1486  * @sa CanonicalForm::operator <(), InternalCF::comparesame(),
1487  * InternalInteger::comparesame(), InternalRational::comparesame(),
1488  * InternalPoly::comparesame(),
1489  * InternalCF::comparecoeff(), InternalInteger::comparecoeff(),
1490  * InternalRational::comparecoeff(),
1491  * InternalPoly::comparecoeff(),
1492  * imm_cmp(), imm_cmp_p(), imm_cmp_gf()
1493  *
1494 **/
1495 bool
1496 operator > ( const CanonicalForm & lhs, const CanonicalForm & rhs )
1497 {
1498  int what = is_imm( rhs.value );
1499  if ( is_imm( lhs.value ) ) {
1500  ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
1501  if ( what == 0 )
1502  return rhs.value->comparecoeff( lhs.value ) < 0;
1503  else if ( what == INTMARK )
1504  return imm_cmp( lhs.value, rhs.value ) > 0;
1505  else if ( what == FFMARK )
1506  return imm_cmp_p( lhs.value, rhs.value ) > 0;
1507  else
1508  return imm_cmp_gf( lhs.value, rhs.value ) > 0;
1509  }
1510  else if ( what )
1511  return lhs.value->comparecoeff( rhs.value ) > 0;
1512  else if ( lhs.value->level() == rhs.value->level() )
1513  if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
1514  return lhs.value->comparesame( rhs.value ) > 0;
1515  else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
1516  return lhs.value->comparecoeff( rhs.value ) > 0;
1517  else
1518  return rhs.value->comparecoeff( lhs.value ) < 0;
1519  else
1520  return lhs.value->level() > rhs.value->level();
1521 }
1522 
1523 /**
1524  * @sa CanonicalForm::operator >()
1525 **/
1526 bool
1527 operator < ( const CanonicalForm & lhs, const CanonicalForm & rhs )
1528 {
1529  int what = is_imm( rhs.value );
1530  if ( is_imm( lhs.value ) ) {
1531  ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
1532  if ( what == 0 )
1533  return rhs.value->comparecoeff( lhs.value ) > 0;
1534  else if ( what == INTMARK )
1535  return imm_cmp( lhs.value, rhs.value ) < 0;
1536  else if ( what == FFMARK )
1537  return imm_cmp_p( lhs.value, rhs.value ) < 0;
1538  else
1539  return imm_cmp_gf( lhs.value, rhs.value ) < 0;
1540  }
1541  else if ( what )
1542  return lhs.value->comparecoeff( rhs.value ) < 0;
1543  else if ( lhs.value->level() == rhs.value->level() )
1544  if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
1545  return lhs.value->comparesame( rhs.value ) < 0;
1546  else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
1547  return lhs.value->comparecoeff( rhs.value ) < 0;
1548  else
1549  return rhs.value->comparecoeff( lhs.value ) > 0;
1550  else
1551  return lhs.value->level() < rhs.value->level();
1552 }
1553 
1554 /** CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
1555  *
1556  * bgcd() - return base coefficient gcd.
1557  *
1558  * If both f and g are integers and `SW_RATIONAL' is off the
1559  * positive greatest common divisor of f and g is returned.
1560  * Otherwise, if `SW_RATIONAL' is on or one of f and g is not an
1561  * integer, the greatest common divisor is trivial: either zero
1562  * if f and g equal zero or one (both from the current domain).
1563  *
1564  * f and g should come from one base domain which should be not
1565  * the prime power domain.
1566  *
1567  * Implementation:
1568  *
1569  * CanonicalForm::bgcd() handles the immediate case with a
1570  * standard euclidean algorithm. For the non-immediate cases
1571  * `InternalCF::bgcdsame()' or `InternalCF::bgcdcoeff()', resp. are
1572  * called following the usual level/levelcoeff approach.
1573  *
1574  * InternalCF::bgcdsame() and
1575  * InternalCF::bgcdcoeff() throw an assertion ("not implemented")
1576  *
1577  * InternalInteger::bgcdsame() is a wrapper around `mpz_gcd()'
1578  * which takes some care about immediate results and the sign
1579  * of the result
1580  * InternalInteger::bgcdcoeff() is a wrapper around
1581  * `mpz_gcd_ui()' which takes some care about the sign
1582  * of the result
1583  *
1584  * InternalRational::bgcdsame() and
1585  * InternalRational::bgcdcoeff() always return one
1586  *
1587 **/
1589 bgcd ( const CanonicalForm & f, const CanonicalForm & g )
1590 {
1591  // check immediate cases
1592  int what = is_imm( g.value );
1593  if ( is_imm( f.value ) )
1594  {
1595  ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
1596  if ( what == 0 )
1597  return g.value->bgcdcoeff( f.value );
1598  else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) )
1599  {
1600  // calculate gcd using standard integer
1601  // arithmetic
1602  long fInt = imm2int( f.value );
1603  long gInt = imm2int( g.value );
1604 
1605  if ( fInt < 0 ) fInt = -fInt;
1606  if ( gInt < 0 ) gInt = -gInt;
1607  // swap fInt and gInt
1608  if ( gInt > fInt )
1609  {
1610  long swap = gInt;
1611  gInt = fInt;
1612  fInt = swap;
1613  }
1614 
1615  // now, 0 <= gInt <= fInt. Start the loop.
1616  while ( gInt )
1617  {
1618  // calculate (fInt, gInt) = (gInt, fInt%gInt)
1619  long r = fInt % gInt;
1620  fInt = gInt;
1621  gInt = r;
1622  }
1623 
1624  return CanonicalForm( fInt );
1625  }
1626  else
1627  // we do not go for maximal speed for these stupid
1628  // special cases
1629  return CanonicalForm( f.isZero() && g.isZero() ? 0 : 1 );
1630  }
1631  else if ( what )
1632  return f.value->bgcdcoeff( g.value );
1633 
1634  int fLevel = f.value->level();
1635  int gLevel = g.value->level();
1636 
1637  // check levels
1638  if ( fLevel == gLevel )
1639  {
1640  fLevel = f.value->levelcoeff();
1641  gLevel = g.value->levelcoeff();
1642 
1643  // check levelcoeffs
1644  if ( fLevel == gLevel )
1645  return f.value->bgcdsame( g.value );
1646  else if ( fLevel < gLevel )
1647  return g.value->bgcdcoeff( f.value );
1648  else
1649  return f.value->bgcdcoeff( g.value );
1650  }
1651  else if ( fLevel < gLevel )
1652  return g.value->bgcdcoeff( f.value );
1653  else
1654  return f.value->bgcdcoeff( g.value );
1655 }
1656 
1657 /** CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
1658  *
1659  * bextgcd() - return base coefficient extended gcd.
1660  *
1661 **/
1664 {
1665  // check immediate cases
1666  int what = is_imm( g.value );
1667  if ( is_imm( f.value ) ) {
1668  ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
1669  if ( what == 0 )
1670  return g.value->bextgcdcoeff( f.value, b, a );
1671  else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) {
1672  // calculate extended gcd using standard integer
1673  // arithmetic
1674  long fInt = imm2int( f.value );
1675  long gInt = imm2int( g.value );
1676 
1677  // to avoid any system dpendencies with `%', we work
1678  // with positive numbers only. To a pity, we have to
1679  // redo all the checks when assigning to a and b.
1680  if ( fInt < 0 ) fInt = -fInt;
1681  if ( gInt < 0 ) gInt = -gInt;
1682  // swap fInt and gInt
1683  if ( gInt > fInt ) {
1684  long swap = gInt;
1685  gInt = fInt;
1686  fInt = swap;
1687  }
1688 
1689  long u = 1; long v = 0;
1690  long uNext = 0; long vNext = 1;
1691 
1692  // at any step, we have:
1693  // fInt_0 * u + gInt_0 * v = fInt
1694  // fInt_0 * uNext + gInt_0 * vNext = gInt
1695  // where fInt_0 and gInt_0 denote the values of fint
1696  // and gInt, resp., at the beginning
1697  while ( gInt ) {
1698  long r = fInt % gInt;
1699  long q = fInt / gInt;
1700  long uSwap = u - q * uNext;
1701  long vSwap = v - q * vNext;
1702 
1703  // update variables
1704  fInt = gInt;
1705  gInt = r;
1706  u = uNext; v = vNext;
1707  uNext = uSwap; vNext = vSwap;
1708  }
1709 
1710  // now, assign to a and b
1711  long fTest = imm2int( f.value );
1712  long gTest = imm2int( g.value );
1713  if ( gTest > fTest ) {
1714  a = v; b = u;
1715  } else {
1716  a = u; b = v;
1717  }
1718  if ( fTest < 0 ) a = -a;
1719  if ( gTest < 0 ) b = -b;
1720  return CanonicalForm( fInt );
1721  } else
1722  // stupid special cases
1723  if ( ! f.isZero() ) {
1724  a = 1/f; b = 0; return CanonicalForm( 1L );
1725  } else if ( ! g.isZero() ) {
1726  a = 0; b = 1/g; return CanonicalForm( 1L );
1727  } else {
1728  a = 0; b = 0; return CanonicalForm( 0L );
1729  }
1730  }
1731  else if ( what )
1732  return f.value->bextgcdcoeff( g.value, a, b );
1733 
1734  int fLevel = f.value->level();
1735  int gLevel = g.value->level();
1736 
1737  // check levels
1738  if ( fLevel == gLevel ) {
1739  fLevel = f.value->levelcoeff();
1740  gLevel = g.value->levelcoeff();
1741 
1742  // check levelcoeffs
1743  if ( fLevel == gLevel )
1744  return f.value->bextgcdsame( g.value, a, b );
1745  else if ( fLevel < gLevel )
1746  return g.value->bextgcdcoeff( f.value, b, a );
1747  else
1748  return f.value->bextgcdcoeff( g.value, a, b );
1749  }
1750  else if ( fLevel < gLevel )
1751  return g.value->bextgcdcoeff( f.value, b, a );
1752  else
1753  return f.value->bextgcdcoeff( g.value, a, b );
1754 }
1755 
1757 blcm ( const CanonicalForm & f, const CanonicalForm & g )
1758 {
1759  if ( f.isZero() || g.isZero() )
1760  return CanonicalForm( 0L );
1761 /*
1762  else if (f.isOne())
1763  return g;
1764  else if (g.isOne())
1765  return f;
1766 */
1767  else
1768  return (f / bgcd( f, g )) * g;
1769 }
1770 
1771 /** input/output **/
1772 #ifndef NOSTREAMIO
1773 void
1774 CanonicalForm::print( OSTREAM & os, char * str ) const
1775 {
1776  if ( is_imm( value ) )
1777  imm_print( os, value, str );
1778  else
1779  value->print( os, str );
1780 }
1781 
1782 void
1784 {
1785  if ( is_imm( value ) )
1786  imm_print( os, value, "" );
1787  else
1788  value->print( os, "" );
1789 }
1790 
1791 OSTREAM&
1793 {
1794  cf.print( os, "" );
1795  return os;
1796 }
1797 
1798 ISTREAM&
1800 {
1801  cf = readCF( is );
1802  return is;
1803 }
1804 #endif /* NOSTREAMIO */
1805 
1806 /** genOne(), genZero() **/
1809 {
1810  int what = is_imm( value );
1811  if ( what == FFMARK )
1813  else if ( what == GFMARK )
1815  else if ( what )
1816  return CanonicalForm( CFFactory::basic( IntegerDomain, 0L ) );
1817  else
1818  return CanonicalForm( value->genZero() );
1819 }
1820 
1823 {
1824  int what = is_imm( value );
1825  if ( what == FFMARK )
1827  else if ( what == GFMARK )
1829  else if ( what )
1830  return CanonicalForm( CFFactory::basic( IntegerDomain, 1L ) );
1831  else
1832  return CanonicalForm( value->genOne() );
1833 }
1834 
1835 /** exponentiation **/
1837 power ( const CanonicalForm & f, int n )
1838 {
1839  ASSERT( n >= 0, "illegal exponent" );
1840  if ( f.isZero() )
1841  return CanonicalForm(0L);
1842  else if ( f.isOne() )
1843  return f;
1844  else if ( f == -1 )
1845  {
1846  if ( n % 2 == 0 )
1847  return CanonicalForm(1L);
1848  else
1849  return CanonicalForm(-1L);
1850  }
1851  else if ( n == 0 )
1852  return CanonicalForm(1L);
1853 
1854  //else if (f.inGF())
1855  //{
1856  //}
1857  else
1858  {
1859  CanonicalForm g,h;
1860  h=f;
1861  while(n%2==0)
1862  {
1863  h*=h;
1864  n/=2;
1865  }
1866  g=h;
1867  while(1)
1868  {
1869  n/=2;
1870  if(n==0)
1871  return g;
1872  h*=h;
1873  if(n%2!=0) g*=h;
1874  }
1875  }
1876 }
1877 
1878 /** exponentiation **/
1880 power ( const Variable & v, int n )
1881 {
1882  //ASSERT( n >= 0, "illegal exponent" );
1883  if ( n == 0 )
1884  return 1;
1885  else if ( n == 1 )
1886  return v;
1887  else if (( v.level() < 0 ) && (hasMipo(v)))
1888  {
1889  CanonicalForm result( v, n-1 );
1890  return result * v;
1891  }
1892  else
1893  return CanonicalForm( v, n );
1894 }
1895 
1896 /** switches **/
1897 void
1898 On( int sw )
1899 {
1900  cf_glob_switches.On( sw );
1901 }
1902 
1903 /** switches **/
1904 void
1905 Off( int sw )
1906 {
1907  cf_glob_switches.Off( sw );
1908 }
1909 
1910 /** switches **/
1911 bool
1912 isOn( int sw )
1913 {
1914  return cf_glob_switches.isOn( sw );
1915 }
hasMipo
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226
cf_glob_switches
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:41
InternalCF::intval
virtual long intval() const
Definition: int_cf.cc:165
InternalCF::degree
virtual int degree()
int InternalCF::degree ()
Definition: int_cf.cc:55
operator<
bool operator<(const CanonicalForm &lhs, const CanonicalForm &rhs)
Definition: canonicalform.cc:1527
GFMARK
const long GFMARK
Definition: imm.h:39
InternalCF::mulsame
virtual InternalCF * mulsame(InternalCF *) PVIRT_INTCF("mulsame")
CanonicalForm::operator/=
CanonicalForm & operator/=(const CanonicalForm &)
Definition: canonicalform.cc:743
CanonicalForm::print
void print(OSTREAM &, char *) const
input/output
Definition: canonicalform.cc:1774
imm_add_p
InternalCF * imm_add_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:278
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
imm_mod
InternalCF * imm_mod(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:394
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
imm_mul
InternalCF * imm_mul(InternalCF *lhs, InternalCF *rhs)
Definition: imm.h:308
CanonicalForm::inQ
bool inQ() const
Definition: canonicalform.cc:77
imm_print
void imm_print(OSTREAM &os, const InternalCF *const op, const char *const str)
Definition: imm.h:476
f
FILE * f
Definition: checklibs.c:9
CanonicalForm::inQuotDomain
bool inQuotDomain() const
Definition: canonicalform.cc:137
InternalCF::inBaseDomain
virtual bool inBaseDomain() const
Definition: int_cf.h:74
CanonicalForm::div
CanonicalForm & div(const CanonicalForm &)
Definition: canonicalform.cc:797
getmpi
void getmpi(InternalCF *value, mpz_t mpi)
Definition: cf_factory.cc:260
canonicalform.h
CanonicalForm::tryDiv
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
Definition: canonicalform.cc:840
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
CFSwitches::Off
void Off(int s)
switch 's' off
Definition: cf_switches.h:53
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm::LC
CanonicalForm LC() const
Definition: canonicalform.cc:334
operator>>
ISTREAM & operator>>(ISTREAM &is, CanonicalForm &cf)
Definition: canonicalform.cc:1799
result
return result
Definition: facAbsBiFact.cc:76
CanonicalForm::operator-=
CanonicalForm & operator-=(const CanonicalForm &)
Definition: canonicalform.cc:647
RationalDomain
#define RationalDomain
Definition: cf_defs.h:25
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
imm_mul_gf
InternalCF * imm_mul_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:351
InternalCF::modulosame
virtual InternalCF * modulosame(InternalCF *) PVIRT_INTCF("modulosame")
InternalCF::divsame
virtual InternalCF * divsame(InternalCF *) PVIRT_INTCF("divsame")
h
STATIC_VAR Poly * h
Definition: janet.cc:971
CxxTest::base
char N base
Definition: ValueTraits.h:144
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
reduce
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition: cf_ops.cc:646
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
imm_divrem_gf
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:446
g
g
Definition: cfModGcd.cc:4031
InternalCF::tailcoeff
virtual CanonicalForm tailcoeff()
CanonicalForm InternalCF::tailcoeff (), int InternalCF::taildegree ()
Definition: int_cf.cc:67
ff_prime
VAR int ff_prime
Definition: ffops.cc:14
CanonicalForm::isHomogeneous
bool isHomogeneous() const
Definition: canonicalform.cc:162
InternalCF::subsame
virtual InternalCF * subsame(InternalCF *) PVIRT_INTCF("subsame")
InternalCF::taildegree
virtual int taildegree()
Definition: int_cf.cc:73
CanonicalForm::sign
int sign() const
int CanonicalForm::sign () const
Definition: canonicalform.cc:1295
InternalCF
virtual class for internal CanonicalForm's
Definition: int_cf.h:41
InternalCF::addsame
virtual InternalCF * addsame(InternalCF *) PVIRT_INTCF("addsame")
InternalCF::intmod
virtual int intmod(int) const
Definition: int_cf.h:83
InternalCF::comparesame
virtual int comparesame(InternalCF *) PVIRT_INT("comparesame")
InternalCF::genZero
virtual InternalCF * genZero() PVIRT_INTCF("genZero")
CanonicalForm::isImm
bool isImm() const
Definition: canonicalform.h:107
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm::ilog2
int ilog2() const
int CanonicalForm::ilog2 () const
Definition: canonicalform.cc:1352
CanonicalForm::inGF
bool inGF() const
Definition: canonicalform.cc:95
CanonicalForm::num
CanonicalForm num() const
num() returns the numerator of CO if CO is a rational number, CO itself otherwise.
Definition: canonicalform.cc:578
CanonicalForm::tailcoeff
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
Definition: canonicalform.cc:465
CanonicalForm
factory's main class
Definition: canonicalform.h:77
CanonicalForm::value
InternalCF * value
Definition: canonicalform.h:85
ff_symmetric
int ff_symmetric(const int a)
Definition: ffops.h:67
InternalCF::subcoeff
virtual InternalCF * subcoeff(InternalCF *, bool) PVIRT_INTCF("subcoeff")
cf_globals.h
CanonicalForm::intval
long intval() const
conversion functions
Definition: canonicalform.cc:197
CanonicalForm::operator[]
CanonicalForm operator[](int i) const
operator []() - return i'th coefficient from CO.
Definition: canonicalform.cc:1212
InternalCF::print
virtual void print(OSTREAM &, char *) PVIRT_VOID("print")
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition: canonicalform.cc:967
InternalCF::copyObject
InternalCF * copyObject()
Definition: int_cf.h:62
gf_gf2ff
long gf_gf2ff(long a)
Definition: gfops.cc:226
InternalCF::level
virtual int level() const
Definition: int_cf.h:67
CanonicalForm::genOne
CanonicalForm genOne() const
Definition: canonicalform.cc:1822
operator!=
bool operator!=(const CanonicalForm &lhs, const CanonicalForm &rhs)
operator !=() returns true iff lhs does not equal rhs.
Definition: canonicalform.cc:1433
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:23
CanonicalForm::Lc
CanonicalForm Lc() const
Definition: canonicalform.cc:319
i
int i
Definition: cfEzgcd.cc:125
imm_div_p
InternalCF * imm_div_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:384
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
InternalCF::levelcoeff
virtual int levelcoeff() const
Definition: int_cf.h:68
mulNTL
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition: facMul.cc:407
CanonicalForm::mpzval
void mpzval(mpz_t val) const
Definition: canonicalform.cc:49
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
INTMARK
const long INTMARK
Definition: imm.h:37
M
#define M
Definition: sirandom.c:25
FFMARK
const long FFMARK
Definition: imm.h:38
int2imm
static InternalCF * int2imm(long i)
Definition: imm.h:75
CanonicalForm::isFFinGF
bool isFFinGF() const
Definition: canonicalform.cc:146
InternalCF::isUnivariate
virtual bool isUnivariate() const
Definition: int_cf.h:81
InternalCF::addcoeff
virtual InternalCF * addcoeff(InternalCF *) PVIRT_INTCF("addcoeff")
imm_sign
int imm_sign(const InternalCF *const op)
imm_sign() - return sign of immediate object.
Definition: imm.h:197
imm_divrem
void imm_divrem(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:428
cf_defs.h
int_cf.h
InternalCF::LC
virtual CanonicalForm LC()
Definition: int_cf.cc:46
cf_iter.h
CanonicalForm::deepCopy
CanonicalForm deepCopy() const
Definition: canonicalform.cc:40
CanonicalForm::deriv
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
Definition: canonicalform.cc:1235
gf_isff
bool gf_isff(long a)
Definition: gfops.cc:270
imm_cmp_gf
int imm_cmp_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:256
CFFactory::basic
static InternalCF * basic(long value)
Definition: cf_factory.cc:30
tryDivremt
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
Definition: canonicalform.cc:1043
gInt
static long gInt(number &a, const coeffs)
Definition: generics.cc:147
InternalCF::inCoeffDomain
virtual bool inCoeffDomain() const
Definition: int_cf.h:76
InternalCF::coeff
virtual CanonicalForm coeff(int i)
CanonicalForm InternalCF::coeff ( int i )
Definition: int_cf.cc:120
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
InternalCF::sqrt
virtual InternalCF * sqrt()
InternalCF * InternalCF::sqrt ()
Definition: int_cf.cc:100
gfops.h
CanonicalForm::CanonicalForm
CF_INLINE CanonicalForm()
CF_INLINE CanonicalForm::CanonicalForm ()
Definition: cf_inline.cc:126
cf_algorithm.h
CFFactory
Definition: cf_factory.h:23
InternalCF::modcoeff
virtual InternalCF * modcoeff(InternalCF *, bool) PVIRT_INTCF("modcoeff")
imm_sub_p
InternalCF * imm_sub_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:297
divNTL
CanonicalForm divNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z,...
Definition: facMul.cc:850
imm_add
InternalCF * imm_add(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:269
InternalCF::genOne
virtual InternalCF * genOne() PVIRT_INTCF("genOne")
operator==
bool operator==(const CanonicalForm &lhs, const CanonicalForm &rhs)
operator ==() - compare canonical forms on (in)equality.
Definition: canonicalform.cc:1408
FiniteFieldDomain
#define FiniteFieldDomain
Definition: cf_defs.h:24
imm_cmp
int imm_cmp(const InternalCF *const lhs, const InternalCF *const rhs)
imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
Definition: imm.h:234
Variable::level
int level() const
Definition: factory.h:134
imm_mod_gf
InternalCF * imm_mod_gf(const InternalCF *const, const InternalCF *const)
Definition: imm.h:423
InternalCF::Lc
virtual CanonicalForm Lc()
Definition: int_cf.cc:40
CanonicalForm::sqrt
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
Definition: canonicalform.cc:1318
CanonicalForm::operator%=
CanonicalForm & operator%=(const CanonicalForm &)
Definition: canonicalform.cc:883
FLINTconvert.h
imm.h
InternalCF::tryDivcoeff
virtual InternalCF * tryDivcoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition: int_cf.cc:214
imm_iszero_p
int imm_iszero_p(const InternalCF *const ptr)
Definition: imm.h:151
InternalCF::variable
virtual Variable variable() const
Definition: int_cf.h:70
imm_divrem_p
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:440
operator<<
OSTREAM & operator<<(OSTREAM &os, const CanonicalForm &cf)
Definition: canonicalform.cc:1792
imm_sub_gf
InternalCF * imm_sub_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:302
InternalCF::dividecoeff
virtual InternalCF * dividecoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
CanonicalForm::den
CanonicalForm den() const
den() returns the denominator of CO if CO is a rational number, 1 (from the current domain!...
Definition: canonicalform.cc:595
InternalCF::comparecoeff
virtual int comparecoeff(InternalCF *) PVIRT_INT("comparecoeff")
CanonicalForm::operator*=
CanonicalForm & operator*=(const CanonicalForm &)
Definition: canonicalform.cc:689
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
InternalCF::den
virtual InternalCF * den()
Definition: int_cf.cc:91
divremt
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition: canonicalform.cc:1001
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
CanonicalForm::inZ
bool inZ() const
predicates
Definition: canonicalform.cc:66
get_Terms
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
readCF
CanonicalForm readCF(ISTREAM &)
InternalCF::deleteObject
int deleteObject()
Definition: int_cf.h:61
LEVELBASE
#define LEVELBASE
Definition: cf_defs.h:17
imm_iszero_gf
int imm_iszero_gf(const InternalCF *const ptr)
Definition: imm.h:157
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
imm_mul_p
InternalCF * imm_mul_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:346
cf_factory.h
InternalCF::dividesame
virtual InternalCF * dividesame(InternalCF *) PVIRT_INTCF("dividesame")
imm_cmp_p
int imm_cmp_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:245
imm_divrat
InternalCF * imm_divrat(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:368
InternalCF::tryDivsame
virtual InternalCF * tryDivsame(InternalCF *, const CanonicalForm &, bool &)
Definition: int_cf.cc:207
CanonicalForm::genZero
CanonicalForm genZero() const
genOne(), genZero()
Definition: canonicalform.cc:1808
imm2int
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Variable
factory's class for variables
Definition: factory.h:117
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition: canonicalform.cc:381
imm_iszero
int imm_iszero(const InternalCF *const ptr)
Definition: imm.h:145
InternalCF::inQuotDomain
virtual bool inQuotDomain() const
Definition: int_cf.h:78
CanonicalForm::inExtension
bool inExtension() const
Definition: canonicalform.cc:110
InternalCF::modulocoeff
virtual InternalCF * modulocoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
InternalCF::inExtension
virtual bool inExtension() const
Definition: int_cf.h:75
is_imm
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:62
InternalCF::divcoeff
virtual InternalCF * divcoeff(InternalCF *, bool) PVIRT_INTCF("divcoeff")
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
int2imm_p
InternalCF * int2imm_p(long i)
Definition: imm.h:101
imm_add_gf
InternalCF * imm_add_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:283
operator>
bool operator>(const CanonicalForm &lhs, const CanonicalForm &rhs)
operator >() - compare canonical forms.
Definition: canonicalform.cc:1496
imm_div
InternalCF * imm_div(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:356
CanonicalForm::mod
CanonicalForm & mod(const CanonicalForm &)
Definition: canonicalform.cc:925
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition: canonicalform.cc:304
ff_norm
int ff_norm(const int a)
Definition: ffops.h:39
InternalCF::inPolyDomain
virtual bool inPolyDomain() const
Definition: int_cf.h:77
InternalCF::ilog2
virtual int ilog2()
int InternalCF::ilog2 ()
Definition: int_cf.cc:110
CanonicalForm::taildegree
int taildegree() const
taildegree() returns -1 for the zero polynomial, 0 if CO is in a base domain, otherwise the least deg...
Definition: canonicalform.cc:519
ISTREAM
#define ISTREAM
Definition: canonicalform.h:17
InternalCF::num
virtual InternalCF * num()
InternalCF * InternalCF::num (), den ()
Definition: int_cf.cc:85
InternalCF::mulcoeff
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
bgcd
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
Definition: canonicalform.cc:1589
cf_assert.h
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
CanonicalForm::operator()
CanonicalForm operator()(const CanonicalForm &f) const
operator ()() - evaluation operator.
Definition: canonicalform.cc:1104
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
List< CanonicalForm >
swap
#define swap(_i, _j)
gf_int2gf
int gf_int2gf(int i)
Definition: gfops.h:65
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
OSTREAM
#define OSTREAM
Definition: canonicalform.h:16
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
int2imm_gf
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
getReduce
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
CFSwitches::On
void On(int s)
switch 's' on
Definition: cf_switches.h:51
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
imm_div_gf
InternalCF * imm_div_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:389
InternalCF::deepCopyObject
virtual InternalCF * deepCopyObject() const PVIRT_INTCF("deepCopyObject")
blcm
CanonicalForm blcm(const CanonicalForm &f, const CanonicalForm &g)
Definition: canonicalform.cc:1757
CanonicalForm::operator+=
CanonicalForm & operator+=(const CanonicalForm &)
assignment operators
Definition: canonicalform.cc:605
InternalCF::modsame
virtual InternalCF * modsame(InternalCF *) PVIRT_INTCF("modsame")
imm_sub
InternalCF * imm_sub(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:288
bextgcd
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: canonicalform.cc:1663
CanonicalForm::inFF
bool inFF() const
Definition: canonicalform.cc:89
IntegerDomain
#define IntegerDomain
Definition: cf_defs.h:26
imm_mod_p
InternalCF * imm_mod_p(const InternalCF *const, const InternalCF *const)
Definition: imm.h:418
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
facMul.h
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm::inPolyDomain
bool inPolyDomain() const
Definition: canonicalform.cc:128
imm_intval
long imm_intval(const InternalCF *const op)
Definition: imm.h:164
CFSwitches::isOn
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
InternalCF::sign
virtual int sign() const PVIRT_INT("sign")
ListIterator
Definition: ftmpl_list.h:17
CanonicalForm::getval
InternalCF * getval() const
Definition: canonicalform.cc:31
InternalCF::lc
virtual CanonicalForm lc()
CanonicalForm InternalCF::lc (), Lc (), LC ()
Definition: int_cf.cc:34