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