My Project
Loading...
Searching...
No Matches
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>
16using 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
42const 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
58InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
59{
60 var = v;
61 firstTerm = new term( 0, c, e );
63}
64
66{
67 ASSERT( 0, "ups there is something wrong in your code" );
68}
69
71{
73}
74
77{
78 termList first, last;
80 return new InternalPoly( first, last, var );
81}
82
83bool
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**/
99int
101{
102 return firstTerm->exp;
103}
104
105
106/** int InternalPoly::sign () const
107 * @sa CanonicalForm::sign()
108**/
109int
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
152int
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
178void
179InternalPoly::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**/
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
248{
249 if ( inExtension() && getReduce( var ) )
250 {
251 setReduce( var, false );
252 CanonicalForm a( this->copyObject() );
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
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
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();
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
327{
328 InternalPoly * aPoly = (InternalPoly*)aCoeff;
329 if ( getRefCount() <= 1 )
330 {
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();
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
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
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
492{
493 return divsame( aCoeff );
494}
495
496
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
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
688{
689 return modsame( aCoeff );
690}
691
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
764void
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
816bool
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
882bool
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 {
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**/
989int
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 inequality 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**/
1031int
1033{
1034 return 1;
1035}
1036
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 );
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
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 );
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
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();
1210 mulTermList( first, c, 0 );
1211 return new InternalPoly( first, last, var );
1212 }
1213 }
1214}
1215
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 {
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();
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
1303InternalPoly::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 {
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();
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
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();
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
1475InternalPoly::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 {
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();
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
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
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();
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
1651void
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
1688bool
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
1754bool
1755InternalPoly::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
1830InternalPoly::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
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
1897void
1899{
1900 termList cursor = aTermList;
1901
1902 while ( LIKELY(cursor) )
1903 {
1904 cursor = cursor->next;
1905 delete aTermList;
1906 aTermList = cursor;
1907 }
1908}
1909
1910void
1912{
1913 termList cursor = terms;
1914 while ( LIKELY(cursor) )
1915 {
1916 cursor->coeff = -cursor->coeff;
1917 cursor = cursor->next;
1918 }
1919}
1920
1922InternalPoly::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
2037void
2038InternalPoly::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
2049InternalPoly::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
2078InternalPoly::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
2107InternalPoly::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
2138InternalPoly::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
2166void
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
2182InternalPoly::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
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
#define UNLIKELY(X)
Definition: auxiliary.h:404
#define LIKELY(X)
Definition: auxiliary.h:403
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:4082
g
Definition: cfModGcd.cc:4090
CanonicalForm test
Definition: cfModGcd.cc:4096
CanonicalForm b
Definition: cfModGcd.cc:4103
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:25
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.
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
InternalCF * copyObject()
Definition: int_cf.h:62
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
virtual InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition: int_cf.cc:221
virtual InternalCF * dividecoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
int getRefCount()
Definition: int_cf.h:51
virtual InternalCF * tryInvert(const CanonicalForm &, bool &)
Definition: int_cf.cc:186
virtual void print(OSTREAM &, char *) PVIRT_VOID("print")
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
virtual InternalCF * mulsame(InternalCF *) PVIRT_INTCF("mulsame")
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
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: variable.h:33
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
STATIC_VAR poly last
Definition: hdegree.cc:1173
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Factory's internal CanonicalForm's.
Factory's internal integers.
Factory's internal polynomials.
ListNode * next
Definition: janet.h:31
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
#define omGetSpecBin(size)
Definition: omBin.h:11
omBin_t * omBin
Definition: omStructs.h:12
#define M
Definition: sirandom.c:25
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
InternalPoly * getInternalMipo(const Variable &alpha)
Definition: variable.cc:201
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
operations on variables