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