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