source: git/factory/int_poly.cc @ 8d1432e

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