My Project  debian-1:4.1.1-p2+ds-4build4
int_poly.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 #ifndef NOSTREAMIO
8 #include <string.h>
9 #if defined(WINNT) && ! defined(__GNUC__)
10 #include <strstrea.h>
11 #else
12 #if __GNUC__ < 3
13 #include <strstream.h>
14 #else
15 #include <strstream>
16 using namespace std;
17 #endif
18 #endif
19 #endif /* NOSTREAMIO */
20 
21 #include "cf_assert.h"
22 
23 #include "cf_defs.h"
24 #include "cf_factory.h"
25 #include "cfUnivarGcd.h"
26 #include "int_cf.h"
27 #include "int_int.h"
28 #include "int_poly.h"
29 #include "canonicalform.h"
30 #include "variable.h"
31 #include "imm.h"
32 
33 #ifdef HAVE_OMALLOC
34 const omBin term::term_bin = omGetSpecBin(sizeof(term));
36 #endif
37 
39 {
40  firstTerm = first;
41  lastTerm = last;
42  var = v;
43 }
44 
46 {
47  ASSERT( 0, "ups, why do you initialize an empty poly" );
48 }
49 
50 InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
51 {
52  var = v;
53  firstTerm = new term( 0, c, e );
54  lastTerm = firstTerm;
55 }
56 
58 {
59  ASSERT( 0, "ups there is something wrong in your code" );
60 }
61 
63 {
65 }
66 
69 {
70  termList first, last;
71  first = deepCopyTermList( firstTerm, last );
72  return new InternalPoly( first, last, var );
73 }
74 
75 bool
77 {
78  termList cursor = firstTerm;
79  while ( cursor )
80  {
81  if ( ! cursor->coeff.inCoeffDomain() )
82  return false;
83  cursor = cursor->next;
84  }
85  return true;
86 }
87 
88 /** int InternalPoly::degree ()
89  * @sa CanonicalForm::sign ()
90 **/
91 int
93 {
94  return firstTerm->exp;
95 }
96 
97 
98 /** int InternalPoly::sign () const
99  * @sa CanonicalForm::sign()
100 **/
101 int
103 {
104  return firstTerm->coeff.sign();
105 }
106 
107 
108 /**
109  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::Lc (), InternalPoly::LC ()
110 **/
113 {
114  return firstTerm->coeff.lc();
115 }
116 
117 /**
118  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::LC ()
119 **/
122 {
123  return firstTerm->coeff.Lc();
124 }
125 
126 /**
127  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::Lc ()
128 **/
131 {
132  return firstTerm->coeff;
133 }
134 
135 /** CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
136  * @sa CanonicalForm::tailcoeff(), taildegree()
137 **/
140 {
141  return lastTerm->coeff;
142 }
143 
144 int
146 {
147  return lastTerm->exp;
148 }
149 
150 /** CanonicalForm InternalPoly::coeff ( int i )
151  * @sa CanonicalForm::operator []()
152 **/
155 {
156  termList theCursor = firstTerm;
157  while ( theCursor )
158  {
159  if ( theCursor->exp == i )
160  return theCursor->coeff;
161  else if ( theCursor->exp < i )
162  return CanonicalForm( 0 );
163  else
164  theCursor = theCursor->next;
165  }
166  return CanonicalForm( 0 );
167 }
168 
169 #ifndef NOSTREAMIO
170 void
171 InternalPoly::print(OSTREAM &aStream, char * aString )
172 {
173  if ( ! firstTerm )
174  aStream << 0 << aString;
175  else
176  {
177  char * theString;
178  termList theCursor = firstTerm;
179  while ( theCursor )
180  {
181  ostrstream theStream;
182  if ( theCursor->exp == 0 )
183  theCursor->coeff.print( aStream, aString );
184  else if ( theCursor->coeff.isOne() )
185  {
186  aStream << var;
187  if ( theCursor->exp != 1 )
188  aStream << '^' << theCursor->exp << aString;
189  else
190  aStream << aString;
191  }
192  else if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() )
193  {
194  aStream << '-' << var;
195  if ( theCursor->exp != 1 )
196  aStream << '^' << theCursor->exp << aString;
197  else
198  aStream << aString;
199  }
200  else
201  {
202  theStream << '*' << var;
203  if ( theCursor->exp != 1 )
204  theStream << '^' << theCursor->exp << aString << ends;
205  else
206  theStream << aString << ends; // results from error in GNU strstream
207  theString = theStream.str();
208  theCursor->coeff.print( aStream, theString );
209  theStream.freeze(0);//delete [] theString;
210  }
211  theCursor = theCursor->next;
212  if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
213  aStream << '+';
214  }
215  }
216 }
217 #endif /* NOSTREAMIO */
218 
219 /** InternalCF * InternalPoly::neg ()
220  * @sa CanonicalForm::operator -()
221 **/
222 InternalCF *
224 {
225  if ( getRefCount() <= 1 )
226  {
228  return this;
229  }
230  else
231  {
232  decRefCount();
233  termList last, first = copyTermList( firstTerm, last, true );
234  return new InternalPoly( first, last, var );
235  }
236 }
237 
238 InternalCF*
240 {
241  if ( inExtension() && getReduce( var ) )
242  {
243  setReduce( var, false );
244  CanonicalForm a( this->copyObject() );
245  CanonicalForm b = getMipo( var );
246  CanonicalForm u, v;
247  CanonicalForm g = extgcd( a, b, u, v );
248  setReduce( var, true );
249  return u.getval();
250  }
251  else
252  return CFFactory::basic( 0L );
253 }
254 
255 InternalCF*
257 {
258  if ( inExtension() && !getReduce ( var ) )
259  {
260  CanonicalForm b, inverse;
261  CanonicalForm F ( this ->copyObject() );
262  Variable a = M.mvar();
263  Variable x = Variable(1);
264  F= mod (F, M); //reduce mod M
265  CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b );
266  if(!g.isOne())
267  fail = true;
268  else
269  inverse = replacevar( inverse, x, a ); // change back to alg var
270  CanonicalForm test= mod (inverse*F, M);
271  return inverse.getval();
272  }
273  else
274  return CFFactory::basic( 0L );
275 }
276 
277 InternalCF*
279 {
280  InternalPoly * aPoly = (InternalPoly*)aCoeff;
281  if ( getRefCount() <= 1 )
282  {
283  firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
284  if ( firstTerm && firstTerm->exp != 0 )
285  return this;
286  else if ( firstTerm )
287  {
289  delete this;
290  return res;
291  }
292  else
293  {
294  delete this;
295  return CFFactory::basic( 0L );
296  }
297  }
298  else
299  {
300  decRefCount();
301  termList last, first = copyTermList( firstTerm, last );
302  first = addTermList( first, aPoly->firstTerm, last, false );
303  if ( first && first->exp != 0 )
304  return new InternalPoly( first, last, var );
305  else if ( first )
306  {
307  InternalCF * res = first->coeff.getval();
308  delete first;
309  return res;
310  }
311  else
312  return CFFactory::basic( 0L );
313 
314  }
315 }
316 
317 InternalCF*
319 {
320  InternalPoly * aPoly = (InternalPoly*)aCoeff;
321  if ( getRefCount() <= 1 )
322  {
323  firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
324  if ( firstTerm && firstTerm->exp != 0 )
325  return this;
326  else if ( firstTerm )
327  {
329  delete this;
330  return res;
331  }
332  else
333  {
334  delete this;
335  return CFFactory::basic( 0L );
336  }
337  }
338  else
339  {
340  decRefCount();
341  termList last, first = copyTermList( firstTerm, last );
342  first = addTermList( first, aPoly->firstTerm, last, true );
343  if ( first && first->exp != 0 )
344  return new InternalPoly( first, last, var );
345  else if ( first )
346  {
347  InternalCF * res = first->coeff.getval();
348  delete first;
349  return res;
350  }
351  else
352  return CFFactory::basic( 0L );
353 
354  }
355 }
356 
357 InternalCF*
359 {
360  if (is_imm(aCoeff)) return mulcoeff(aCoeff);
361  InternalPoly *aPoly = (InternalPoly*)aCoeff;
362  termList resultFirst = 0, resultLast = 0;
363  termList theCursor = firstTerm;
364 
365  while ( theCursor )
366  {
367  resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
368  theCursor->coeff, theCursor->exp, resultLast, false );
369  theCursor = theCursor->next;
370  }
371  if ( inExtension() && getReduce( var ) )
372  {
373  resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
374  if ( resultFirst == 0 )
375  {
376  if ( getRefCount() <= 1 )
377  {
378  delete this;
379  return CFFactory::basic(0L);
380  }
381  else
382  {
383  decRefCount();
384  return CFFactory::basic(0L);
385  }
386  }
387  else if ( resultFirst->exp == 0 )
388  {
389  if ( getRefCount() <= 1 )
390  {
391  InternalCF * res = resultFirst->coeff.getval();
392  delete resultFirst;
393  delete this;
394  return res;
395  }
396  else
397  {
398  decRefCount();
399  InternalCF * res = resultFirst->coeff.getval();
400  delete resultFirst;
401  return res;
402  }
403  }
404  }
405  if ( getRefCount() <= 1 )
406  {
408  firstTerm = resultFirst;
409  lastTerm = resultLast;
410  return this;
411  }
412  else
413  {
414  decRefCount();
415  return new InternalPoly( resultFirst, resultLast, var );
416  }
417 }
418 
419 InternalCF*
421 {
422  if (is_imm(aCoeff))
423  return mulcoeff(aCoeff);
424  InternalPoly *aPoly = (InternalPoly*)aCoeff;
425  termList resultFirst = 0, resultLast = 0;
426  termList theCursor = firstTerm;
427 
428  while ( theCursor )
429  {
430  resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
431  theCursor->coeff, theCursor->exp, resultLast, false );
432  theCursor = theCursor->next;
433  }
434  if ( inExtension() && !getReduce( var ) )
435  {
436  resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())->firstTerm, resultLast);
437  if ( resultFirst == 0 )
438  {
439  if ( getRefCount() <= 1 )
440  {
441  delete this;
442  return CFFactory::basic(0L);
443  }
444  else
445  {
446  decRefCount();
447  return CFFactory::basic(0L);
448  }
449  }
450  else if ( resultFirst->exp == 0 )
451  {
452  if ( getRefCount() <= 1 )
453  {
454  InternalCF * res = resultFirst->coeff.getval();
455  delete resultFirst;
456  delete this;
457  return res;
458  }
459  else
460  {
461  decRefCount();
462  InternalCF * res = resultFirst->coeff.getval();
463  delete resultFirst;
464  return res;
465  }
466  }
467  }
468  if ( getRefCount() <= 1 )
469  {
471  firstTerm = resultFirst;
472  lastTerm = resultLast;
473  return this;
474  }
475  else
476  {
477  decRefCount();
478  return new InternalPoly( resultFirst, resultLast, var );
479  }
480 }
481 
482 InternalCF*
484 {
485  return divsame( aCoeff );
486 }
487 
488 
489 InternalCF*
491 {
492  if ( inExtension() && getReduce( var ) )
493  {
494  InternalCF * dummy = aCoeff->invert();
495  if (is_imm(dummy)) dummy=this->mulsame(dummy);
496  else dummy = dummy->mulsame( this );
497  if ( getRefCount() <= 1 )
498  {
499  delete this;
500  return dummy;
501  }
502  else
503  {
504  decRefCount();
505  return dummy;
506  }
507  }
508  InternalPoly *aPoly = (InternalPoly*)aCoeff;
509  termList dummy, first, last, resultfirst = 0, resultlast = 0;
510  CanonicalForm coeff, newcoeff;
511  int exp, newexp;
512  bool singleObject;
513 
514  if ( getRefCount() <= 1 )
515  {
516  first = firstTerm; last = lastTerm; singleObject = true;
517  }
518  else
519  {
520  first = copyTermList( firstTerm, last ); singleObject = false;
521  decRefCount();
522  }
523  coeff = aPoly->firstTerm->coeff;
524  exp = aPoly->firstTerm->exp;
525  while (first && ( first->exp >= exp ) )
526  {
527  newcoeff = first->coeff / coeff;
528  newexp = first->exp - exp;
529  dummy = first;
530  first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
531  delete dummy;
532  appendTermList( resultfirst, resultlast, newcoeff, newexp );
533  }
534  freeTermList( first );
535  if ( singleObject )
536  {
537  if ( resultfirst && resultfirst->exp != 0 )
538  {
539  firstTerm = resultfirst;
540  lastTerm = resultlast;
541  return this;
542  }
543  else if ( resultfirst )
544  {
545  InternalCF * res = resultfirst->coeff.getval();
546  delete resultfirst;
547  firstTerm = 0;
548  delete this;
549  return res;
550  }
551  else
552  {
553  // this should not happen (evtl use assertion)
554  ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
555  firstTerm = 0;
556  delete this;
557  return CFFactory::basic( 0L );
558  }
559  }
560  else
561  {
562  if ( resultfirst && resultfirst->exp != 0 )
563  return new InternalPoly( resultfirst, resultlast, var );
564  else if ( resultfirst )
565  {
566  InternalCF * res = resultfirst->coeff.getval();
567  delete resultfirst;
568  return res;
569  }
570  else
571  return CFFactory::basic( 0L );
572  }
573 }
574 
575 InternalCF*
576 InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail )
577 {
578  if ( inExtension() && !getReduce( var ) )
579  {
580  InternalCF * dummy = aCoeff->tryInvert(M, fail);
581  if (fail)
582  return CFFactory::basic( 0L );
583  if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M);
584  else dummy = dummy->tryMulsame( this, M);
585  if (fail)
586  {
587  if (getRefCount() <= 1)
588  delete this;
589  else
590  decRefCount();
591  return dummy;
592  }
593  if ( getRefCount() <= 1 )
594  {
595  delete this;
596  return dummy;
597  }
598  else
599  {
600  decRefCount();
601  return dummy;
602  }
603  }
604  InternalPoly *aPoly = (InternalPoly*)aCoeff;
605  termList dummy, first, last, resultfirst = 0, resultlast = 0;
606  CanonicalForm coeff, newcoeff;
607  int exp, newexp;
608  bool singleObject;
609 
610  if ( getRefCount() <= 1 )
611  {
612  first = firstTerm; last = lastTerm; singleObject = true;
613  }
614  else
615  {
616  first = copyTermList( firstTerm, last ); singleObject = false;
617  decRefCount();
618  }
619  coeff = aPoly->firstTerm->coeff;
620  exp = aPoly->firstTerm->exp;
621  while (first && ( first->exp >= exp ) )
622  {
623  newcoeff= first->coeff.tryDiv (coeff, M, fail);
624  if (fail)
625  {
626  freeTermList (first);
627  return CFFactory::basic (0L);
628  }
629  newcoeff= reduce (newcoeff, M);
630  newexp = first->exp - exp;
631  dummy = first;
632  first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
633  delete dummy;
634  if (!newcoeff.isZero())
635  appendTermList( resultfirst, resultlast, newcoeff, newexp );
636  }
637  freeTermList( first );
638  if ( singleObject )
639  {
640  if ( resultfirst && resultfirst->exp != 0 )
641  {
642  firstTerm = resultfirst;
643  lastTerm = resultlast;
644  return this;
645  }
646  else if ( resultfirst )
647  {
648  InternalCF * res = resultfirst->coeff.getval();
649  delete resultfirst;
650  firstTerm = 0;
651  delete this;
652  return res;
653  }
654  else
655  {
656  // this should not happen (evtl use assertion)
657  ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
658  firstTerm = 0;
659  delete this;
660  return CFFactory::basic( 0L );
661  }
662  }
663  else
664  {
665  if ( resultfirst && resultfirst->exp != 0 )
666  return new InternalPoly( resultfirst, resultlast, var );
667  else if ( resultfirst )
668  {
669  InternalCF * res = resultfirst->coeff.getval();
670  delete resultfirst;
671  return res;
672  }
673  else
674  return CFFactory::basic( 0L );
675  }
676 }
677 
678 InternalCF*
680 {
681  return modsame( aCoeff );
682 }
683 
684 InternalCF*
686 {
687  if ( inExtension() && getReduce( var ) )
688  {
689  if ( deleteObject() ) delete this;
690  return CFFactory::basic( 0L );
691  }
692  InternalPoly *aPoly = (InternalPoly*)aCoeff;
693  termList dummy, first, last;
694  CanonicalForm coeff, newcoeff;
695  int exp, newexp;
696  bool singleObject;
697 
698  if ( getRefCount() <= 1 )
699  {
700  first = firstTerm; last = lastTerm; singleObject = true;
701  }
702  else
703  {
704  first = copyTermList( firstTerm, last ); singleObject = false;
705  decRefCount();
706  }
707  coeff = aPoly->firstTerm->coeff;
708  exp = aPoly->firstTerm->exp;
709  while (first && ( first->exp >= exp ) )
710  {
711  newcoeff = first->coeff / coeff;
712  newexp = first->exp - exp;
713  dummy = first;
714  first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
715  delete dummy;
716  }
717  if ( singleObject )
718  {
719  if ( first && first->exp != 0 )
720  {
721  firstTerm = first;
722  lastTerm = last;
723  return this;
724  }
725  else if ( first )
726  {
727  InternalCF * res = first->coeff.getval();
728  delete first;
729  firstTerm = 0;
730  delete this;
731  return res;
732  }
733  else
734  {
735  firstTerm = 0;
736  delete this;
737  return CFFactory::basic( 0L );
738  }
739  }
740  else
741  {
742  if ( first && first->exp != 0 )
743  return new InternalPoly( first, last, var );
744  else if ( first )
745  {
746  InternalCF * res = first->coeff.getval();
747  delete first;
748  return res;
749  }
750  else
751  return CFFactory::basic( 0L );
752  }
753 }
754 
755 
756 void
758 {
759  if ( inExtension() && getReduce( var ) )
760  {
761  InternalCF * dummy = acoeff->invert();
762  quot = dummy->mulsame( this );
763  rem = CFFactory::basic( 0L );
764  }
765  else
766  {
767  InternalPoly *aPoly = (InternalPoly*)acoeff;
768  termList dummy, first, last, resultfirst = 0, resultlast = 0;
769  CanonicalForm coeff, newcoeff;
770  int exp, newexp;
771 
772  first = copyTermList( firstTerm, last );
773 
774  coeff = aPoly->firstTerm->coeff;
775  exp = aPoly->firstTerm->exp;
776  while (first && ( first->exp >= exp ) )
777  {
778  newcoeff = first->coeff / coeff;
779  newexp = first->exp - exp;
780  dummy = first;
781  first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
782  delete dummy;
783  appendTermList( resultfirst, resultlast, newcoeff, newexp );
784  }
785  if ( resultfirst )
786  if ( resultfirst->exp == 0 )
787  {
788  quot = resultfirst->coeff.getval();
789  delete resultfirst;
790  }
791  else
792  quot = new InternalPoly( resultfirst, resultlast, var );
793  else
794  quot = CFFactory::basic( 0L );
795  if ( first )
796  if ( first->exp == 0 )
797  {
798  rem = first->coeff.getval();
799  delete first;
800  }
801  else
802  rem = new InternalPoly( first, last, var );
803  else
804  rem = CFFactory::basic( 0L );
805  }
806 }
807 
808 bool
810 {
811  if ( inExtension() && getReduce( var ) )
812  {
813  divremsame( acoeff, quot, rem );
814  return true;
815  }
816  InternalPoly *aPoly = (InternalPoly*)acoeff;
817  termList dummy, first, last, resultfirst = 0, resultlast = 0;
818  CanonicalForm coeff, newcoeff, dummycoeff;
819  int exp, newexp;
820  bool divideok = true;
821 
822 // if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
823 // return false;
824 
825  first = copyTermList( firstTerm, last );
826 
827  coeff = aPoly->firstTerm->coeff;
828  exp = aPoly->firstTerm->exp;
829  while (first && ( first->exp >= exp ) && divideok )
830  {
831  divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff );
832  if ( divideok && dummycoeff.isZero() )
833  {
834  newexp = first->exp - exp;
835  dummy = first;
836  first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
837  delete dummy;
838  appendTermList( resultfirst, resultlast, newcoeff, newexp );
839  }
840  else
841  divideok = false;
842  }
843  if ( divideok )
844  {
845  if ( resultfirst )
846  if ( resultfirst->exp == 0 )
847  {
848  quot = resultfirst->coeff.getval();
849  delete resultfirst;
850  }
851  else
852  quot = new InternalPoly( resultfirst, resultlast, var );
853  else
854  quot = CFFactory::basic( 0L );
855  if ( first )
856  if ( first->exp == 0 )
857  {
858  rem = first->coeff.getval();
859  delete first;
860  }
861  else
862  rem = new InternalPoly( first, last, var );
863  else
864  rem = CFFactory::basic( 0L );
865  }
866  else
867  {
868  freeTermList( resultfirst );
869  freeTermList( first );
870  }
871  return divideok;
872 }
873 
874 bool
876 {
877  if (inExtension() && !getReduce (var))
878  {
879  InternalCF * dummy = acoeff->tryInvert(M, fail);
880  if (fail)
881  return false;
882  quot = dummy->tryMulsame( this, M);
883  rem = CFFactory::basic( 0L );
884  if (fail)
885  return false;
886  return true;
887  }
888  InternalPoly *aPoly = (InternalPoly*)acoeff;
889  termList dummy, first, last, resultfirst = 0, resultlast = 0;
890  CanonicalForm coeff, newcoeff, dummycoeff;
891  int exp, newexp;
892  bool divideok = true;
893 
894  first = copyTermList( firstTerm, last );
895 
896  coeff = aPoly->firstTerm->coeff;
897  exp = aPoly->firstTerm->exp;
898  while (first && ( first->exp >= exp ) && divideok )
899  {
900  divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail );
901  if (fail)
902  {
903  freeTermList (first);
904  return false;
905  }
906  if ( divideok && dummycoeff.isZero() )
907  {
908  newexp = first->exp - exp;
909  dummy = first;
910  first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
911  delete dummy;
912  if (!newcoeff.isZero())
913  appendTermList( resultfirst, resultlast, newcoeff, newexp );
914  }
915  else
916  divideok = false;
917  }
918  if ( divideok )
919  {
920  if ( resultfirst )
921  if ( resultfirst->exp == 0 )
922  {
923  quot = resultfirst->coeff.getval();
924  delete resultfirst;
925  }
926  else
927  quot = new InternalPoly( resultfirst, resultlast, var );
928  else
929  quot = CFFactory::basic( 0L );
930  if ( first )
931  if ( first->exp == 0 )
932  {
933  rem = first->coeff.getval();
934  delete first;
935  }
936  else
937  {
938  if (first->coeff.isZero())
939  {
940  rem= CFFactory::basic (0L);
941  delete first;
942  }
943  else
944  rem = new InternalPoly( first, last, var );
945  }
946  else
947  rem = CFFactory::basic( 0L );
948  }
949  else
950  {
951  freeTermList( resultfirst );
952  freeTermList( first );
953  }
954  return divideok;
955 }
956 
957 /**
958  * comparesame(), comparecoeff() - compare with an
959  * InternalPoly.
960  *
961  * comparesame() compares the coefficient vectors of f=CO and
962  * g=acoeff w.r.t to a lexicographic order in the following way:
963  * f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
964  * i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
965  * ii) g[i] occurs in g (i.e. is not equal to zero) and
966  * f[i] does not occur in f or f[i] < g[i] if f[i] occurs
967  * where f[i] denotes the coefficient to the power x^i of f.
968  *
969  * As usual, comparesame() returns 1 if CO is larger than c, 0 if
970  * CO equals c, and -1 if CO is less than c. However, this
971  * function is optimized to test on equality since this is its
972  * most important and frequent usage.
973  *
974  * See the respective `CanonicalForm'-methods for an explanation
975  * why we define such a strange (but total) ordering on
976  * polynomials.
977  *
978  * @sa CanonicalForm::operator <(), CanonicalForm::operator ==()
979  *
980 **/
981 int
983 {
984  ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
985  InternalPoly* apoly = (InternalPoly*)acoeff;
986  // check on triviality
987  if ( this == apoly )
988  return 0;
989  else
990  {
991  termList cursor1 = firstTerm;
992  termList cursor2 = apoly->firstTerm;
993  for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
994  // we test on inequality of coefficients at this
995  // point instead of testing on "less than" at the
996  // last `else' in the enclosed `if' statement since a
997  // test on inequaltiy in general is cheaper
998  if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) )
999  {
1000  if ( cursor1->exp > cursor2->exp )
1001  return 1;
1002  else if ( cursor1->exp < cursor2->exp )
1003  return -1;
1004  else if ( cursor1->coeff > cursor2->coeff )
1005  return 1;
1006  else
1007  return -1;
1008  }
1009  // check trailing terms
1010  if ( cursor1 == cursor2 )
1011  return 0;
1012  else if ( cursor1 != 0 )
1013  return 1;
1014  else
1015  return -1;
1016  }
1017 }
1018 
1019 /**
1020  * comparecoeff() always returns 1 since CO is defined to be
1021  * larger than anything which is a coefficient w.r.t. CO.
1022 **/
1023 int
1025 {
1026  return 1;
1027 }
1028 
1029 InternalCF*
1031 {
1032  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1033  if ( c.isZero() )
1034  return this;
1035  else
1036  {
1037  if ( getRefCount() <= 1 )
1038  {
1039  if ( lastTerm->exp == 0 )
1040  {
1041  lastTerm->coeff += c;
1042  if ( lastTerm->coeff.isZero() )
1043  {
1044  termList cursor = firstTerm;
1045  while ( cursor->next != lastTerm )
1046  cursor = cursor->next;
1047  delete lastTerm;
1048  cursor->next = 0;
1049  lastTerm = cursor;
1050  }
1051  }
1052  else
1053  {
1054  lastTerm->next = new term( 0, c, 0 );
1055  lastTerm = lastTerm->next;
1056  }
1057  return this;
1058  }
1059  else
1060  {
1061  decRefCount();
1062  termList last, first = copyTermList( firstTerm, last, false );
1063  if ( last->exp == 0 )
1064  {
1065  last->coeff += c;
1066  if ( last->coeff.isZero() )
1067  {
1068  termList cursor = first;
1069  while ( cursor->next != last )
1070  cursor = cursor->next;
1071  delete last;
1072  cursor->next = 0;
1073  last = cursor;
1074  }
1075  }
1076  else
1077  {
1078  last->next = new term( 0, c, 0L );
1079  last = last->next;
1080  }
1081  return new InternalPoly( first, last, var );
1082  }
1083  }
1084 }
1085 
1086 InternalCF*
1088 {
1089  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1090  if ( c.isZero() )
1091  if ( getRefCount() > 1 )
1092  {
1093  decRefCount();
1094  termList last, first = copyTermList( firstTerm, last, negate );
1095  return new InternalPoly( first, last, var );
1096  }
1097  else
1098  {
1099  if ( negate )
1101  return this;
1102  }
1103  else
1104  {
1105  if ( getRefCount() <= 1 )
1106  {
1107  if ( lastTerm->exp == 0 )
1108  {
1109  if ( negate )
1110  {
1112  lastTerm->coeff += c;
1113  }
1114  else
1115  lastTerm->coeff -= c;
1116  if ( lastTerm->coeff.isZero() )
1117  {
1118  termList cursor = firstTerm;
1119  while ( cursor->next != lastTerm )
1120  cursor = cursor->next;
1121  delete lastTerm;
1122  cursor->next = 0;
1123  lastTerm = cursor;
1124  }
1125  }
1126  else
1127  {
1128  if ( negate )
1129  {
1131  lastTerm->next = new term( 0, c, 0 );
1132  }
1133  else
1134  lastTerm->next = new term( 0, -c, 0 );
1135  lastTerm = lastTerm->next;
1136  }
1137  return this;
1138  }
1139  else
1140  {
1141  decRefCount();
1142  termList last, first = copyTermList( firstTerm, last, negate );
1143  if ( last->exp == 0 )
1144  {
1145  if ( negate )
1146  last->coeff += c;
1147  else
1148  last->coeff -= c;
1149  if ( last->coeff.isZero() )
1150  {
1151  termList cursor = first;
1152  while ( cursor->next != last )
1153  cursor = cursor->next;
1154  delete last;
1155  cursor->next = 0;
1156  last = cursor;
1157  }
1158  }
1159  else
1160  {
1161  if ( negate )
1162  last->next = new term( 0, c, 0 );
1163  else
1164  last->next = new term( 0, -c, 0 );
1165  last = last->next;
1166  }
1167  return new InternalPoly( first, last, var );
1168  }
1169  }
1170 }
1171 
1172 InternalCF*
1174 {
1175  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1176  if ( c.isZero() )
1177  {
1178  if ( getRefCount() <= 1 )
1179  {
1180  delete this;
1181  return CFFactory::basic( 0L );
1182  }
1183  else
1184  {
1185  decRefCount();
1186  return CFFactory::basic( 0L );
1187  }
1188  }
1189  else if ( c.isOne() )
1190  return this;
1191  else
1192  {
1193  if ( getRefCount() <= 1 )
1194  {
1195  mulTermList( firstTerm, c, 0L );
1196  return this;
1197  }
1198  else
1199  {
1200  decRefCount();
1201  termList last, first = copyTermList( firstTerm, last );
1202  mulTermList( first, c, 0 );
1203  return new InternalPoly( first, last, var );
1204  }
1205  }
1206 }
1207 
1208 InternalCF*
1210 {
1211  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1212  if ( inExtension() && getReduce( var ) && invert )
1213  {
1214  InternalCF * dummy;
1215  dummy = this->invert();
1216  if (is_imm(dummy))
1217  {
1218  if (is_imm(cc))
1219  {
1220  InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
1221  dummy=d;
1222  }
1223  else
1224  dummy=cc->mulcoeff(dummy);
1225  }
1226  else dummy = dummy->mulcoeff( cc );
1227  if ( getRefCount() <= 1 )
1228  {
1229  delete this;
1230  return dummy;
1231  }
1232  else
1233  {
1234  decRefCount();
1235  return dummy;
1236  }
1237  }
1238  if ( invert )
1239  {
1240  if ( getRefCount() <= 1 )
1241  {
1242  delete this;
1243  return CFFactory::basic( 0L );
1244  }
1245  else
1246  {
1247  decRefCount();
1248  return CFFactory::basic( 0L );
1249  }
1250  }
1251  if ( c.isOne() )
1252  return this;
1253  else
1254  {
1255  if ( getRefCount() <= 1 )
1256  {
1258  if ( firstTerm && firstTerm->exp != 0 )
1259  return this;
1260  else if ( firstTerm )
1261  {
1263  delete this;
1264  return res;
1265  }
1266  else
1267  {
1268  delete this;
1269  return CFFactory::basic( 0L );
1270  }
1271  }
1272  else
1273  {
1274  decRefCount();
1275  termList last, first = copyTermList( firstTerm, last );
1276  first = divideTermList( first, c, last );
1277  if ( first && first->exp != 0 )
1278  return new InternalPoly( first, last, var );
1279  else if ( first )
1280  {
1281  InternalCF * res = first->coeff.getval();
1282  delete first;
1283  return res;
1284  }
1285  else
1286  {
1287  delete first;
1288  return CFFactory::basic( 0L );
1289  }
1290  }
1291  }
1292 }
1293 
1294 InternalCF*
1295 InternalPoly::tryDividecoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
1296 {
1297  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1298  if ( inExtension() && !getReduce( var ) && invert )
1299  {
1300  InternalCF * dummy;
1301  dummy = this->tryInvert(M, fail);
1302  if (fail)
1303  {
1304  if (getRefCount() <= 1)
1305  delete this;
1306  else
1307  decRefCount();
1308  return dummy; //is equal to CFFactory::basic ( 0L ) in this case
1309  }
1310  if (is_imm(dummy))
1311  {
1312  if (is_imm(cc))
1313  {
1314  InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
1315  dummy=d;
1316  }
1317  else
1318  dummy=cc->mulcoeff(dummy);
1319  }
1320  else dummy = dummy->mulcoeff( cc );
1321  if ( getRefCount() <= 1 )
1322  {
1323  delete this;
1324  return dummy;
1325  }
1326  else
1327  {
1328  decRefCount();
1329  return dummy;
1330  }
1331  }
1332  if ( invert )
1333  {
1334  if ( getRefCount() <= 1 )
1335  {
1336  delete this;
1337  return CFFactory::basic( 0L );
1338  }
1339  else
1340  {
1341  decRefCount();
1342  return CFFactory::basic( 0L );
1343  }
1344  }
1345  if ( c.isOne() )
1346  return this;
1347  //one should never get here
1348  else
1349  {
1350  if ( getRefCount() <= 1 )
1351  {
1353  if ( firstTerm && firstTerm->exp != 0 )
1354  return this;
1355  else if ( firstTerm )
1356  {
1358  delete this;
1359  return res;
1360  }
1361  else
1362  {
1363  delete this;
1364  return CFFactory::basic( 0L );
1365  }
1366  }
1367  else
1368  {
1369  decRefCount();
1370  termList last, first = copyTermList( firstTerm, last );
1371  first = divideTermList( first, c, last );
1372  if ( first && first->exp != 0 )
1373  return new InternalPoly( first, last, var );
1374  else if ( first )
1375  {
1376  InternalCF * res = first->coeff.getval();
1377  delete first;
1378  return res;
1379  }
1380  else
1381  {
1382  delete first;
1383  return CFFactory::basic( 0L );
1384  }
1385  }
1386  }
1387 }
1388 
1389 
1390 InternalCF*
1392 {
1393  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1394  if ( inExtension() && getReduce( var ) && invert )
1395  {
1396  InternalCF * dummy;
1397  dummy = this->invert();
1398  dummy = dummy->mulcoeff( cc );
1399  if ( getRefCount() <= 1 )
1400  {
1401  delete this;
1402  return dummy;
1403  }
1404  else
1405  {
1406  decRefCount();
1407  return dummy;
1408  }
1409  }
1410  if ( invert )
1411  {
1412  if ( getRefCount() <= 1 )
1413  {
1414  delete this;
1415  return CFFactory::basic( 0L );
1416  }
1417  else
1418  {
1419  decRefCount();
1420  return CFFactory::basic( 0L );
1421  }
1422  }
1423  if ( c.isOne() )
1424  return this;
1425  else
1426  {
1427  if ( getRefCount() <= 1 )
1428  {
1430  if ( firstTerm && firstTerm->exp != 0 )
1431  return this;
1432  else if ( firstTerm )
1433  {
1435  delete this;
1436  return res;
1437  }
1438  else
1439  {
1440  delete this;
1441  return CFFactory::basic( 0L );
1442  }
1443  }
1444  else
1445  {
1446  decRefCount();
1447  termList last, first = copyTermList( firstTerm, last );
1448  first = divTermList( first, c, last );
1449  if ( first && first->exp != 0 )
1450  return new InternalPoly( first, last, var );
1451  else if ( first )
1452  {
1453  InternalCF * res = first->coeff.getval();
1454  delete first;
1455  return res;
1456  }
1457  else
1458  {
1459  delete first;
1460  return CFFactory::basic( 0L );
1461  }
1462  }
1463  }
1464 }
1465 
1466 InternalCF*
1467 InternalPoly::tryDivcoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
1468 {
1469  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1470  if ( inExtension() && !getReduce( var ) && invert )
1471  {
1472  InternalCF * dummy;
1473  dummy = this->tryInvert(M, fail);
1474  if (fail)
1475  {
1476  if (getRefCount() <= 1)
1477  delete this;
1478  else
1479  decRefCount();
1480  return dummy;
1481  }
1482  dummy = dummy->mulcoeff( cc );
1483  if ( getRefCount() <= 1 )
1484  {
1485  delete this;
1486  return dummy;
1487  }
1488  else
1489  {
1490  decRefCount();
1491  return dummy;
1492  }
1493  }
1494  if ( invert )
1495  {
1496  if ( getRefCount() <= 1 )
1497  {
1498  delete this;
1499  return CFFactory::basic( 0L );
1500  }
1501  else
1502  {
1503  decRefCount();
1504  return CFFactory::basic( 0L );
1505  }
1506  }
1507  if ( c.isOne() )
1508  return this;
1509  else
1510  {
1511  if ( getRefCount() <= 1 )
1512  {
1513  firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
1514  if (fail)
1515  {
1516  delete this;
1517  return CFFactory::basic (0L);
1518  }
1519  if ( firstTerm && firstTerm->exp != 0 )
1520  return this;
1521  else if ( firstTerm )
1522  {
1524  delete this;
1525  return res;
1526  }
1527  else
1528  {
1529  delete this;
1530  return CFFactory::basic( 0L );
1531  }
1532  }
1533  else
1534  {
1535  decRefCount();
1536  termList last, first = copyTermList( firstTerm, last );
1537  first = tryDivTermList( first, c, last, M, fail );
1538  if (fail)
1539  {
1540  delete this;
1541  return CFFactory::basic (0L);
1542  }
1543  if (fail)
1544  {
1545  delete first;
1546  return CFFactory::basic (0L);
1547  }
1548  if ( first && first->exp != 0 )
1549  return new InternalPoly( first, last, var );
1550  else if ( first )
1551  {
1552  InternalCF * res = first->coeff.getval();
1553  delete first;
1554  return res;
1555  }
1556  else
1557  {
1558  delete first;
1559  return CFFactory::basic( 0L );
1560  }
1561  }
1562  }
1563 }
1564 
1565 InternalCF*
1567 {
1568  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1569  if ( invert )
1570  {
1571  if ( deleteObject() ) delete this;
1572  return c.getval();
1573  }
1574  ASSERT( ! c.isZero(), "divide by zero!" );
1575  if ( deleteObject() ) delete this;
1576  return CFFactory::basic( 0L );
1577 }
1578 
1579 InternalCF*
1581 {
1582  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1583  if ( invert )
1584  {
1585  if ( deleteObject() ) delete this;
1586  return c.getval();
1587  }
1588  ASSERT( ! c.isZero(), "divide by zero!" );
1589  if ( c.isOne() )
1590  {
1591  if ( getRefCount() <= 1 )
1592  {
1593  delete this;
1594  return CFFactory::basic( 0L );
1595  }
1596  else
1597  {
1598  decRefCount();
1599  return CFFactory::basic( 0L );
1600  }
1601  }
1602  else
1603  {
1604  if ( getRefCount() <= 1 )
1605  {
1607  if ( firstTerm && firstTerm->exp != 0 )
1608  return this;
1609  else if ( firstTerm )
1610  {
1612  delete this;
1613  return res;
1614  }
1615  else
1616  {
1617  delete this;
1618  return CFFactory::basic( 0L );
1619  }
1620  }
1621  else
1622  {
1623  decRefCount();
1624  termList last, first = copyTermList( firstTerm, last );
1625  first = modTermList( first, c, last );
1626  if ( first && first->exp != 0 )
1627  return new InternalPoly( first, last, var );
1628  else if ( first )
1629  {
1630  InternalCF * res = first->coeff.getval();
1631  delete first;
1632  return res;
1633  }
1634  else
1635  {
1636  delete first;
1637  return CFFactory::basic( 0L );
1638  }
1639  }
1640  }
1641 }
1642 
1643 void
1645 {
1646  if ( inExtension() && getReduce( var ) )
1647  {
1648  quot = copyObject();
1649  quot = quot->dividecoeff( cc, invert );
1650  rem = CFFactory::basic( 0L );
1651  }
1652  else if ( invert )
1653  {
1654  if ( is_imm( cc ) )
1655  rem = cc;
1656  else
1657  rem = cc->copyObject();
1658  quot = CFFactory::basic( 0L );
1659  }
1660  else
1661  {
1662  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1663  ASSERT( ! c.isZero(), "divide by zero!" );
1664  termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
1665  quotfirst = divideTermList( quotfirst, c, quotlast );
1666  if ( quotfirst )
1667  if ( quotfirst->exp == 0 )
1668  {
1669  quot = quotfirst->coeff.getval();
1670  delete quotfirst;
1671  }
1672  else
1673  quot = new InternalPoly( quotfirst, quotlast, var );
1674  else
1675  quot = CFFactory::basic( 0L );
1676  rem = CFFactory::basic( 0L );
1677  }
1678 }
1679 
1680 bool
1682 {
1683  if ( inExtension() && getReduce( var ) )
1684  {
1685  quot = copyObject();
1686  quot = quot->dividecoeff( cc, invert );
1687  rem = CFFactory::basic( 0L );
1688  return true;
1689  }
1690  else if ( invert )
1691  {
1692  if ( is_imm( cc ) )
1693  rem = cc;
1694  else
1695  rem = cc->copyObject();
1696  quot = CFFactory::basic( 0L );
1697  return true;
1698  }
1699  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1700  ASSERT( ! c.isZero(), "divide by zero!" );
1701  termList quotfirst, quotcursor;
1702  termList cursor;
1703  CanonicalForm cquot, crem;
1704  bool divideok = true;
1705 
1706  cursor = firstTerm;
1707  quotcursor = quotfirst = new term;
1708 
1709  while ( cursor && divideok )
1710  {
1711  divideok = divremt( cursor->coeff, c, cquot, crem );
1712  divideok = divideok && crem.isZero();
1713  if ( divideok )
1714  {
1715  if ( ! cquot.isZero() )
1716  {
1717  quotcursor->next = new term( 0, cquot, cursor->exp );
1718  quotcursor = quotcursor->next;
1719  }
1720  cursor = cursor->next;
1721  }
1722  }
1723  quotcursor->next = 0;
1724  if ( divideok )
1725  {
1726  cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1727  if ( quotfirst )
1728  if ( quotfirst->exp == 0 )
1729  {
1730  quot = quotfirst->coeff.getval();
1731  delete quotfirst;
1732  }
1733  else
1734  quot = new InternalPoly( quotfirst, quotcursor, var );
1735  else
1736  quot = CFFactory::basic( 0L );
1737  rem = CFFactory::basic( 0L );
1738  }
1739  else
1740  {
1741  freeTermList( quotfirst );
1742  }
1743  return divideok;
1744 }
1745 
1746 bool
1747 InternalPoly::tryDivremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert, const CanonicalForm& M, bool& fail )
1748 {
1749  if ( inExtension() && !getReduce( var ) )
1750  {
1751  quot = copyObject();
1752  quot = quot->tryDividecoeff( cc, invert, M, fail );
1753  if (fail)
1754  return false;
1755  rem = CFFactory::basic( 0L );
1756  return true;
1757  }
1758  else if ( invert )
1759  {
1760  if ( is_imm( cc ) )
1761  rem = cc;
1762  else
1763  rem = cc->copyObject();
1764  quot = CFFactory::basic( 0L );
1765  return true;
1766  }
1767  CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1768  ASSERT( ! c.isZero(), "divide by zero!" );
1769  termList quotfirst, quotcursor;
1770  termList cursor;
1771  CanonicalForm cquot, crem;
1772  bool divideok = true;
1773 
1774  cursor = firstTerm;
1775  quotcursor = quotfirst = new term;
1776 
1777  while ( cursor && divideok )
1778  {
1779  divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail );
1780  if (fail)
1781  {
1782  freeTermList (quotfirst);
1783  return false;
1784  }
1785  divideok = divideok && crem.isZero();
1786  if ( divideok )
1787  {
1788  if ( ! cquot.isZero() )
1789  {
1790  quotcursor->next = new term( 0, cquot, cursor->exp );
1791  quotcursor = quotcursor->next;
1792  }
1793  cursor = cursor->next;
1794  }
1795  }
1796  quotcursor->next = 0;
1797  if ( divideok )
1798  {
1799  cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1800  if ( quotfirst )
1801  if ( quotfirst->exp == 0 )
1802  {
1803  quot = quotfirst->coeff.getval();
1804  delete quotfirst;
1805  }
1806  else
1807  quot = new InternalPoly( quotfirst, quotcursor, var );
1808  else
1809  quot = CFFactory::basic( 0L );
1810  rem = CFFactory::basic( 0L );
1811  }
1812  else
1813  {
1814  freeTermList( quotfirst );
1815  }
1816  return divideok;
1817 }
1818 
1819 // static functions
1820 
1821 termList
1822 InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
1823 {
1824  if ( aTermList == 0 )
1825  return 0;
1826  else if ( negate )
1827  {
1828  termList sourceCursor = aTermList;
1829  termList dummy = new term;
1830  termList targetCursor = dummy;
1831 
1832  while ( sourceCursor )
1833  {
1834  targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1835  targetCursor = targetCursor->next;
1836  sourceCursor = sourceCursor->next;
1837  }
1838  targetCursor->next = 0;
1839  theLastTerm = targetCursor;
1840  targetCursor = dummy->next;
1841  delete dummy;
1842  return targetCursor;
1843  }
1844  else
1845  {
1846  termList sourceCursor = aTermList;
1847  termList dummy = new term;
1848  termList targetCursor = dummy;
1849 
1850  while ( sourceCursor )
1851  {
1852  targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1853  targetCursor = targetCursor->next;
1854  sourceCursor = sourceCursor->next;
1855  }
1856  targetCursor->next = 0;
1857  theLastTerm = targetCursor;
1858  targetCursor = dummy->next;
1859  delete dummy;
1860  return targetCursor;
1861  }
1862 }
1863 
1864 termList
1866 {
1867  if ( aTermList == 0 )
1868  return 0;
1869  else
1870  {
1871  termList sourceCursor = aTermList;
1872  termList dummy = new term;
1873  termList targetCursor = dummy;
1874 
1875  while ( sourceCursor )
1876  {
1877  targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1878  targetCursor = targetCursor->next;
1879  sourceCursor = sourceCursor->next;
1880  }
1881  targetCursor->next = 0;
1882  theLastTerm = targetCursor;
1883  targetCursor = dummy->next;
1884  delete dummy;
1885  return targetCursor;
1886  }
1887 }
1888 
1889 void
1891 {
1892  termList cursor = aTermList;
1893 
1894  while ( cursor )
1895  {
1896  cursor = cursor->next;
1897  delete aTermList;
1898  aTermList = cursor;
1899  }
1900 }
1901 
1902 void
1904 {
1905  termList cursor = terms;
1906  while ( cursor )
1907  {
1908  cursor->coeff = -cursor->coeff;
1909  cursor = cursor->next;
1910  }
1911 }
1912 
1913 termList
1914 InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
1915 {
1916  termList theCursor = theList;
1917  termList aCursor = aList;
1918  termList predCursor = 0;
1919 
1920  while ( theCursor && aCursor )
1921  {
1922  if ( theCursor->exp == aCursor->exp )
1923  {
1924  if ( negate )
1925  theCursor->coeff -= aCursor->coeff;
1926  else
1927  theCursor->coeff += aCursor->coeff;
1928  if ( theCursor->coeff.isZero() )
1929  {
1930  if ( predCursor )
1931  {
1932  predCursor->next = theCursor->next;
1933  delete theCursor;
1934  theCursor = predCursor->next;
1935  }
1936  else
1937  {
1938  theList = theList->next;
1939  delete theCursor;
1940  theCursor = theList;
1941  }
1942  }
1943  else
1944  {
1945  predCursor = theCursor;
1946  theCursor = theCursor->next;
1947  }
1948  aCursor = aCursor->next;
1949  }
1950  else if ( theCursor->exp < aCursor->exp )
1951  {
1952  if ( negate )
1953  if ( predCursor )
1954  {
1955  predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1956  predCursor = predCursor->next;
1957  }
1958  else
1959  {
1960  theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1961  predCursor = theList;
1962  }
1963  else
1964  if ( predCursor )
1965  {
1966  predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1967  predCursor = predCursor->next;
1968  }
1969  else
1970  {
1971  theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1972  predCursor = theList;
1973  }
1974  aCursor = aCursor->next;
1975  }
1976  else
1977  {
1978  predCursor = theCursor;
1979  theCursor = theCursor->next;
1980  }
1981  }
1982  if ( aCursor )
1983  {
1984  if ( predCursor )
1985  predCursor->next = copyTermList( aCursor, lastTerm, negate );
1986  else
1987  theList = copyTermList( aCursor, lastTerm, negate );
1988  }
1989  else if ( ! theCursor )
1990  lastTerm = predCursor;
1991 
1992  return theList;
1993 }
1994 
1995 void
1996 InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
1997 {
1998  while ( theCursor )
1999  {
2000  theCursor->coeff *= coeff;
2001  theCursor->exp += exp;
2002  theCursor = theCursor->next;
2003  }
2004 }
2005 
2006 termList
2007 InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
2008 {
2009  termList theCursor = firstTerm;
2010  lastTerm = 0;
2011  termList dummy;
2012 
2013  while ( theCursor )
2014  {
2015  theCursor->coeff /= coeff;
2016  if ( theCursor->coeff.isZero() )
2017  {
2018  if ( theCursor == firstTerm )
2019  firstTerm = theCursor->next;
2020  else
2021  lastTerm->next = theCursor->next;
2022  dummy = theCursor;
2023  theCursor = theCursor->next;
2024  delete dummy;
2025  }
2026  else
2027  {
2028  lastTerm = theCursor;
2029  theCursor = theCursor->next;
2030  }
2031  }
2032  return firstTerm;
2033 }
2034 
2035 termList
2036 InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
2037 {
2038  termList theCursor = firstTerm;
2039  lastTerm = 0;
2040  termList dummy;
2041 
2042  while ( theCursor )
2043  {
2044  theCursor->coeff.div( coeff );
2045  if ( theCursor->coeff.isZero() )
2046  {
2047  if ( theCursor == firstTerm )
2048  firstTerm = theCursor->next;
2049  else
2050  lastTerm->next = theCursor->next;
2051  dummy = theCursor;
2052  theCursor = theCursor->next;
2053  delete dummy;
2054  }
2055  else
2056  {
2057  lastTerm = theCursor;
2058  theCursor = theCursor->next;
2059  }
2060  }
2061  return firstTerm;
2062 }
2063 
2064 termList
2065 InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail )
2066 {
2067  termList theCursor = firstTerm;
2068  lastTerm = 0;
2069  termList dummy;
2070 
2071  while ( theCursor )
2072  {
2073  theCursor->coeff.tryDiv( coeff, M, fail );
2074  if (fail)
2075  return 0;
2076  if ( theCursor->coeff.isZero() )
2077  {
2078  if ( theCursor == firstTerm )
2079  firstTerm = theCursor->next;
2080  else
2081  lastTerm->next = theCursor->next;
2082  dummy = theCursor;
2083  theCursor = theCursor->next;
2084  delete dummy;
2085  }
2086  else
2087  {
2088  lastTerm = theCursor;
2089  theCursor = theCursor->next;
2090  }
2091  }
2092  return firstTerm;
2093 }
2094 
2095 termList
2096 InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
2097 {
2098  termList theCursor = firstTerm;
2099  lastTerm = 0;
2100  termList dummy;
2101 
2102  while ( theCursor )
2103  {
2104  theCursor->coeff.mod( coeff );
2105  if ( theCursor->coeff.isZero() )
2106  {
2107  if ( theCursor == firstTerm )
2108  firstTerm = theCursor->next;
2109  else
2110  lastTerm->next = theCursor->next;
2111  dummy = theCursor;
2112  theCursor = theCursor-> next;
2113  delete dummy;
2114  }
2115  else
2116  {
2117  lastTerm = theCursor;
2118  theCursor = theCursor->next;
2119  }
2120  }
2121  return firstTerm;
2122 }
2123 
2124 void
2126 {
2127  if ( last )
2128  {
2129  last->next = new term( 0, coeff, exp );
2130  last = last->next;
2131  }
2132  else
2133  {
2134  first = new term( 0, coeff, exp );
2135  last = first;
2136  }
2137 }
2138 
2139 termList
2140 InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
2141 {
2142  termList theCursor = theList;
2143  termList aCursor = aList;
2144  termList predCursor = 0;
2146 
2147  if ( negate )
2148  coeff = -c;
2149  else
2150  coeff = c;
2151 
2152  while ( theCursor && aCursor )
2153  {
2154  if ( theCursor->exp == aCursor->exp + exp )
2155  {
2156  theCursor->coeff += aCursor->coeff * coeff;
2157  if ( theCursor->coeff.isZero() )
2158  {
2159  if ( predCursor )
2160  {
2161  predCursor->next = theCursor->next;
2162  delete theCursor;
2163  theCursor = predCursor->next;
2164  }
2165  else
2166  {
2167  theList = theList->next;
2168  delete theCursor;
2169  theCursor = theList;
2170  }
2171  }
2172  else
2173  {
2174  predCursor = theCursor;
2175  theCursor = theCursor->next;
2176  }
2177  aCursor = aCursor->next;
2178  }
2179  else if ( theCursor->exp < aCursor->exp + exp )
2180  {
2181  if ( predCursor )
2182  {
2183  predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
2184  predCursor = predCursor->next;
2185  }
2186  else
2187  {
2188  theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
2189  predCursor = theList;
2190  }
2191  aCursor = aCursor->next;
2192  }
2193  else
2194  {
2195  predCursor = theCursor;
2196  theCursor = theCursor->next;
2197  }
2198  }
2199  if ( aCursor )
2200  {
2201  if ( predCursor )
2202  {
2203  predCursor->next = copyTermList( aCursor, lastTerm );
2204  predCursor = predCursor->next;
2205  }
2206  else
2207  {
2208  theList = copyTermList( aCursor, lastTerm );
2209  predCursor = theList;
2210  }
2211  while ( predCursor )
2212  {
2213  predCursor->exp += exp;
2214  predCursor->coeff *= coeff;
2215  predCursor = predCursor->next;
2216  }
2217  }
2218  else if ( ! theCursor )
2219  lastTerm = predCursor;
2220  return theList;
2221 }
2222 
2223 termList
2225 {
2226  CanonicalForm coeff = CanonicalForm (1)/redterms->coeff;
2227  CanonicalForm newcoeff;
2228  int newexp;
2229  int exp = redterms->exp;
2230  termList dummy;
2231  while ( first && ( first->exp >= exp ) )
2232  {
2233  newcoeff = first->coeff * coeff;
2234  newexp = first->exp - exp;
2235  dummy = first;
2236  first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
2237  delete dummy;
2238  }
2239  return first;
2240 }
2241 
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
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Header for factory's main class CanonicalForm.
#define OSTREAM
Definition: canonicalform.h:16
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:62
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
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
int i
Definition: cfEzgcd.cc:125
Variable x
Definition: cfModGcd.cc:4023
g
Definition: cfModGcd.cc:4031
CanonicalForm test
Definition: cfModGcd.cc:4037
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:173
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
#define LEVELBASE
Definition: cf_defs.h:16
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
static InternalCF * basic(long value)
Definition: cf_factory.cc:30
factory's main class
Definition: canonicalform.h:83
int sign() const
int CanonicalForm::sign () const
CanonicalForm deepCopy() const
CanonicalForm Lc() const
InternalCF * getval() const
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
bool inCoeffDomain() const
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
CanonicalForm & mod(const CanonicalForm &)
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
void print(OSTREAM &, char *) const
input/output
CanonicalForm & div(const CanonicalForm &)
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
virtual InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
Definition: int_cf.cc:179
virtual InternalCF * mulsame(InternalCF *) PVIRT_INTCF("mulsame")
virtual InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition: int_cf.cc:221
int getRefCount()
Definition: int_cf.h:51
virtual InternalCF * tryInvert(const CanonicalForm &, bool &)
Definition: int_cf.cc:186
int decRefCount()
Definition: int_cf.h:53
virtual InternalCF * invert()
Definition: int_cf.cc:172
int deleteObject()
Definition: int_cf.h:61
virtual int level() const
Definition: int_cf.h:67
InternalCF * copyObject()
Definition: int_cf.h:62
virtual InternalCF * dividecoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
factory's class for integers
Definition: int_int.h:41
factory's class for polynomials
Definition: int_poly.h:71
InternalCF * addsame(InternalCF *)
Definition: int_poly.cc:278
static termList divideTermList(termList, const CanonicalForm &, termList &)
Definition: int_poly.cc:2007
int taildegree()
Definition: int_poly.cc:145
static termList addTermList(termList, termList, termList &, bool negate)
Definition: int_poly.cc:1914
InternalCF * mulcoeff(InternalCF *)
Definition: int_poly.cc:1173
Variable var
Definition: int_poly.h:74
void print(OSTREAM &, char *)
Definition: int_poly.cc:171
static termList reduceTermList(termList first, termList redterms, termList &last)
Definition: int_poly.cc:2224
CanonicalForm LC()
Definition: int_poly.cc:130
InternalCF * modsame(InternalCF *)
Definition: int_poly.cc:685
int degree()
int InternalPoly::degree ()
Definition: int_poly.cc:92
static void freeTermList(termList)
Definition: int_poly.cc:1890
InternalCF * deepCopyObject() const
Definition: int_poly.cc:68
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
Definition: int_poly.cc:809
InternalCF * neg()
InternalCF * InternalPoly::neg ()
Definition: int_poly.cc:223
InternalCF * tryDivcoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition: int_poly.cc:1467
static const omBin InternalPoly_bin
Definition: int_poly.h:159
static void mulTermList(termList, const CanonicalForm &, const int)
Definition: int_poly.cc:1996
bool isUnivariate() const
Definition: int_poly.cc:76
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_poly.cc:1644
int comparesame(InternalCF *)
comparesame(), comparecoeff() - compare with an InternalPoly.
Definition: int_poly.cc:982
InternalCF * invert()
Definition: int_poly.cc:239
InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition: int_poly.cc:1295
InternalCF * modulocoeff(InternalCF *, bool)
Definition: int_poly.cc:1566
InternalCF * subsame(InternalCF *)
Definition: int_poly.cc:318
termList firstTerm
Definition: int_poly.h:73
InternalCF * divcoeff(InternalCF *, bool)
Definition: int_poly.cc:1391
InternalCF * modcoeff(InternalCF *, bool)
Definition: int_poly.cc:1580
bool inExtension() const
Definition: int_poly.h:110
InternalCF * modulosame(InternalCF *)
Definition: int_poly.cc:679
static void negateTermList(termList)
Definition: int_poly.cc:1903
static termList tryDivTermList(termList, const CanonicalForm &, termList &, const CanonicalForm &, bool &)
Definition: int_poly.cc:2065
static termList mulAddTermList(termList theList, termList aList, const CanonicalForm &c, const int exp, termList &lastTerm, bool negate)
Definition: int_poly.cc:2140
bool tryDivremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
Definition: int_poly.cc:1747
termList lastTerm
Definition: int_poly.h:73
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
Definition: int_poly.cc:757
InternalCF * dividesame(InternalCF *)
Definition: int_poly.cc:483
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_poly.cc:1681
CanonicalForm coeff(int i)
CanonicalForm InternalPoly::coeff ( int i )
Definition: int_poly.cc:154
InternalCF * dividecoeff(InternalCF *, bool)
Definition: int_poly.cc:1209
int comparecoeff(InternalCF *)
comparecoeff() always returns 1 since CO is defined to be larger than anything which is a coefficient...
Definition: int_poly.cc:1024
CanonicalForm tailcoeff()
CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
Definition: int_poly.cc:139
static termList deepCopyTermList(termList, termList &)
Definition: int_poly.cc:1865
InternalCF * divsame(InternalCF *)
Definition: int_poly.cc:490
InternalCF * addcoeff(InternalCF *)
Definition: int_poly.cc:1030
InternalCF * subcoeff(InternalCF *, bool)
Definition: int_poly.cc:1087
bool tryDivremsamet(InternalCF *, InternalCF *&, InternalCF *&, const CanonicalForm &, bool &)
Definition: int_poly.cc:875
CanonicalForm lc()
Definition: int_poly.cc:112
static termList modTermList(termList, const CanonicalForm &, termList &)
Definition: int_poly.cc:2096
static termList copyTermList(termList, termList &, bool negate=false)
Definition: int_poly.cc:1822
static void appendTermList(termList &, termList &, const CanonicalForm &, const int)
Definition: int_poly.cc:2125
CanonicalForm Lc()
Definition: int_poly.cc:121
static termList divTermList(termList, const CanonicalForm &, termList &)
Definition: int_poly.cc:2036
InternalCF * mulsame(InternalCF *)
Definition: int_poly.cc:358
InternalCF * tryInvert(const CanonicalForm &, bool &)
Definition: int_poly.cc:256
InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
Definition: int_poly.cc:420
int sign() const
int InternalPoly::sign () const
Definition: int_poly.cc:102
InternalCF * tryDivsame(InternalCF *, const CanonicalForm &, bool &)
Definition: int_poly.cc:576
factory's class for variables
Definition: factory.h:118
Definition: int_poly.h:33
static const omBin term_bin
Definition: int_poly.h:39
term * next
Definition: int_poly.h:35
CanonicalForm coeff
Definition: int_poly.h:36
int exp
Definition: int_poly.h:37
CanonicalForm res
Definition: facAbsFact.cc:64
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
static poly last
Definition: hdegree.cc:1077
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Factory's internal CanonicalForm's.
Factory's internal integers.
Factory's internal polynomials.
ListNode * next
Definition: janet.h:31
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
#define omGetSpecBin(size)
Definition: omBin.h:11
omBin_t * omBin
Definition: omStructs.h:12
#define M
Definition: sirandom.c:24
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
InternalPoly * getInternalMipo(const Variable &alpha)
Definition: variable.cc:201
operations on variables