source: git/factory/int_poly.cc @ 650f2d8

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