source: git/factory/int_poly.cc @ 3c0e63d

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