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
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 {
296 InternalCF * res = firstTerm->coeff.getval();
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 {
336 InternalCF * res = firstTerm->coeff.getval();
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 {
1003 // we test on inequality of coefficients at this
1004 // point instead of testing on "less than" at the
1005 // last `else' in the enclosed `if' statement since a
1006 // test on inequality in general is cheaper
1007 if ( cursor1->exp > cursor2->exp )
1008 return 1;
1009 else if ( cursor1->exp < cursor2->exp )
1010 return -1;
1011 if ( (cursor1->coeff != cursor2->coeff) )
1012 {
1013 if ( cursor1->coeff > cursor2->coeff )
1014 return 1;
1015 else
1016 return -1;
1017 }
1018 }
1019 // check trailing terms
1020 if ( cursor1 == cursor2 )
1021 return 0;
1022 else if ( cursor1 != 0 )
1023 return 1;
1024 else
1025 return -1;
1026 }
1027}
1028
1029/**
1030 * comparecoeff() always returns 1 since CO is defined to be
1031 * larger than anything which is a coefficient w.r.t. CO.
1032**/
1033int
1035{
1036 return 1;
1037}
1038
1041{
1042 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1043 if ( c.isZero() )
1044 return this;
1045 else
1046 {
1047 if ( getRefCount() <= 1 )
1048 {
1049 if ( lastTerm->exp == 0 )
1050 {
1051 lastTerm->coeff += c;
1052 if ( lastTerm->coeff.isZero() )
1053 {
1054 termList cursor = firstTerm;
1055 while ( cursor->next != lastTerm )
1056 cursor = cursor->next;
1057 delete lastTerm;
1058 cursor->next = 0;
1059 lastTerm = cursor;
1060 }
1061 }
1062 else
1063 {
1064 lastTerm->next = new term( 0, c, 0 );
1065 lastTerm = lastTerm->next;
1066 }
1067 return this;
1068 }
1069 else
1070 {
1071 decRefCount();
1072 termList last, first = copyTermList( firstTerm, last, false );
1073 if ( last->exp == 0 )
1074 {
1075 last->coeff += c;
1076 if ( last->coeff.isZero() )
1077 {
1078 termList cursor = first;
1079 while ( cursor->next != last )
1080 cursor = cursor->next;
1081 delete last;
1082 cursor->next = 0;
1083 last = cursor;
1084 }
1085 }
1086 else
1087 {
1088 last->next = new term( 0, c, 0L );
1089 last = last->next;
1090 }
1091 return new InternalPoly( first, last, var );
1092 }
1093 }
1094}
1095
1098{
1099 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1100 if ( c.isZero() )
1101 if ( getRefCount() > 1 )
1102 {
1103 decRefCount();
1104 termList last, first = copyTermList( firstTerm, last, negate );
1105 return new InternalPoly( first, last, var );
1106 }
1107 else
1108 {
1109 if ( negate )
1111 return this;
1112 }
1113 else
1114 {
1115 if ( getRefCount() <= 1 )
1116 {
1117 if ( lastTerm->exp == 0 )
1118 {
1119 if ( negate )
1120 {
1122 lastTerm->coeff += c;
1123 }
1124 else
1125 lastTerm->coeff -= c;
1126 if ( lastTerm->coeff.isZero() )
1127 {
1128 termList cursor = firstTerm;
1129 while ( cursor->next != lastTerm )
1130 cursor = cursor->next;
1131 delete lastTerm;
1132 cursor->next = 0;
1133 lastTerm = cursor;
1134 }
1135 }
1136 else
1137 {
1138 if ( negate )
1139 {
1141 lastTerm->next = new term( 0, c, 0 );
1142 }
1143 else
1144 lastTerm->next = new term( 0, -c, 0 );
1145 lastTerm = lastTerm->next;
1146 }
1147 return this;
1148 }
1149 else
1150 {
1151 decRefCount();
1152 termList last, first = copyTermList( firstTerm, last, negate );
1153 if ( last->exp == 0 )
1154 {
1155 if ( negate )
1156 last->coeff += c;
1157 else
1158 last->coeff -= c;
1159 if ( last->coeff.isZero() )
1160 {
1161 termList cursor = first;
1162 while ( cursor->next != last )
1163 cursor = cursor->next;
1164 delete last;
1165 cursor->next = 0;
1166 last = cursor;
1167 }
1168 }
1169 else
1170 {
1171 if ( negate )
1172 last->next = new term( 0, c, 0 );
1173 else
1174 last->next = new term( 0, -c, 0 );
1175 last = last->next;
1176 }
1177 return new InternalPoly( first, last, var );
1178 }
1179 }
1180}
1181
1184{
1185 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1186 if ( c.isZero() )
1187 {
1188 if ( getRefCount() <= 1 )
1189 {
1190 delete this;
1191 return CFFactory::basic( 0 );
1192 }
1193 else
1194 {
1195 decRefCount();
1196 return CFFactory::basic( 0 );
1197 }
1198 }
1199 else if ( c.isOne() )
1200 return this;
1201 else
1202 {
1203 if ( getRefCount() <= 1 )
1204 {
1205 mulTermList( firstTerm, c, 0 );
1206 return this;
1207 }
1208 else
1209 {
1210 decRefCount();
1212 mulTermList( first, c, 0 );
1213 return new InternalPoly( first, last, var );
1214 }
1215 }
1216}
1217
1220{
1221 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1222 if ( inExtension() && getReduce( var ) && invert )
1223 {
1224 InternalCF * dummy;
1225 dummy = this->invert();
1226 if (is_imm(dummy))
1227 {
1228 if (is_imm(cc))
1229 {
1231 dummy=d;
1232 }
1233 else
1234 dummy=cc->mulcoeff(dummy);
1235 }
1236 else dummy = dummy->mulcoeff( cc );
1237 if ( getRefCount() <= 1 )
1238 {
1239 delete this;
1240 return dummy;
1241 }
1242 else
1243 {
1244 decRefCount();
1245 return dummy;
1246 }
1247 }
1248 if ( invert )
1249 {
1250 if ( getRefCount() <= 1 )
1251 {
1252 delete this;
1253 return CFFactory::basic( 0 );
1254 }
1255 else
1256 {
1257 decRefCount();
1258 return CFFactory::basic( 0 );
1259 }
1260 }
1261 if ( c.isOne() )
1262 return this;
1263 else
1264 {
1265 if ( getRefCount() <= 1 )
1266 {
1268 if ( firstTerm && firstTerm->exp != 0 )
1269 return this;
1270 else if ( firstTerm )
1271 {
1272 InternalCF * res = firstTerm->coeff.getval();
1273 delete this;
1274 return res;
1275 }
1276 else
1277 {
1278 delete this;
1279 return CFFactory::basic( 0 );
1280 }
1281 }
1282 else
1283 {
1284 decRefCount();
1286 first = divideTermList( first, c, last );
1287 if ( first && first->exp != 0 )
1288 return new InternalPoly( first, last, var );
1289 else if ( first )
1290 {
1291 InternalCF * res = first->coeff.getval();
1292 delete first;
1293 return res;
1294 }
1295 else
1296 {
1297 delete first;
1298 return CFFactory::basic( 0 );
1299 }
1300 }
1301 }
1302}
1303
1306{
1307 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1308 if ( inExtension() && !getReduce( var ) && invert )
1309 {
1310 InternalCF * dummy;
1311 dummy = this->tryInvert(M, fail);
1312 if (fail)
1313 {
1314 if (getRefCount() <= 1)
1315 delete this;
1316 else
1317 decRefCount();
1318 return dummy; //is equal to CFFactory::basic ( 0 ) in this case
1319 }
1320 if (is_imm(dummy))
1321 {
1322 if (is_imm(cc))
1323 {
1325 dummy=d;
1326 }
1327 else
1328 dummy=cc->mulcoeff(dummy);
1329 }
1330 else dummy = dummy->mulcoeff( cc );
1331 if ( getRefCount() <= 1 )
1332 {
1333 delete this;
1334 return dummy;
1335 }
1336 else
1337 {
1338 decRefCount();
1339 return dummy;
1340 }
1341 }
1342 if ( invert )
1343 {
1344 if ( getRefCount() <= 1 )
1345 {
1346 delete this;
1347 return CFFactory::basic( 0 );
1348 }
1349 else
1350 {
1351 decRefCount();
1352 return CFFactory::basic( 0 );
1353 }
1354 }
1355 if ( c.isOne() )
1356 return this;
1357 //one should never get here
1358 else
1359 {
1360 if ( getRefCount() <= 1 )
1361 {
1363 if ( firstTerm && firstTerm->exp != 0 )
1364 return this;
1365 else if ( firstTerm )
1366 {
1367 InternalCF * res = firstTerm->coeff.getval();
1368 delete this;
1369 return res;
1370 }
1371 else
1372 {
1373 delete this;
1374 return CFFactory::basic( 0 );
1375 }
1376 }
1377 else
1378 {
1379 decRefCount();
1381 first = divideTermList( first, c, last );
1382 if ( first && first->exp != 0 )
1383 return new InternalPoly( first, last, var );
1384 else if ( first )
1385 {
1386 InternalCF * res = first->coeff.getval();
1387 delete first;
1388 return res;
1389 }
1390 else
1391 {
1392 delete first;
1393 return CFFactory::basic( 0 );
1394 }
1395 }
1396 }
1397}
1398
1399
1402{
1403 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1404 if ( inExtension() && getReduce( var ) && invert )
1405 {
1406 InternalCF * dummy;
1407 dummy = this->invert();
1408 dummy = dummy->mulcoeff( cc );
1409 if ( getRefCount() <= 1 )
1410 {
1411 delete this;
1412 return dummy;
1413 }
1414 else
1415 {
1416 decRefCount();
1417 return dummy;
1418 }
1419 }
1420 if ( invert )
1421 {
1422 if ( getRefCount() <= 1 )
1423 {
1424 delete this;
1425 return CFFactory::basic( 0 );
1426 }
1427 else
1428 {
1429 decRefCount();
1430 return CFFactory::basic( 0 );
1431 }
1432 }
1433 if ( c.isOne() )
1434 return this;
1435 else
1436 {
1437 if ( getRefCount() <= 1 )
1438 {
1440 if ( firstTerm && firstTerm->exp != 0 )
1441 return this;
1442 else if ( firstTerm )
1443 {
1444 InternalCF * res = firstTerm->coeff.getval();
1445 delete this;
1446 return res;
1447 }
1448 else
1449 {
1450 delete this;
1451 return CFFactory::basic( 0 );
1452 }
1453 }
1454 else
1455 {
1456 decRefCount();
1458 first = divTermList( first, c, last );
1459 if ( first && first->exp != 0 )
1460 return new InternalPoly( first, last, var );
1461 else if ( first )
1462 {
1463 InternalCF * res = first->coeff.getval();
1464 delete first;
1465 return res;
1466 }
1467 else
1468 {
1469 delete first;
1470 return CFFactory::basic( 0 );
1471 }
1472 }
1473 }
1474}
1475
1478{
1479 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1480 if ( inExtension() && !getReduce( var ) && invert )
1481 {
1482 InternalCF * dummy;
1483 dummy = this->tryInvert(M, fail);
1484 if (fail)
1485 {
1486 if (getRefCount() <= 1)
1487 delete this;
1488 else
1489 decRefCount();
1490 return dummy;
1491 }
1492 dummy = dummy->mulcoeff( cc );
1493 if ( getRefCount() <= 1 )
1494 {
1495 delete this;
1496 return dummy;
1497 }
1498 else
1499 {
1500 decRefCount();
1501 return dummy;
1502 }
1503 }
1504 if ( invert )
1505 {
1506 if ( getRefCount() <= 1 )
1507 {
1508 delete this;
1509 return CFFactory::basic( 0 );
1510 }
1511 else
1512 {
1513 decRefCount();
1514 return CFFactory::basic( 0 );
1515 }
1516 }
1517 if ( c.isOne() )
1518 return this;
1519 else
1520 {
1521 if ( getRefCount() <= 1 )
1522 {
1524 if (fail)
1525 {
1526 delete this;
1527 return CFFactory::basic (0);
1528 }
1529 if ( firstTerm && firstTerm->exp != 0 )
1530 return this;
1531 else if ( firstTerm )
1532 {
1533 InternalCF * res = firstTerm->coeff.getval();
1534 delete this;
1535 return res;
1536 }
1537 else
1538 {
1539 delete this;
1540 return CFFactory::basic( 0 );
1541 }
1542 }
1543 else
1544 {
1545 decRefCount();
1547 first = tryDivTermList( first, c, last, M, fail );
1548 if (fail)
1549 {
1550 delete this;
1551 return CFFactory::basic (0);
1552 }
1553 if (fail)
1554 {
1555 delete first;
1556 return CFFactory::basic (0);
1557 }
1558 if ( first && first->exp != 0 )
1559 return new InternalPoly( first, last, var );
1560 else if ( first )
1561 {
1562 InternalCF * res = first->coeff.getval();
1563 delete first;
1564 return res;
1565 }
1566 else
1567 {
1568 delete first;
1569 return CFFactory::basic( 0 );
1570 }
1571 }
1572 }
1573}
1574
1577{
1578 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1579 if ( invert )
1580 {
1581 if ( deleteObject() ) delete this;
1582 return c.getval();
1583 }
1584 ASSERT( ! c.isZero(), "divide by zero!" );
1585 if ( deleteObject() ) delete this;
1586 return CFFactory::basic( 0 );
1587}
1588
1591{
1592 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1593 if ( invert )
1594 {
1595 if ( deleteObject() ) delete this;
1596 return c.getval();
1597 }
1598 ASSERT( ! c.isZero(), "divide by zero!" );
1599 if ( c.isOne() )
1600 {
1601 if ( getRefCount() <= 1 )
1602 {
1603 delete this;
1604 return CFFactory::basic( 0 );
1605 }
1606 else
1607 {
1608 decRefCount();
1609 return CFFactory::basic( 0 );
1610 }
1611 }
1612 else
1613 {
1614 if ( getRefCount() <= 1 )
1615 {
1617 if ( firstTerm && firstTerm->exp != 0 )
1618 return this;
1619 else if ( firstTerm )
1620 {
1621 InternalCF * res = firstTerm->coeff.getval();
1622 delete this;
1623 return res;
1624 }
1625 else
1626 {
1627 delete this;
1628 return CFFactory::basic( 0 );
1629 }
1630 }
1631 else
1632 {
1633 decRefCount();
1635 first = modTermList( first, c, last );
1636 if ( first && first->exp != 0 )
1637 return new InternalPoly( first, last, var );
1638 else if ( first )
1639 {
1640 InternalCF * res = first->coeff.getval();
1641 delete first;
1642 return res;
1643 }
1644 else
1645 {
1646 delete first;
1647 return CFFactory::basic( 0 );
1648 }
1649 }
1650 }
1651}
1652
1653void
1655{
1656 if ( inExtension() && getReduce( var ) )
1657 {
1658 quot = copyObject();
1659 quot = quot->dividecoeff( cc, invert );
1660 rem = CFFactory::basic( 0 );
1661 }
1662 else if ( invert )
1663 {
1664 if ( is_imm( cc ) )
1665 rem = cc;
1666 else
1667 rem = cc->copyObject();
1668 quot = CFFactory::basic( 0 );
1669 }
1670 else
1671 {
1672 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1673 ASSERT( ! c.isZero(), "divide by zero!" );
1674 termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
1675 quotfirst = divideTermList( quotfirst, c, quotlast );
1676 if ( quotfirst )
1677 if ( quotfirst->exp == 0 )
1678 {
1679 quot = quotfirst->coeff.getval();
1680 delete quotfirst;
1681 }
1682 else
1683 quot = new InternalPoly( quotfirst, quotlast, var );
1684 else
1685 quot = CFFactory::basic( 0 );
1686 rem = CFFactory::basic( 0 );
1687 }
1688}
1689
1690bool
1692{
1693 if ( inExtension() && getReduce( var ) )
1694 {
1695 quot = copyObject();
1696 quot = quot->dividecoeff( cc, invert );
1697 rem = CFFactory::basic( 0 );
1698 return true;
1699 }
1700 else if ( invert )
1701 {
1702 if ( is_imm( cc ) )
1703 rem = cc;
1704 else
1705 rem = cc->copyObject();
1706 quot = CFFactory::basic( 0 );
1707 return true;
1708 }
1709 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1710 ASSERT( ! c.isZero(), "divide by zero!" );
1711 termList quotfirst, quotcursor;
1712 termList cursor;
1713 CanonicalForm cquot, crem;
1714 bool divideok = true;
1715
1716 cursor = firstTerm;
1717 quotcursor = quotfirst = new term;
1718
1719 while ( cursor && divideok )
1720 {
1721 divideok = divremt( cursor->coeff, c, cquot, crem );
1722 divideok = divideok && crem.isZero();
1723 if ( divideok )
1724 {
1725 if ( ! cquot.isZero() )
1726 {
1727 quotcursor->next = new term( 0, cquot, cursor->exp );
1728 quotcursor = quotcursor->next;
1729 }
1730 cursor = cursor->next;
1731 }
1732 }
1733 quotcursor->next = 0;
1734 if ( divideok )
1735 {
1736 cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1737 if ( quotfirst )
1738 if ( quotfirst->exp == 0 )
1739 {
1740 quot = quotfirst->coeff.getval();
1741 delete quotfirst;
1742 }
1743 else
1744 quot = new InternalPoly( quotfirst, quotcursor, var );
1745 else
1746 quot = CFFactory::basic( 0 );
1747 rem = CFFactory::basic( 0 );
1748 }
1749 else
1750 {
1751 freeTermList( quotfirst );
1752 }
1753 return divideok;
1754}
1755
1756bool
1758{
1759 if ( inExtension() && !getReduce( var ) )
1760 {
1761 quot = copyObject();
1762 quot = quot->tryDividecoeff( cc, invert, M, fail );
1763 if (fail)
1764 return false;
1765 rem = CFFactory::basic( 0 );
1766 return true;
1767 }
1768 else if ( invert )
1769 {
1770 if ( is_imm( cc ) )
1771 rem = cc;
1772 else
1773 rem = cc->copyObject();
1774 quot = CFFactory::basic( 0 );
1775 return true;
1776 }
1777 CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1778 ASSERT( ! c.isZero(), "divide by zero!" );
1779 termList quotfirst, quotcursor;
1780 termList cursor;
1781 CanonicalForm cquot, crem;
1782 bool divideok = true;
1783
1784 cursor = firstTerm;
1785 quotcursor = quotfirst = new term;
1786
1787 while ( cursor && divideok )
1788 {
1789 divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail );
1790 if (fail)
1791 {
1792 freeTermList (quotfirst);
1793 return false;
1794 }
1795 divideok = divideok && crem.isZero();
1796 if ( divideok )
1797 {
1798 if ( ! cquot.isZero() )
1799 {
1800 quotcursor->next = new term( 0, cquot, cursor->exp );
1801 quotcursor = quotcursor->next;
1802 }
1803 cursor = cursor->next;
1804 }
1805 }
1806 quotcursor->next = 0;
1807 if ( divideok )
1808 {
1809 cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1810 if ( quotfirst )
1811 if ( quotfirst->exp == 0 )
1812 {
1813 quot = quotfirst->coeff.getval();
1814 delete quotfirst;
1815 }
1816 else
1817 quot = new InternalPoly( quotfirst, quotcursor, var );
1818 else
1819 quot = CFFactory::basic( 0 );
1820 rem = CFFactory::basic( 0 );
1821 }
1822 else
1823 {
1824 freeTermList( quotfirst );
1825 }
1826 return divideok;
1827}
1828
1829// static functions
1830
1832InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
1833{
1834 if ( UNLIKELY(aTermList == 0) )
1835 return 0;
1836 else if ( negate )
1837 {
1838 termList sourceCursor = aTermList;
1839 termList dummy = new term;
1840 termList targetCursor = dummy;
1841
1842 while ( LIKELY(sourceCursor) )
1843 {
1844 targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1845 targetCursor = targetCursor->next;
1846 sourceCursor = sourceCursor->next;
1847 }
1848 targetCursor->next = 0;
1849 theLastTerm = targetCursor;
1850 targetCursor = dummy->next;
1851 delete dummy;
1852 return targetCursor;
1853 }
1854 else
1855 {
1856 termList sourceCursor = aTermList;
1857 termList dummy = new term;
1858 termList targetCursor = dummy;
1859
1860 while ( LIKELY(sourceCursor) )
1861 {
1862 targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1863 targetCursor = targetCursor->next;
1864 sourceCursor = sourceCursor->next;
1865 }
1866 targetCursor->next = 0;
1867 theLastTerm = targetCursor;
1868 targetCursor = dummy->next;
1869 delete dummy;
1870 return targetCursor;
1871 }
1872}
1873
1876{
1877 if ( aTermList == 0 )
1878 return 0;
1879 else
1880 {
1881 termList sourceCursor = aTermList;
1882 termList dummy = new term;
1883 termList targetCursor = dummy;
1884
1885 while ( sourceCursor )
1886 {
1887 targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1888 targetCursor = targetCursor->next;
1889 sourceCursor = sourceCursor->next;
1890 }
1891 targetCursor->next = 0;
1892 theLastTerm = targetCursor;
1893 targetCursor = dummy->next;
1894 delete dummy;
1895 return targetCursor;
1896 }
1897}
1898
1899void
1901{
1902 termList cursor = aTermList;
1903
1904 while ( LIKELY(cursor) )
1905 {
1906 cursor = cursor->next;
1907 delete aTermList;
1908 aTermList = cursor;
1909 }
1910}
1911
1912void
1914{
1915 termList cursor = terms;
1916 while ( LIKELY(cursor) )
1917 {
1918 cursor->coeff = -cursor->coeff;
1919 cursor = cursor->next;
1920 }
1921}
1922
1925{
1926 termList theCursor = theList;
1927 termList aCursor = aList;
1928 termList predCursor = 0;
1929
1930 if (negate)
1931 while ( theCursor && aCursor )
1932 {
1933 if ( theCursor->exp == aCursor->exp )
1934 {
1935 theCursor->coeff -= aCursor->coeff;
1936 if ( theCursor->coeff.isZero() )
1937 {
1938 if ( predCursor )
1939 {
1940 predCursor->next = theCursor->next;
1941 delete theCursor;
1942 theCursor = predCursor->next;
1943 }
1944 else
1945 {
1946 theList = theList->next;
1947 delete theCursor;
1948 theCursor = theList;
1949 }
1950 }
1951 else
1952 {
1953 predCursor = theCursor;
1954 theCursor = theCursor->next;
1955 }
1956 aCursor = aCursor->next;
1957 }
1958 else if ( theCursor->exp < aCursor->exp )
1959 {
1960 if ( predCursor )
1961 {
1962 predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1963 predCursor = predCursor->next;
1964 }
1965 else
1966 {
1967 theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1968 predCursor = theList;
1969 }
1970 aCursor = aCursor->next;
1971 }
1972 else
1973 {
1974 predCursor = theCursor;
1975 theCursor = theCursor->next;
1976 }
1977 }
1978 else
1979 while ( theCursor && aCursor )
1980 {
1981 if ( theCursor->exp == aCursor->exp )
1982 {
1983 theCursor->coeff += aCursor->coeff;
1984 if ( theCursor->coeff.isZero() )
1985 {
1986 if ( predCursor )
1987 {
1988 predCursor->next = theCursor->next;
1989 delete theCursor;
1990 theCursor = predCursor->next;
1991 }
1992 else
1993 {
1994 theList = theList->next;
1995 delete theCursor;
1996 theCursor = theList;
1997 }
1998 }
1999 else
2000 {
2001 predCursor = theCursor;
2002 theCursor = theCursor->next;
2003 }
2004 aCursor = aCursor->next;
2005 }
2006 else if ( theCursor->exp < aCursor->exp )
2007 {
2008 if ( predCursor )
2009 {
2010 predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
2011 predCursor = predCursor->next;
2012 }
2013 else
2014 {
2015 theList = new term( theCursor, aCursor->coeff, aCursor->exp );
2016 predCursor = theList;
2017 }
2018 aCursor = aCursor->next;
2019 }
2020 else
2021 {
2022 predCursor = theCursor;
2023 theCursor = theCursor->next;
2024 }
2025 }
2026 if ( aCursor )
2027 {
2028 if ( predCursor )
2029 predCursor->next = copyTermList( aCursor, lastTerm, negate );
2030 else
2031 theList = copyTermList( aCursor, lastTerm, negate );
2032 }
2033 else if ( ! theCursor )
2034 lastTerm = predCursor;
2035
2036 return theList;
2037}
2038
2039void
2041{
2042 while ( LIKELY(theCursor) )
2043 {
2044 theCursor->coeff *= coeff;
2045 theCursor->exp += exp;
2046 theCursor = theCursor->next;
2047 }
2048}
2049
2052{
2053 termList theCursor = firstTerm;
2054 lastTerm = 0;
2055 termList dummy;
2056
2057 while ( LIKELY(theCursor) )
2058 {
2059 theCursor->coeff /= coeff;
2060 if ( theCursor->coeff.isZero() )
2061 {
2062 if ( theCursor == firstTerm )
2063 firstTerm = theCursor->next;
2064 else
2065 lastTerm->next = theCursor->next;
2066 dummy = theCursor;
2067 theCursor = theCursor->next;
2068 delete dummy;
2069 }
2070 else
2071 {
2072 lastTerm = theCursor;
2073 theCursor = theCursor->next;
2074 }
2075 }
2076 return firstTerm;
2077}
2078
2081{
2082 termList theCursor = firstTerm;
2083 lastTerm = 0;
2084 termList dummy;
2085
2086 while ( LIKELY(theCursor) )
2087 {
2088 theCursor->coeff.div( coeff );
2089 if ( theCursor->coeff.isZero() )
2090 {
2091 if ( theCursor == firstTerm )
2092 firstTerm = theCursor->next;
2093 else
2094 lastTerm->next = theCursor->next;
2095 dummy = theCursor;
2096 theCursor = theCursor->next;
2097 delete dummy;
2098 }
2099 else
2100 {
2101 lastTerm = theCursor;
2102 theCursor = theCursor->next;
2103 }
2104 }
2105 return firstTerm;
2106}
2107
2110{
2111 termList theCursor = firstTerm;
2112 lastTerm = 0;
2113 termList dummy;
2114
2115 while ( theCursor )
2116 {
2117 theCursor->coeff.tryDiv( coeff, M, fail );
2118 if (fail)
2119 return 0;
2120 if ( theCursor->coeff.isZero() )
2121 {
2122 if ( theCursor == firstTerm )
2123 firstTerm = theCursor->next;
2124 else
2125 lastTerm->next = theCursor->next;
2126 dummy = theCursor;
2127 theCursor = theCursor->next;
2128 delete dummy;
2129 }
2130 else
2131 {
2132 lastTerm = theCursor;
2133 theCursor = theCursor->next;
2134 }
2135 }
2136 return firstTerm;
2137}
2138
2141{
2142 termList theCursor = firstTerm;
2143 lastTerm = 0;
2144 termList dummy;
2145
2146 while ( theCursor )
2147 {
2148 theCursor->coeff.mod( coeff );
2149 if ( theCursor->coeff.isZero() )
2150 {
2151 if ( theCursor == firstTerm )
2152 firstTerm = theCursor->next;
2153 else
2154 lastTerm->next = theCursor->next;
2155 dummy = theCursor;
2156 theCursor = theCursor-> next;
2157 delete dummy;
2158 }
2159 else
2160 {
2161 lastTerm = theCursor;
2162 theCursor = theCursor->next;
2163 }
2164 }
2165 return firstTerm;
2166}
2167
2168void
2170{
2171 if ( last )
2172 {
2173 last->next = new term( 0, coeff, exp );
2174 last = last->next;
2175 }
2176 else
2177 {
2178 first = new term( 0, coeff, exp );
2179 last = first;
2180 }
2181}
2182
2184InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
2185{
2186 termList theCursor = theList;
2187 termList aCursor = aList;
2188 termList predCursor = 0;
2190
2191 if ( negate )
2192 coeff = -c;
2193 else
2194 coeff = c;
2195
2196 while ( theCursor && aCursor )
2197 {
2198 if ( theCursor->exp == aCursor->exp + exp )
2199 {
2200 theCursor->coeff += aCursor->coeff * coeff;
2201 if(UNLIKELY(( theCursor->coeff.isZero() )))
2202 {
2203 if ( predCursor )
2204 {
2205 predCursor->next = theCursor->next;
2206 delete theCursor;
2207 theCursor = predCursor->next;
2208 }
2209 else
2210 {
2211 theList = theList->next;
2212 delete theCursor;
2213 theCursor = theList;
2214 }
2215 }
2216 else
2217 {
2218 predCursor = theCursor;
2219 theCursor = theCursor->next;
2220 }
2221 aCursor = aCursor->next;
2222 }
2223 else if ( theCursor->exp < aCursor->exp + exp )
2224 {
2225 if ( predCursor )
2226 {
2227 predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
2228 predCursor = predCursor->next;
2229 }
2230 else
2231 {
2232 theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
2233 predCursor = theList;
2234 }
2235 aCursor = aCursor->next;
2236 }
2237 else
2238 {
2239 predCursor = theCursor;
2240 theCursor = theCursor->next;
2241 }
2242 }
2243 if ( aCursor )
2244 {
2245 if ( predCursor )
2246 {
2247 predCursor->next = copyTermList( aCursor, lastTerm );
2248 predCursor = predCursor->next;
2249 }
2250 else
2251 {
2252 theList = copyTermList( aCursor, lastTerm );
2253 predCursor = theList;
2254 }
2255 while ( predCursor )
2256 {
2257 predCursor->exp += exp;
2258 predCursor->coeff *= coeff;
2259 predCursor = predCursor->next;
2260 }
2261 }
2262 else if ( ! theCursor )
2263 lastTerm = predCursor;
2264 return theList;
2265}
2266
2269{
2270 CanonicalForm coeff = CanonicalForm (1)/redterms->coeff;
2271 CanonicalForm newcoeff;
2272 int newexp;
2273 int exp = redterms->exp;
2274 termList dummy;
2275 while ( first && ( first->exp >= exp ) )
2276 {
2277 newcoeff = first->coeff * coeff;
2278 newexp = first->exp - exp;
2279 dummy = first;
2280 first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
2281 delete dummy;
2282 }
2283 return first;
2284}
2285
#define UNLIKELY(X)
Definition auxiliary.h:405
#define LIKELY(X)
Definition auxiliary.h:404
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
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int is_imm(const InternalCF *const ptr)
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:4090
g
Definition cfModGcd.cc:4098
CanonicalForm test
Definition cfModGcd.cc:4104
CanonicalForm b
Definition cfModGcd.cc:4111
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
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.
term * termList
Definition cf_iter.h:36
static InternalCF * basic(int value)
Definition cf_factory.cc:61
factory's main class
CF_NO_INLINE bool isZero() const
int sign() const
int CanonicalForm::sign () const
CanonicalForm deepCopy() 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 &)
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
InternalCF * copyObject()
Definition int_cf.h:62
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
InternalCF()
Definition int_cf.h:55
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
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:56
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:2051
int taildegree()
Definition int_poly.cc:153
static termList addTermList(termList, termList, termList &, bool negate)
Definition int_poly.cc:1924
InternalCF * mulcoeff(InternalCF *)
Definition int_poly.cc:1183
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:2268
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:1900
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:1477
static const omBin InternalPoly_bin
Definition int_poly.h:159
static void mulTermList(termList, const CanonicalForm &, const int)
Definition int_poly.cc:2040
bool isUnivariate() const
Definition int_poly.cc:84
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition int_poly.cc:1654
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:1305
InternalCF * modulocoeff(InternalCF *, bool)
Definition int_poly.cc:1576
InternalCF * subsame(InternalCF *)
Definition int_poly.cc:326
termList firstTerm
Definition int_poly.h:73
InternalCF * divcoeff(InternalCF *, bool)
Definition int_poly.cc:1401
InternalCF * modcoeff(InternalCF *, bool)
Definition int_poly.cc:1590
bool inExtension() const
Definition int_poly.h:110
InternalCF * modulosame(InternalCF *)
Definition int_poly.cc:687
static void negateTermList(termList)
Definition int_poly.cc:1913
static termList tryDivTermList(termList, const CanonicalForm &, termList &, const CanonicalForm &, bool &)
Definition int_poly.cc:2109
static termList mulAddTermList(termList theList, termList aList, const CanonicalForm &c, const int exp, termList &lastTerm, bool negate)
Definition int_poly.cc:2184
bool tryDivremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
Definition int_poly.cc:1757
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:1691
CanonicalForm coeff(int i)
CanonicalForm InternalPoly::coeff ( int i )
Definition int_poly.cc:162
InternalCF * dividecoeff(InternalCF *, bool)
Definition int_poly.cc:1219
int comparecoeff(InternalCF *)
comparecoeff() always returns 1 since CO is defined to be larger than anything which is a coefficient...
Definition int_poly.cc:1034
CanonicalForm tailcoeff()
CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
Definition int_poly.cc:147
static termList deepCopyTermList(termList, termList &)
Definition int_poly.cc:1875
InternalCF * divsame(InternalCF *)
Definition int_poly.cc:498
InternalCF * addcoeff(InternalCF *)
Definition int_poly.cc:1040
InternalCF * subcoeff(InternalCF *, bool)
Definition int_poly.cc:1097
InternalPoly(termList, termList, const Variable &)
Definition int_poly.cc:46
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:2140
static termList copyTermList(termList, termList &, bool negate=false)
Definition int_poly.cc:1832
static void appendTermList(termList &, termList &, const CanonicalForm &, const int)
Definition int_poly.cc:2169
CanonicalForm Lc()
Definition int_poly.cc:129
static termList divTermList(termList, const CanonicalForm &, termList &)
Definition int_poly.cc:2080
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:127
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:1137
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.
#define OSTREAM
Definition int_poly.h:17
term * termList
Definition int_poly.h:60
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)
#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