source: git/factory/int_poly.cc @ ba5e9e

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