source: git/factory/int_poly.cc @ 4a7a45

spielwiese
Last change on this file since 4a7a45 was 84bac9, checked in by Hans Schoenemann <hannes@…>, 6 years ago
opt: conversion to factory
  • Property mode set to 100644
File size: 58.0 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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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(0L);
388            }
389            else
390            {
391                decRefCount();
392                return CFFactory::basic(0L);
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(0L);
451            }
452            else
453            {
454                decRefCount();
455                return CFFactory::basic(0L);
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( 0L );
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( 0L );
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( 0L );
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 (0L);
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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( 0L );
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 (0L);
949                  delete first;
950                }
951                else
952                  rem = new InternalPoly( first, last, var );
953            }
954        else
955            rem = CFFactory::basic( 0L );
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( 0L );
1190        }
1191        else
1192        {
1193            decRefCount();
1194            return CFFactory::basic( 0L );
1195        }
1196    }
1197    else  if ( c.isOne() )
1198        return this;
1199    else
1200    {
1201        if ( getRefCount() <= 1 )
1202        {
1203            mulTermList( firstTerm, c, 0L );
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( 0L );
1252        }
1253        else
1254        {
1255            decRefCount();
1256            return CFFactory::basic( 0L );
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( 0L );
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( 0L );
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 ( 0L ) 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( 0L );
1346        }
1347        else
1348        {
1349            decRefCount();
1350            return CFFactory::basic( 0L );
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( 0L );
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( 0L );
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( 0L );
1424        }
1425        else
1426        {
1427            decRefCount();
1428            return CFFactory::basic( 0L );
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( 0L );
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( 0L );
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( 0L );
1508        }
1509        else
1510        {
1511            decRefCount();
1512            return CFFactory::basic( 0L );
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 (0L);
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( 0L );
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 (0L);
1550            }
1551            if (fail)
1552            {
1553              delete first;
1554              return CFFactory::basic (0L);
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( 0L );
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( 0L );
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( 0L );
1603        }
1604        else
1605        {
1606            decRefCount();
1607            return CFFactory::basic( 0L );
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( 0L );
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( 0L );
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( 0L );
1659    }
1660    else  if ( invert )
1661    {
1662        if ( is_imm( cc ) )
1663            rem = cc;
1664        else
1665            rem = cc->copyObject();
1666        quot = CFFactory::basic( 0L );
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( 0L );
1684        rem = CFFactory::basic( 0L );
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( 0L );
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( 0L );
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( 0L );
1745        rem = CFFactory::basic( 0L );
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( 0L );
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( 0L );
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( 0L );
1818        rem = CFFactory::basic( 0L );
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 ( 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 ( 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 ( 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 ( 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 ( 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    while ( theCursor && aCursor )
1929    {
1930        if ( theCursor->exp == aCursor->exp )
1931        {
1932            if ( negate )
1933                theCursor->coeff -= aCursor->coeff;
1934            else
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 ( negate )
1961                if ( predCursor )
1962                {
1963                    predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1964                    predCursor = predCursor->next;
1965                }
1966                else
1967                {
1968                    theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1969                    predCursor = theList;
1970                }
1971            else
1972                if ( predCursor )
1973                {
1974                    predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1975                    predCursor = predCursor->next;
1976                }
1977                else
1978                {
1979                    theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1980                    predCursor = theList;
1981                }
1982            aCursor = aCursor->next;
1983        }
1984        else
1985        {
1986            predCursor = theCursor;
1987            theCursor = theCursor->next;
1988        }
1989    }
1990    if ( aCursor )
1991    {
1992        if ( predCursor )
1993            predCursor->next = copyTermList( aCursor, lastTerm, negate );
1994        else
1995            theList = copyTermList( aCursor, lastTerm, negate );
1996    }
1997    else if ( ! theCursor )
1998        lastTerm = predCursor;
1999
2000    return theList;
2001}
2002
2003void
2004InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
2005{
2006    while ( theCursor )
2007    {
2008        theCursor->coeff *= coeff;
2009        theCursor->exp += exp;
2010        theCursor = theCursor->next;
2011    }
2012}
2013
2014termList
2015InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
2016{
2017    termList theCursor = firstTerm;
2018    lastTerm = 0;
2019    termList dummy;
2020
2021    while ( theCursor )
2022    {
2023        theCursor->coeff /= coeff;
2024        if ( theCursor->coeff.isZero() )
2025        {
2026            if ( theCursor == firstTerm )
2027                firstTerm = theCursor->next;
2028            else
2029                lastTerm->next = theCursor->next;
2030            dummy = theCursor;
2031            theCursor = theCursor->next;
2032            delete dummy;
2033        }
2034        else
2035        {
2036            lastTerm = theCursor;
2037            theCursor = theCursor->next;
2038        }
2039    }
2040    return firstTerm;
2041}
2042
2043termList
2044InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
2045{
2046    termList theCursor = firstTerm;
2047    lastTerm = 0;
2048    termList dummy;
2049
2050    while ( theCursor )
2051    {
2052        theCursor->coeff.div( coeff );
2053        if ( theCursor->coeff.isZero() )
2054        {
2055            if ( theCursor == firstTerm )
2056                firstTerm = theCursor->next;
2057            else
2058                lastTerm->next = theCursor->next;
2059            dummy = theCursor;
2060            theCursor = theCursor->next;
2061            delete dummy;
2062        }
2063        else
2064        {
2065            lastTerm = theCursor;
2066            theCursor = theCursor->next;
2067        }
2068    }
2069    return firstTerm;
2070}
2071
2072termList
2073InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail )
2074{
2075    termList theCursor = firstTerm;
2076    lastTerm = 0;
2077    termList dummy;
2078
2079    while ( theCursor )
2080    {
2081        theCursor->coeff.tryDiv( coeff, M, fail );
2082        if (fail)
2083          return 0;
2084        if ( theCursor->coeff.isZero() )
2085        {
2086            if ( theCursor == firstTerm )
2087                firstTerm = theCursor->next;
2088            else
2089                lastTerm->next = theCursor->next;
2090            dummy = theCursor;
2091            theCursor = theCursor->next;
2092            delete dummy;
2093        }
2094        else
2095        {
2096            lastTerm = theCursor;
2097            theCursor = theCursor->next;
2098        }
2099    }
2100    return firstTerm;
2101}
2102
2103termList
2104InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
2105{
2106    termList theCursor = firstTerm;
2107    lastTerm = 0;
2108    termList dummy;
2109
2110    while ( theCursor )
2111    {
2112        theCursor->coeff.mod( coeff );
2113        if ( theCursor->coeff.isZero() )
2114        {
2115            if ( theCursor == firstTerm )
2116                firstTerm = theCursor->next;
2117            else
2118                lastTerm->next = theCursor->next;
2119            dummy = theCursor;
2120            theCursor = theCursor-> next;
2121            delete dummy;
2122        }
2123        else
2124        {
2125            lastTerm = theCursor;
2126            theCursor = theCursor->next;
2127        }
2128    }
2129    return firstTerm;
2130}
2131
2132void
2133InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
2134{
2135    if ( last )
2136    {
2137        last->next = new term( 0, coeff, exp );
2138        last = last->next;
2139    }
2140    else
2141    {
2142        first = new term( 0, coeff, exp );
2143        last = first;
2144    }
2145}
2146
2147termList
2148InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
2149{
2150    termList theCursor = theList;
2151    termList aCursor = aList;
2152    termList predCursor = 0;
2153    CanonicalForm coeff;
2154
2155    if ( negate )
2156        coeff = -c;
2157    else
2158        coeff = c;
2159
2160    while ( theCursor && aCursor )
2161    {
2162        if ( theCursor->exp == aCursor->exp + exp )
2163        {
2164            theCursor->coeff += aCursor->coeff * coeff;
2165            if(UNLIKELY(( theCursor->coeff.isZero() )))
2166            {
2167                if ( predCursor )
2168                {
2169                    predCursor->next = theCursor->next;
2170                    delete theCursor;
2171                    theCursor = predCursor->next;
2172                }
2173                else
2174                {
2175                    theList = theList->next;
2176                    delete theCursor;
2177                    theCursor = theList;
2178                }
2179            }
2180            else
2181            {
2182                predCursor = theCursor;
2183                theCursor = theCursor->next;
2184            }
2185            aCursor = aCursor->next;
2186        }
2187        else if ( theCursor->exp < aCursor->exp + exp )
2188        {
2189            if ( predCursor )
2190            {
2191                predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
2192                predCursor = predCursor->next;
2193            }
2194            else
2195            {
2196                theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
2197                predCursor = theList;
2198            }
2199            aCursor = aCursor->next;
2200        }
2201        else
2202        {
2203            predCursor = theCursor;
2204            theCursor = theCursor->next;
2205        }
2206    }
2207    if ( aCursor )
2208    {
2209        if ( predCursor )
2210        {
2211            predCursor->next = copyTermList( aCursor, lastTerm );
2212            predCursor = predCursor->next;
2213        }
2214        else
2215        {
2216            theList = copyTermList( aCursor, lastTerm );
2217            predCursor = theList;
2218        }
2219        while ( predCursor )
2220        {
2221            predCursor->exp += exp;
2222            predCursor->coeff *= coeff;
2223            predCursor = predCursor->next;
2224        }
2225    }
2226    else if ( ! theCursor )
2227        lastTerm = predCursor;
2228    return theList;
2229}
2230
2231termList
2232InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
2233{
2234    CanonicalForm coeff = CanonicalForm (1)/redterms->coeff;
2235    CanonicalForm newcoeff;
2236    int newexp;
2237    int exp = redterms->exp;
2238    termList dummy;
2239    while ( first && ( first->exp >= exp ) )
2240    {
2241        newcoeff = first->coeff * coeff;
2242        newexp = first->exp - exp;
2243        dummy = first;
2244        first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
2245        delete dummy;
2246    }
2247    return first;
2248}
2249
Note: See TracBrowser for help on using the repository browser.