source: git/factory/int_poly.cc @ ef4ae2

spielwiese
Last change on this file since ef4ae2 was ef4ae2, checked in by Hans Schoenemann <hannes@…>, 3 years ago
opt: factory (mpz_init, is_imm, moved tests out of loops(addTermList) etc
  • Property mode set to 100644
File size: 58.8 KB
Line 
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));
43const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly));
44#endif
45
46InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
47{
48    firstTerm = first;
49    lastTerm = last;
50    var = v;
51}
52
53InternalPoly::InternalPoly()
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 );
62    lastTerm = firstTerm;
63}
64
65InternalPoly::InternalPoly( const InternalPoly& ):InternalCF()
66{
67    ASSERT( 0, "ups there is something wrong in your code" );
68}
69
70InternalPoly::~InternalPoly()
71{
72    freeTermList( firstTerm );
73}
74
75InternalCF*
76InternalPoly::deepCopyObject() const
77{
78    termList first, last;
79    first = deepCopyTermList( firstTerm, last );
80    return new InternalPoly( first, last, var );
81}
82
83bool
84InternalPoly::isUnivariate() const
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
100InternalPoly::degree ()
101{
102    return firstTerm->exp;
103}
104
105
106/** int InternalPoly::sign () const
107 * @sa CanonicalForm::sign()
108**/
109int
110InternalPoly::sign () const
111{
112    return firstTerm->coeff.sign();
113}
114
115
116/**
117  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::Lc (), InternalPoly::LC ()
118**/
119CanonicalForm
120InternalPoly::lc ()
121{
122    return firstTerm->coeff.lc();
123}
124
125/**
126  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::LC ()
127**/
128CanonicalForm
129InternalPoly::Lc ()
130{
131    return firstTerm->coeff.Lc();
132}
133
134/**
135  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::Lc ()
136**/
137CanonicalForm
138InternalPoly::LC ()
139{
140    return firstTerm->coeff;
141}
142
143/** CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
144 * @sa CanonicalForm::tailcoeff(), taildegree()
145**/
146CanonicalForm
147InternalPoly::tailcoeff ()
148{
149    return lastTerm->coeff;
150}
151
152int
153InternalPoly::taildegree ()
154{
155    return lastTerm->exp;
156}
157
158/** CanonicalForm InternalPoly::coeff ( int i )
159 * @sa CanonicalForm::operator []()
160**/
161CanonicalForm
162InternalPoly::coeff ( int i )
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**/
230InternalCF *
231InternalPoly::neg ()
232{
233    if ( getRefCount() <= 1 )
234    {
235        negateTermList( firstTerm );
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
246InternalCF*
247InternalPoly::invert()
248{
249    if ( inExtension() && getReduce( var ) )
250    {
251        setReduce( var, false );
252        CanonicalForm a( this->copyObject() );
253        CanonicalForm b = getMipo( var );
254        CanonicalForm u, v;
255        CanonicalForm g = extgcd( a, b, u, v );
256        setReduce( var, true );
257        return u.getval();
258    }
259    else
260        return CFFactory::basic( 0 );
261}
262
263InternalCF*
264InternalPoly::tryInvert ( const CanonicalForm& M, bool& fail)
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
285InternalCF*
286InternalPoly::addsame( InternalCF* aCoeff )
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();
309        termList last, first = copyTermList( firstTerm, last );
310        first = addTermList( first, aPoly->firstTerm, last, false );
311        if ( first && first->exp != 0 )
312            return new InternalPoly( first, last, var );
313        else  if ( first )
314        {
315            InternalCF * res = first->coeff.getval();
316            delete first;
317            return res;
318        }
319        else
320            return CFFactory::basic( 0 );
321
322    }
323}
324
325InternalCF*
326InternalPoly::subsame( InternalCF* aCoeff )
327{
328    InternalPoly * aPoly = (InternalPoly*)aCoeff;
329    if ( getRefCount() <= 1 )
330    {
331        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
332        if ( firstTerm && firstTerm->exp != 0 )
333            return this;
334        else  if ( firstTerm )
335        {
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();
349        termList last, first = copyTermList( firstTerm, last );
350        first = addTermList( first, aPoly->firstTerm, last, true );
351        if ( first && first->exp != 0 )
352            return new InternalPoly( first, last, var );
353        else  if ( first )
354        {
355            InternalCF * res = first->coeff.getval();
356            delete first;
357            return res;
358        }
359        else
360            return CFFactory::basic( 0 );
361
362    }
363}
364
365InternalCF*
366InternalPoly::mulsame( InternalCF* aCoeff )
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    {
415        freeTermList( firstTerm );
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
427InternalCF*
428InternalPoly::tryMulsame( InternalCF* aCoeff, const CanonicalForm& M)
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    {
478        freeTermList( firstTerm );
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
490InternalCF*
491InternalPoly::dividesame( InternalCF* aCoeff )
492{
493    return divsame( aCoeff );
494}
495
496
497InternalCF*
498InternalPoly::divsame( InternalCF* aCoeff )
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
583InternalCF*
584InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail )
585{
586    if ( inExtension() && !getReduce( var ) )
587    {
588        InternalCF * dummy = aCoeff->tryInvert(M, fail);
589        if (fail)
590          return CFFactory::basic( 0 );
591        if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M);
592        else dummy = dummy->tryMulsame( this, M);
593        if (fail)
594        {
595          if (getRefCount() <= 1)
596            delete this;
597          else
598            decRefCount();
599          return dummy;
600        }
601        if ( getRefCount() <= 1 )
602        {
603             delete this;
604             return dummy;
605        }
606        else
607        {
608            decRefCount();
609            return dummy;
610        }
611    }
612    InternalPoly *aPoly = (InternalPoly*)aCoeff;
613    termList dummy, first, last, resultfirst = 0, resultlast = 0;
614    CanonicalForm coeff, newcoeff;
615    int exp, newexp;
616    bool singleObject;
617
618    if ( getRefCount() <= 1 )
619    {
620        first = firstTerm; last = lastTerm; singleObject = true;
621    }
622    else
623    {
624        first = copyTermList( firstTerm, last ); singleObject = false;
625        decRefCount();
626    }
627    coeff = aPoly->firstTerm->coeff;
628    exp = aPoly->firstTerm->exp;
629    while (first && ( first->exp >= exp ) )
630    {
631        newcoeff= first->coeff.tryDiv (coeff, M, fail);
632        if (fail)
633        {
634          freeTermList (first);
635          return CFFactory::basic (0);
636        }
637        newcoeff= reduce (newcoeff, M);
638        newexp = first->exp - exp;
639        dummy = first;
640        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
641        delete dummy;
642        if (!newcoeff.isZero())
643          appendTermList( resultfirst, resultlast, newcoeff, newexp );
644    }
645    freeTermList( first );
646    if ( singleObject )
647    {
648        if ( resultfirst && resultfirst->exp != 0 )
649        {
650            firstTerm = resultfirst;
651            lastTerm = resultlast;
652            return this;
653        }
654        else  if ( resultfirst )
655        {
656            InternalCF * res = resultfirst->coeff.getval();
657            delete resultfirst;
658            firstTerm = 0;
659            delete this;
660            return res;
661        }
662        else
663        {
664            // this should not happen (evtl use assertion)
665            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
666            firstTerm = 0;
667            delete this;
668            return CFFactory::basic( 0 );
669        }
670    }
671    else
672    {
673        if ( resultfirst && resultfirst->exp != 0 )
674            return new InternalPoly( resultfirst, resultlast, var );
675        else  if ( resultfirst )
676        {
677            InternalCF * res = resultfirst->coeff.getval();
678            delete resultfirst;
679            return res;
680        }
681        else
682            return CFFactory::basic( 0 );
683    }
684}
685
686InternalCF*
687InternalPoly::modulosame( InternalCF* aCoeff )
688{
689    return modsame( aCoeff );
690}
691
692InternalCF*
693InternalPoly::modsame( InternalCF* aCoeff )
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
765InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
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
817InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
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
883InternalPoly::tryDivremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem, const CanonicalForm& M, bool& fail)
884{
885    if (inExtension() && !getReduce (var))
886    {
887       InternalCF * dummy = acoeff->tryInvert(M, fail);
888       if (fail)
889         return false;
890       quot = dummy->tryMulsame( this, M);
891       rem = CFFactory::basic( 0 );
892       if (fail)
893         return false;
894       return true;
895    }
896    InternalPoly *aPoly = (InternalPoly*)acoeff;
897    termList dummy, first, last, resultfirst = 0, resultlast = 0;
898    CanonicalForm coeff, newcoeff, dummycoeff;
899    int exp, newexp;
900    bool divideok = true;
901
902    first = copyTermList( firstTerm, last );
903
904    coeff = aPoly->firstTerm->coeff;
905    exp = aPoly->firstTerm->exp;
906    while (first && ( first->exp >= exp ) && divideok )
907    {
908        divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail );
909        if (fail)
910        {
911          freeTermList (first);
912          return false;
913        }
914        if ( divideok && dummycoeff.isZero() )
915        {
916            newexp = first->exp - exp;
917            dummy = first;
918            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
919            delete dummy;
920            if (!newcoeff.isZero())
921              appendTermList( resultfirst, resultlast, newcoeff, newexp );
922        }
923        else
924            divideok = false;
925    }
926    if ( divideok )
927    {
928        if ( resultfirst )
929            if ( resultfirst->exp == 0 )
930            {
931                quot = resultfirst->coeff.getval();
932                delete resultfirst;
933            }
934            else
935                quot = new InternalPoly( resultfirst, resultlast, var );
936        else
937            quot = CFFactory::basic( 0 );
938        if ( first )
939            if ( first->exp == 0 )
940            {
941                rem = first->coeff.getval();
942                delete first;
943            }
944            else
945            {
946                if (first->coeff.isZero())
947                {
948                  rem= CFFactory::basic (0);
949                  delete first;
950                }
951                else
952                  rem = new InternalPoly( first, last, var );
953            }
954        else
955            rem = CFFactory::basic( 0 );
956    }
957    else
958    {
959        freeTermList( resultfirst );
960        freeTermList( first );
961    }
962    return divideok;
963}
964
965/**
966 * comparesame(), comparecoeff() - compare with an
967 *   InternalPoly.
968 *
969 * comparesame() compares the coefficient vectors of f=CO and
970 * g=acoeff w.r.t to a lexicographic order in the following way:
971 * f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
972 * i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
973 * ii) g[i] occurs in g (i.e. is not equal to zero) and
974 *     f[i] does not occur in f or f[i] < g[i] if f[i] occurs
975 * where f[i] denotes the coefficient to the power x^i of f.
976 *
977 * As usual, comparesame() returns 1 if CO is larger than c, 0 if
978 * CO equals c, and -1 if CO is less than c.  However, this
979 * function is optimized to test on equality since this is its
980 * most important and frequent usage.
981 *
982 * See the respective `CanonicalForm'-methods for an explanation
983 * why we define such a strange (but total) ordering on
984 * polynomials.
985 *
986 * @sa CanonicalForm::operator <(), CanonicalForm::operator ==()
987 *
988**/
989int
990InternalPoly::comparesame ( InternalCF * acoeff )
991{
992    ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
993    InternalPoly* apoly = (InternalPoly*)acoeff;
994    // check on triviality
995    if ( this == apoly )
996        return 0;
997    else
998    {
999        termList cursor1 = firstTerm;
1000        termList cursor2 = apoly->firstTerm;
1001        for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
1002            // we test on inequality of coefficients at this
1003            // point instead of testing on "less than" at the
1004            // last `else' in the enclosed `if' statement since a
1005            // test on inequaltiy in general is cheaper
1006            if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) )
1007            {
1008                if ( cursor1->exp > cursor2->exp )
1009                    return 1;
1010                else  if ( cursor1->exp < cursor2->exp )
1011                    return -1;
1012                else  if ( cursor1->coeff > cursor2->coeff )
1013                    return 1;
1014                else
1015                    return -1;
1016             }
1017        // check trailing terms
1018        if ( cursor1 == cursor2 )
1019            return 0;
1020        else if ( cursor1 != 0 )
1021            return 1;
1022        else
1023            return -1;
1024    }
1025}
1026
1027/**
1028 * comparecoeff() always returns 1 since CO is defined to be
1029 * larger than anything which is a coefficient w.r.t. CO.
1030**/
1031int
1032InternalPoly::comparecoeff ( InternalCF * )
1033{
1034    return 1;
1035}
1036
1037InternalCF*
1038InternalPoly::addcoeff( InternalCF* cc )
1039{
1040    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1041    if ( c.isZero() )
1042        return this;
1043    else
1044    {
1045        if ( getRefCount() <= 1 )
1046        {
1047            if ( lastTerm->exp == 0 )
1048            {
1049                lastTerm->coeff += c;
1050                if ( lastTerm->coeff.isZero() )
1051                {
1052                    termList cursor = firstTerm;
1053                    while ( cursor->next != lastTerm )
1054                        cursor = cursor->next;
1055                    delete lastTerm;
1056                    cursor->next = 0;
1057                    lastTerm = cursor;
1058                }
1059            }
1060            else
1061            {
1062                lastTerm->next = new term( 0, c, 0 );
1063                lastTerm = lastTerm->next;
1064            }
1065            return this;
1066        }
1067        else
1068        {
1069            decRefCount();
1070            termList last, first = copyTermList( firstTerm, last, false );
1071            if ( last->exp == 0 )
1072            {
1073                last->coeff += c;
1074                if ( last->coeff.isZero() )
1075                {
1076                    termList cursor = first;
1077                    while ( cursor->next != last )
1078                        cursor = cursor->next;
1079                    delete last;
1080                    cursor->next = 0;
1081                    last = cursor;
1082                }
1083            }
1084            else
1085            {
1086                last->next = new term( 0, c, 0L );
1087                last = last->next;
1088            }
1089            return new InternalPoly( first, last, var );
1090        }
1091    }
1092}
1093
1094InternalCF*
1095InternalPoly::subcoeff( InternalCF* cc, bool negate )
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 )
1108                negateTermList( firstTerm );
1109            return this;
1110        }
1111    else
1112    {
1113        if ( getRefCount() <= 1 )
1114        {
1115            if ( lastTerm->exp == 0 )
1116            {
1117                if ( negate )
1118                {
1119                    negateTermList( firstTerm );
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                {
1138                    negateTermList( firstTerm );
1139                    lastTerm->next = new term( 0, c, 0 );
1140                }
1141                else
1142                    lastTerm->next = new term( 0, -c, 0 );
1143                lastTerm = lastTerm->next;
1144            }
1145            return this;
1146        }
1147        else
1148        {
1149            decRefCount();
1150            termList last, first = copyTermList( firstTerm, last, negate );
1151            if ( last->exp == 0 )
1152            {
1153                if ( negate )
1154                    last->coeff += c;
1155                else
1156                    last->coeff -= c;
1157                if ( last->coeff.isZero() )
1158                {
1159                    termList cursor = first;
1160                    while ( cursor->next != last )
1161                        cursor = cursor->next;
1162                    delete last;
1163                    cursor->next = 0;
1164                    last = cursor;
1165                }
1166            }
1167            else
1168            {
1169                if ( negate )
1170                    last->next = new term( 0, c, 0 );
1171                else
1172                    last->next = new term( 0, -c, 0 );
1173                last = last->next;
1174            }
1175            return new InternalPoly( first, last, var );
1176        }
1177    }
1178}
1179
1180InternalCF*
1181InternalPoly::mulcoeff( InternalCF* cc )
1182{
1183    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1184    if ( c.isZero() )
1185    {
1186        if ( getRefCount() <= 1 )
1187        {
1188            delete this;
1189            return CFFactory::basic( 0 );
1190        }
1191        else
1192        {
1193            decRefCount();
1194            return CFFactory::basic( 0 );
1195        }
1196    }
1197    else  if ( c.isOne() )
1198        return this;
1199    else
1200    {
1201        if ( getRefCount() <= 1 )
1202        {
1203            mulTermList( firstTerm, c, 0 );
1204            return this;
1205        }
1206        else
1207        {
1208            decRefCount();
1209            termList last, first = copyTermList( firstTerm, last );
1210            mulTermList( first, c, 0 );
1211            return new InternalPoly( first, last, var );
1212        }
1213    }
1214}
1215
1216InternalCF*
1217InternalPoly::dividecoeff( InternalCF* cc, bool invert )
1218{
1219    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1220    if ( inExtension() && getReduce( var ) && invert )
1221    {
1222        InternalCF * dummy;
1223        dummy = this->invert();
1224        if (is_imm(dummy))
1225        {
1226          if (is_imm(cc))
1227          {
1228            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
1229            dummy=d;
1230          }
1231          else
1232            dummy=cc->mulcoeff(dummy);
1233        }
1234        else dummy = dummy->mulcoeff( cc );
1235        if ( getRefCount() <= 1 )
1236        {
1237            delete this;
1238            return dummy;
1239        }
1240        else
1241        {
1242            decRefCount();
1243            return dummy;
1244        }
1245    }
1246    if ( invert )
1247    {
1248        if ( getRefCount() <= 1 )
1249        {
1250            delete this;
1251            return CFFactory::basic( 0 );
1252        }
1253        else
1254        {
1255            decRefCount();
1256            return CFFactory::basic( 0 );
1257        }
1258    }
1259    if ( c.isOne() )
1260        return this;
1261    else
1262    {
1263        if ( getRefCount() <= 1 )
1264        {
1265            firstTerm = divideTermList( firstTerm, c, lastTerm );
1266            if ( firstTerm && firstTerm->exp != 0 )
1267                return this;
1268            else  if ( firstTerm )
1269            {
1270                InternalCF * res = firstTerm->coeff.getval();
1271                delete this;
1272                return res;
1273            }
1274            else
1275            {
1276                delete this;
1277                return CFFactory::basic( 0 );
1278            }
1279        }
1280        else
1281        {
1282            decRefCount();
1283            termList last, first = copyTermList( firstTerm, last );
1284            first = divideTermList( first, c, last );
1285            if ( first && first->exp != 0 )
1286                return new InternalPoly( first, last, var );
1287            else  if ( first )
1288            {
1289                InternalCF * res = first->coeff.getval();
1290                delete first;
1291                return res;
1292            }
1293            else
1294            {
1295                delete first;
1296                return CFFactory::basic( 0 );
1297            }
1298        }
1299    }
1300}
1301
1302InternalCF*
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          {
1322            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
1323            dummy=d;
1324          }
1325          else
1326            dummy=cc->mulcoeff(dummy);
1327        }
1328        else dummy = dummy->mulcoeff( cc );
1329        if ( getRefCount() <= 1 )
1330        {
1331            delete this;
1332            return dummy;
1333        }
1334        else
1335        {
1336            decRefCount();
1337            return dummy;
1338        }
1339    }
1340    if ( invert )
1341    {
1342        if ( getRefCount() <= 1 )
1343        {
1344            delete this;
1345            return CFFactory::basic( 0 );
1346        }
1347        else
1348        {
1349            decRefCount();
1350            return CFFactory::basic( 0 );
1351        }
1352    }
1353    if ( c.isOne() )
1354        return this;
1355    //one should never get here
1356    else
1357    {
1358        if ( getRefCount() <= 1 )
1359        {
1360            firstTerm = divideTermList( firstTerm, c, lastTerm );
1361            if ( firstTerm && firstTerm->exp != 0 )
1362                return this;
1363            else  if ( firstTerm )
1364            {
1365                InternalCF * res = firstTerm->coeff.getval();
1366                delete this;
1367                return res;
1368            }
1369            else
1370            {
1371                delete this;
1372                return CFFactory::basic( 0 );
1373            }
1374        }
1375        else
1376        {
1377            decRefCount();
1378            termList last, first = copyTermList( firstTerm, last );
1379            first = divideTermList( first, c, last );
1380            if ( first && first->exp != 0 )
1381                return new InternalPoly( first, last, var );
1382            else  if ( first )
1383            {
1384                InternalCF * res = first->coeff.getval();
1385                delete first;
1386                return res;
1387            }
1388            else
1389            {
1390                delete first;
1391                return CFFactory::basic( 0 );
1392            }
1393        }
1394    }
1395}
1396
1397
1398InternalCF*
1399InternalPoly::divcoeff( InternalCF* cc, bool invert )
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        {
1437            firstTerm = divTermList( firstTerm, c, lastTerm );
1438            if ( firstTerm && firstTerm->exp != 0 )
1439                return this;
1440            else  if ( firstTerm )
1441            {
1442                InternalCF * res = firstTerm->coeff.getval();
1443                delete this;
1444                return res;
1445            }
1446            else
1447            {
1448                delete this;
1449                return CFFactory::basic( 0 );
1450            }
1451        }
1452        else
1453        {
1454            decRefCount();
1455            termList last, first = copyTermList( firstTerm, last );
1456            first = divTermList( first, c, last );
1457            if ( first && first->exp != 0 )
1458                return new InternalPoly( first, last, var );
1459            else  if ( first )
1460            {
1461                InternalCF * res = first->coeff.getval();
1462                delete first;
1463                return res;
1464            }
1465            else
1466            {
1467                delete first;
1468                return CFFactory::basic( 0 );
1469            }
1470        }
1471    }
1472}
1473
1474InternalCF*
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        {
1521            firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
1522            if (fail)
1523            {
1524              delete this;
1525              return CFFactory::basic (0);
1526            }
1527            if ( firstTerm && firstTerm->exp != 0 )
1528                return this;
1529            else  if ( firstTerm )
1530            {
1531                InternalCF * res = firstTerm->coeff.getval();
1532                delete this;
1533                return res;
1534            }
1535            else
1536            {
1537                delete this;
1538                return CFFactory::basic( 0 );
1539            }
1540        }
1541        else
1542        {
1543            decRefCount();
1544            termList last, first = copyTermList( firstTerm, last );
1545            first = tryDivTermList( first, c, last, M, fail );
1546            if (fail)
1547            {
1548              delete this;
1549              return CFFactory::basic (0);
1550            }
1551            if (fail)
1552            {
1553              delete first;
1554              return CFFactory::basic (0);
1555            }
1556            if ( first && first->exp != 0 )
1557                return new InternalPoly( first, last, var );
1558            else  if ( first )
1559            {
1560                InternalCF * res = first->coeff.getval();
1561                delete first;
1562                return res;
1563            }
1564            else
1565            {
1566                delete first;
1567                return CFFactory::basic( 0 );
1568            }
1569        }
1570    }
1571}
1572
1573InternalCF*
1574InternalPoly::modulocoeff( InternalCF* cc, bool invert )
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
1587InternalCF*
1588InternalPoly::modcoeff( InternalCF* cc, bool invert )
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        {
1614            firstTerm = modTermList( firstTerm, c, lastTerm );
1615            if ( firstTerm && firstTerm->exp != 0 )
1616                return this;
1617            else  if ( firstTerm )
1618            {
1619                InternalCF * res = firstTerm->coeff.getval();
1620                delete this;
1621                return res;
1622            }
1623            else
1624            {
1625                delete this;
1626                return CFFactory::basic( 0 );
1627            }
1628        }
1629        else
1630        {
1631            decRefCount();
1632            termList last, first = copyTermList( firstTerm, last );
1633            first = modTermList( first, c, last );
1634            if ( first && first->exp != 0 )
1635                return new InternalPoly( first, last, var );
1636            else  if ( first )
1637            {
1638                InternalCF * res = first->coeff.getval();
1639                delete first;
1640                return res;
1641            }
1642            else
1643            {
1644                delete first;
1645                return CFFactory::basic( 0 );
1646            }
1647        }
1648    }
1649}
1650
1651void
1652InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
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
1689InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
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
1829termList
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
1872termList
1873InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
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
1898InternalPoly::freeTermList ( termList aTermList )
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
1911InternalPoly::negateTermList ( termList terms )
1912{
1913    termList cursor = terms;
1914    while ( LIKELY(cursor) )
1915    {
1916        cursor->coeff = -cursor->coeff;
1917        cursor = cursor->next;
1918    }
1919}
1920
1921termList
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
2048termList
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
2077termList
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
2106termList
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
2137termList
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
2167InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
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
2181termList
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;
2187    CanonicalForm coeff;
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
2265termList
2266InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
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
Note: See TracBrowser for help on using the repository browser.