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

spielwiese
Last change on this file since 4ccbc25 was 4ccbc25, checked in by Hans Schönemann <hannes@…>, 16 years ago
*hannes: format git-svn-id: file:///usr/local/Singular/svn/trunk@10799 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 42.8 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: int_poly.cc,v 1.21 2008-06-25 13:53:20 Singular Exp $ */
3
4#include <config.h>
5
6#ifndef NOSTREAMIO
7#include <string.h>
8#if defined(WINNT) && ! defined(__GNUC__)
9#include <strstrea.h>
10#else
11#if __GNUC__ < 3
12#include <strstream.h>
13#else
14#include <strstream>
15using namespace std;
16#endif
17#endif
18#endif /* NOSTREAMIO */
19
20#include "assert.h"
21
22#include "cf_defs.h"
23#include "cf_factory.h"
24#include "int_cf.h"
25#include "int_int.h"
26#include "int_poly.h"
27#include "canonicalform.h"
28#include "variable.h"
29#include "imm.h"
30
31#ifdef HAVE_OMALLOC
32const omBin term::term_bin = omGetSpecBin(sizeof(term));
33const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly));
34#endif
35
36InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
37{
38    firstTerm = first;
39    lastTerm = last;
40    var = v;
41}
42
43InternalPoly::InternalPoly()
44{
45    ASSERT( 0, "ups, why do you initialize an empty poly" );
46}
47
48InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
49{
50    var = v;
51    firstTerm = new term( 0, c, e );
52    lastTerm = firstTerm;
53}
54
55InternalPoly::InternalPoly( const InternalPoly& )
56{
57    ASSERT( 0, "ups there is something wrong in your code" );
58};
59
60InternalPoly::~InternalPoly()
61{
62    freeTermList( firstTerm );
63}
64
65InternalCF*
66InternalPoly::deepCopyObject() const
67{
68    termList first, last;
69    first = deepCopyTermList( firstTerm, last );
70    return new InternalPoly( first, last, var );
71}
72
73InternalCF*
74InternalPoly::genZero()
75{
76    return firstTerm->coeff.genZero().getval();
77}
78
79InternalCF*
80InternalPoly::genOne()
81{
82    return firstTerm->coeff.genOne().getval();
83}
84
85bool
86InternalPoly::isUnivariate() const
87{
88    termList cursor = firstTerm;
89    while ( cursor )
90    {
91        if ( ! cursor->coeff.inCoeffDomain() )
92            return false;
93        cursor = cursor->next;
94    }
95    return true;
96}
97
98//{{{ int InternalPoly::degree ()
99// docu: see CanonicalForm::sign ()
100int
101InternalPoly::degree ()
102{
103    return firstTerm->exp;
104}
105//}}}
106
107//{{{ int InternalPoly::sign () const
108// docu: see CanonicalForm::sign()
109int
110InternalPoly::sign () const
111{
112    return firstTerm->coeff.sign();
113}
114//}}}
115
116//{{{ CanonicalForm InternalPoly::lc (), Lc (), LC ()
117// docu: see CanonicalForm::lc(), Lc(), LC()
118CanonicalForm
119InternalPoly::lc ()
120{
121    return firstTerm->coeff.lc();
122}
123
124CanonicalForm
125InternalPoly::Lc ()
126{
127    return firstTerm->coeff.Lc();
128}
129
130CanonicalForm
131InternalPoly::LC ()
132{
133    return firstTerm->coeff;
134}
135//}}}
136
137//{{{ CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
138// docu: see CanonicalForm::tailcoeff(), taildegree()
139CanonicalForm
140InternalPoly::tailcoeff ()
141{
142    return lastTerm->coeff;
143}
144
145int
146InternalPoly::taildegree ()
147{
148    return lastTerm->exp;
149}
150//}}}
151
152//{{{ CanonicalForm InternalPoly::coeff ( int i )
153// docu: see CanonicalForm::operator []()
154CanonicalForm
155InternalPoly::coeff ( int i )
156{
157    termList theCursor = firstTerm;
158    while ( theCursor )
159    {
160        if ( theCursor->exp == i )
161            return theCursor->coeff;
162        else if ( theCursor->exp < i )
163            return CanonicalForm( 0 );
164        else
165            theCursor = theCursor->next;
166    }
167    return CanonicalForm( 0 );
168}
169//}}}
170
171#ifndef NOSTREAMIO
172void
173InternalPoly::print(OSTREAM &aStream, char * aString )
174{
175    if ( ! firstTerm )
176        aStream << 0 << aString;
177    else
178    {
179        char * theString;
180        termList theCursor = firstTerm;
181        while ( theCursor )
182        {
183            ostrstream theStream;
184            if ( theCursor->exp == 0 )
185                theCursor->coeff.print( aStream, aString );
186            else  if ( theCursor->coeff.isOne() )
187            {
188                aStream << var;
189                if ( theCursor->exp != 1 )
190                    aStream << '^' << theCursor->exp << aString;
191                else
192                    aStream << aString;
193            }
194            else  if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() )
195            {
196                aStream << '-' << var;
197                if ( theCursor->exp != 1 )
198                    aStream << '^' << theCursor->exp << aString;
199                else
200                    aStream << aString;
201            }
202            else
203            {
204                theStream << '*' << var;
205                if ( theCursor->exp != 1 )
206                    theStream << '^' << theCursor->exp << aString << ends;
207                else
208                    theStream << aString << ends; // results from error in GNU strstream
209                theString = theStream.str();
210                theCursor->coeff.print( aStream, theString );
211                theStream.freeze(0);//delete [] theString;
212            }
213            theCursor = theCursor->next;
214            if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
215                aStream << '+';
216        }
217    }
218}
219#endif /* NOSTREAMIO */
220
221//{{{ InternalCF * InternalPoly::neg ()
222// docu: see CanonicalForm::operator -()
223InternalCF *
224InternalPoly::neg ()
225{
226    if ( getRefCount() == 1 )
227    {
228        negateTermList( firstTerm );
229        return this;
230    }
231    else
232    {
233        decRefCount();
234        termList last, first = copyTermList( firstTerm, last, true );
235        return new InternalPoly( first, last, var );
236    }
237}
238//}}}
239
240InternalCF*
241InternalPoly::invert()
242{
243    if ( inExtension() && getReduce( var ) )
244    {
245        setReduce( var, false );
246        CanonicalForm a( this->copyObject() );
247        CanonicalForm b = getMipo( var );
248        CanonicalForm u, v;
249        CanonicalForm g = extgcd( a, b, u, v );
250        setReduce( var, true );
251        return u.getval();
252    }
253    else
254        return CFFactory::basic( 0 );
255}
256
257InternalCF*
258InternalPoly::addsame( InternalCF* aCoeff )
259{
260    InternalPoly * aPoly = (InternalPoly*)aCoeff;
261    if ( getRefCount() == 1 )
262    {
263        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
264        if ( firstTerm && firstTerm->exp != 0 )
265            return this;
266        else  if ( firstTerm )
267        {
268            InternalCF * res = firstTerm->coeff.getval();
269            delete this;
270            return res;
271        }
272        else
273        {
274            delete this;
275            return CFFactory::basic( 0 );
276        }
277    }
278    else
279    {
280        decRefCount();
281        termList last, first = copyTermList( firstTerm, last );
282        first = addTermList( first, aPoly->firstTerm, last, false );
283        if ( first && first->exp != 0 )
284            return new InternalPoly( first, last, var );
285        else  if ( first )
286        {
287            InternalCF * res = first->coeff.getval();
288            delete first;
289            return res;
290        }
291        else
292            return CFFactory::basic( 0 );
293
294    }
295}
296
297InternalCF*
298InternalPoly::subsame( InternalCF* aCoeff )
299{
300    InternalPoly * aPoly = (InternalPoly*)aCoeff;
301    if ( getRefCount() == 1 )
302    {
303        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
304        if ( firstTerm && firstTerm->exp != 0 )
305            return this;
306        else  if ( firstTerm )
307        {
308            InternalCF * res = firstTerm->coeff.getval();
309            delete this;
310            return res;
311        }
312        else
313        {
314            delete this;
315            return CFFactory::basic( 0 );
316        }
317    }
318    else
319    {
320        decRefCount();
321        termList last, first = copyTermList( firstTerm, last );
322        first = addTermList( first, aPoly->firstTerm, last, true );
323        if ( first && first->exp != 0 )
324            return new InternalPoly( first, last, var );
325        else  if ( first )
326        {
327            InternalCF * res = first->coeff.getval();
328            delete first;
329            return res;
330        }
331        else
332            return CFFactory::basic( 0 );
333
334    }
335}
336
337InternalCF*
338InternalPoly::mulsame( InternalCF* aCoeff )
339{
340    if (is_imm(aCoeff)) return mulcoeff(aCoeff);
341    InternalPoly *aPoly = (InternalPoly*)aCoeff;
342    termList resultFirst = 0, resultLast = 0;
343    termList theCursor = firstTerm;
344
345    while ( theCursor )
346    {
347        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
348                          theCursor->coeff, theCursor->exp, resultLast, false );
349        theCursor = theCursor->next;
350    }
351    if ( inExtension() && getReduce( var ) )
352    {
353        resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
354        if ( resultFirst == 0 )
355            if ( getRefCount() == 1 )
356            {
357                delete this;
358                return CFFactory::basic(0);
359            }
360            else
361            {
362                decRefCount();
363                return CFFactory::basic(0);
364            }
365        else  if ( resultFirst->exp == 0 )
366            if ( getRefCount() == 1 )
367            {
368                InternalCF * res = resultFirst->coeff.getval();
369                delete resultFirst;
370                delete this;
371                return res;
372            }
373            else
374            {
375                decRefCount();
376                InternalCF * res = resultFirst->coeff.getval();
377                delete resultFirst;
378                return res;
379            }
380    }
381    if ( getRefCount() == 1 )
382    {
383        freeTermList( firstTerm );
384        firstTerm = resultFirst;
385        lastTerm = resultLast;
386        return this;
387    }
388    else
389    {
390        decRefCount();
391        return new InternalPoly( resultFirst, resultLast, var );
392    }
393}
394
395InternalCF*
396InternalPoly::dividesame( InternalCF* aCoeff )
397{
398    return divsame( aCoeff );
399}
400
401
402InternalCF*
403InternalPoly::divsame( InternalCF* aCoeff )
404{
405    if ( inExtension() && getReduce( var ) )
406    {
407        InternalCF * dummy = aCoeff->invert();
408        if (is_imm(dummy)) dummy=this->mulsame(dummy);
409        else dummy = dummy->mulsame( this );
410        if ( getRefCount() == 1 )
411        {
412             delete this;
413             return dummy;
414        }
415        else
416        {
417            decRefCount();
418            return dummy;
419        }
420    }
421    InternalPoly *aPoly = (InternalPoly*)aCoeff;
422    termList dummy, first, last, resultfirst = 0, resultlast = 0;
423    CanonicalForm coeff, newcoeff;
424    int exp, newexp;
425    bool singleObject;
426
427    if ( getRefCount() == 1 )
428    {
429        first = firstTerm; last = lastTerm; singleObject = true;
430    }
431    else
432    {
433        first = copyTermList( firstTerm, last ); singleObject = false;
434        decRefCount();
435    }
436    coeff = aPoly->firstTerm->coeff;
437    exp = aPoly->firstTerm->exp;
438    while (first && ( first->exp >= exp ) )
439    {
440        newcoeff = first->coeff / coeff;
441        newexp = first->exp - exp;
442        dummy = first;
443        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
444        delete dummy;
445        appendTermList( resultfirst, resultlast, newcoeff, newexp );
446    }
447    freeTermList( first );
448    if ( singleObject )
449    {
450        if ( resultfirst && resultfirst->exp != 0 )
451        {
452            firstTerm = resultfirst;
453            lastTerm = resultlast;
454            return this;
455        }
456        else  if ( resultfirst )
457        {
458            InternalCF * res = resultfirst->coeff.getval();
459            delete resultfirst;
460            firstTerm = 0;
461            delete this;
462            return res;
463        }
464        else
465        {
466            // this should not happen (evtl use assertion)
467            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
468            firstTerm = 0;
469            delete this;
470            return CFFactory::basic( 0 );
471        }
472    }
473    else
474    {
475        if ( resultfirst && resultfirst->exp != 0 )
476            return new InternalPoly( resultfirst, resultlast, var );
477        else  if ( resultfirst )
478        {
479            InternalCF * res = resultfirst->coeff.getval();
480            delete resultfirst;
481            return res;
482        }
483        else
484            return CFFactory::basic( 0 );
485    }
486}
487
488InternalCF*
489InternalPoly::modulosame( InternalCF* aCoeff )
490{
491    return modsame( aCoeff );
492}
493
494InternalCF*
495InternalPoly::modsame( InternalCF* aCoeff )
496{
497    if ( inExtension() && getReduce( var ) )
498    {
499        if ( deleteObject() ) delete this;
500        return CFFactory::basic( 0 );
501    }
502    InternalPoly *aPoly = (InternalPoly*)aCoeff;
503    termList dummy, first, last;
504    CanonicalForm coeff, newcoeff;
505    int exp, newexp;
506    bool singleObject;
507
508    if ( getRefCount() == 1 )
509    {
510        first = firstTerm; last = lastTerm; singleObject = true;
511    }
512    else
513    {
514        first = copyTermList( firstTerm, last ); singleObject = false;
515        decRefCount();
516    }
517    coeff = aPoly->firstTerm->coeff;
518    exp = aPoly->firstTerm->exp;
519    while (first && ( first->exp >= exp ) )
520    {
521        newcoeff = first->coeff / coeff;
522        newexp = first->exp - exp;
523        dummy = first;
524        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
525        delete dummy;
526    }
527    if ( singleObject )
528    {
529        if ( first && first->exp != 0 )
530        {
531            firstTerm = first;
532            lastTerm = last;
533            return this;
534        }
535        else  if ( first )
536        {
537            InternalCF * res = first->coeff.getval();
538            delete first;
539            firstTerm = 0;
540            delete this;
541            return res;
542        }
543        else
544        {
545            firstTerm = 0;
546            delete this;
547            return CFFactory::basic( 0 );
548        }
549    }
550    else
551    {
552        if ( first && first->exp != 0 )
553            return new InternalPoly( first, last, var );
554        else  if ( first )
555        {
556            InternalCF * res = first->coeff.getval();
557            delete first;
558            return res;
559        }
560        else
561            return CFFactory::basic( 0 );
562    }
563}
564
565
566void
567InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
568{
569    if ( inExtension() && getReduce( var ) )
570    {
571        InternalCF * dummy = acoeff->invert();
572        quot = dummy->mulsame( this );
573        rem = CFFactory::basic( 0 );
574    }
575    else
576    {
577        InternalPoly *aPoly = (InternalPoly*)acoeff;
578        termList dummy, first, last, resultfirst = 0, resultlast = 0;
579        CanonicalForm coeff, newcoeff;
580        int exp, newexp;
581
582        first = copyTermList( firstTerm, last );
583
584        coeff = aPoly->firstTerm->coeff;
585        exp = aPoly->firstTerm->exp;
586        while (first && ( first->exp >= exp ) )
587               {
588            newcoeff = first->coeff / coeff;
589            newexp = first->exp - exp;
590            dummy = first;
591            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
592            delete dummy;
593            appendTermList( resultfirst, resultlast, newcoeff, newexp );
594        }
595        if ( resultfirst )
596            if ( resultfirst->exp == 0 )
597            {
598                quot = resultfirst->coeff.getval();
599                delete resultfirst;
600            }
601            else
602                quot = new InternalPoly( resultfirst, resultlast, var );
603        else
604            quot = CFFactory::basic( 0 );
605        if ( first )
606            if ( first->exp == 0 )
607            {
608                rem = first->coeff.getval();
609                delete first;
610            }
611            else
612                rem = new InternalPoly( first, last, var );
613        else
614            rem = CFFactory::basic( 0 );
615    }
616}
617
618
619bool
620InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
621{
622    if ( inExtension() && getReduce( var ) )
623    {
624        divremsame( acoeff, quot, rem );
625        return true;
626    }
627    InternalPoly *aPoly = (InternalPoly*)acoeff;
628    termList dummy, first, last, resultfirst = 0, resultlast = 0;
629    CanonicalForm coeff, newcoeff, dummycoeff;
630    int exp, newexp;
631    bool divideok = true;
632
633//    if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
634//        return false;
635
636    first = copyTermList( firstTerm, last );
637
638    coeff = aPoly->firstTerm->coeff;
639    exp = aPoly->firstTerm->exp;
640    while (first && ( first->exp >= exp ) && divideok )
641    {
642        divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff );
643        if ( divideok && dummycoeff.isZero() )
644        {
645            newexp = first->exp - exp;
646            dummy = first;
647            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
648            delete dummy;
649            appendTermList( resultfirst, resultlast, newcoeff, newexp );
650        }
651        else
652            divideok = false;
653    }
654    if ( divideok )
655    {
656        if ( resultfirst )
657            if ( resultfirst->exp == 0 )
658            {
659                quot = resultfirst->coeff.getval();
660                delete resultfirst;
661            }
662            else
663                quot = new InternalPoly( resultfirst, resultlast, var );
664        else
665            quot = CFFactory::basic( 0 );
666        if ( first )
667            if ( first->exp == 0 )
668            {
669                rem = first->coeff.getval();
670                delete first;
671            }
672            else
673                rem = new InternalPoly( first, last, var );
674        else
675            rem = CFFactory::basic( 0 );
676    }
677    else
678    {
679        freeTermList( resultfirst );
680        freeTermList( first );
681    }
682    return divideok;
683}
684
685//{{{ int InternalPoly::comparesame, comparecoeff ( InternalCF * acoeff )
686//{{{ docu
687//
688// comparesame(), comparecoeff() - compare with an
689//   InternalPoly.
690//
691// comparecoeff() always returns 1 since CO is defined to be
692// larger than anything which is a coefficient w.r.t. CO.
693//
694// comparesame() compares the coefficient vectors of f=CO and
695// g=acoeff w.r.t to a lexicographic order in the following way:
696// f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
697// i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
698// ii) g[i] occurs in g (i.e. is not equal to zero) and
699//     f[i] does not occur in f or f[i] < g[i] if f[i] occurs
700// where f[i] denotes the coefficient to the power x^i of f.
701//
702// As usual, comparesame() returns 1 if CO is larger than c, 0 if
703// CO equals c, and -1 if CO is less than c.  However, this
704// function is optimized to test on equality since this is its
705// most important and frequent usage.
706//
707// See the respective `CanonicalForm'-methods for an explanation
708// why we define such a strange (but total) ordering on
709// polynomials.
710//
711// See also: CanonicalForm::operator <(), CanonicalForm::operator ==()
712//
713//}}}
714int
715InternalPoly::comparesame ( InternalCF * acoeff )
716{
717    ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
718    InternalPoly* apoly = (InternalPoly*)acoeff;
719    // check on triviality
720    if ( this == apoly )
721        return 0;
722    else
723    {
724        termList cursor1 = firstTerm;
725        termList cursor2 = apoly->firstTerm;
726        for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
727            // we test on inequality of coefficients at this
728            // point instead of testing on "less than" at the
729            // last `else' in the enclosed `if' statement since a
730            // test on inequaltiy in general is cheaper
731            if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) )
732                if ( cursor1->exp > cursor2->exp )
733                    return 1;
734                else  if ( cursor1->exp < cursor2->exp )
735                    return -1;
736                else  if ( cursor1->coeff > cursor2->coeff )
737                    return 1;
738                else
739                    return -1;
740        // check trailing terms
741        if ( cursor1 == cursor2 )
742            return 0;
743        else if ( cursor1 != 0 )
744            return 1;
745        else
746            return -1;
747    }
748}
749
750int
751InternalPoly::comparecoeff ( InternalCF * )
752{
753    return 1;
754}
755//}}}
756
757InternalCF*
758InternalPoly::addcoeff( InternalCF* cc )
759{
760    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
761    if ( c.isZero() )
762        return this;
763    else
764    {
765        if ( getRefCount() == 1 )
766        {
767            if ( lastTerm->exp == 0 )
768            {
769                lastTerm->coeff += c;
770                if ( lastTerm->coeff.isZero() )
771                {
772                    termList cursor = firstTerm;
773                    while ( cursor->next != lastTerm )
774                        cursor = cursor->next;
775                    delete lastTerm;
776                    cursor->next = 0;
777                    lastTerm = cursor;
778                }
779            }
780            else
781            {
782                lastTerm->next = new term( 0, c, 0 );
783                lastTerm = lastTerm->next;
784            }
785            return this;
786        }
787        else
788        {
789            decRefCount();
790            termList last, first = copyTermList( firstTerm, last, false );
791            if ( last->exp == 0 )
792            {
793                last->coeff += c;
794                if ( last->coeff.isZero() )
795                {
796                    termList cursor = first;
797                    while ( cursor->next != last )
798                        cursor = cursor->next;
799                    delete last;
800                    cursor->next = 0;
801                    last = cursor;
802                }
803            }
804            else
805            {
806                last->next = new term( 0, c, 0 );
807                last = last->next;
808            }
809            return new InternalPoly( first, last, var );
810        }
811    }
812}
813
814InternalCF*
815InternalPoly::subcoeff( InternalCF* cc, bool negate )
816{
817    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
818    if ( c.isZero() )
819        if ( getRefCount() > 1 )
820        {
821            decRefCount();
822            termList last, first = copyTermList( firstTerm, last, negate );
823            return new InternalPoly( first, last, var );
824        }
825        else
826        {
827            if ( negate )
828                negateTermList( firstTerm );
829            return this;
830        }
831    else
832    {
833        if ( getRefCount() == 1 )
834        {
835            if ( lastTerm->exp == 0 )
836            {
837                if ( negate )
838                {
839                    negateTermList( firstTerm );
840                    lastTerm->coeff += c;
841                }
842                else
843                    lastTerm->coeff -= c;
844                if ( lastTerm->coeff.isZero() )
845                {
846                    termList cursor = firstTerm;
847                    while ( cursor->next != lastTerm )
848                        cursor = cursor->next;
849                    delete lastTerm;
850                    cursor->next = 0;
851                    lastTerm = cursor;
852                }
853            }
854            else
855            {
856                if ( negate )
857                {
858                    negateTermList( firstTerm );
859                    lastTerm->next = new term( 0, c, 0 );
860                }
861                else
862                    lastTerm->next = new term( 0, -c, 0 );
863                lastTerm = lastTerm->next;
864            }
865            return this;
866        }
867        else
868        {
869            decRefCount();
870            termList last, first = copyTermList( firstTerm, last, negate );
871            if ( last->exp == 0 )
872            {
873                if ( negate )
874                    last->coeff += c;
875                else
876                    last->coeff -= c;
877                if ( last->coeff.isZero() )
878                {
879                    termList cursor = first;
880                    while ( cursor->next != last )
881                        cursor = cursor->next;
882                    delete last;
883                    cursor->next = 0;
884                    last = cursor;
885                }
886            }
887            else
888            {
889                if ( negate )
890                    last->next = new term( 0, c, 0 );
891                else
892                    last->next = new term( 0, -c, 0 );
893                last = last->next;
894            }
895            return new InternalPoly( first, last, var );
896        }
897    }
898}
899
900InternalCF*
901InternalPoly::mulcoeff( InternalCF* cc )
902{
903    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
904    if ( c.isZero() )
905    {
906        if ( getRefCount() == 1 )
907        {
908            delete this;
909            return CFFactory::basic( 0 );
910        }
911        else
912        {
913            decRefCount();
914            return CFFactory::basic( 0 );
915        }
916    }
917    else  if ( c.isOne() )
918        return this;
919    else
920    {
921        if ( getRefCount() == 1 )
922        {
923            mulTermList( firstTerm, c, 0 );
924            return this;
925        }
926        else
927        {
928            decRefCount();
929            termList last, first = copyTermList( firstTerm, last );
930            mulTermList( first, c, 0 );
931            return new InternalPoly( first, last, var );
932        }
933    }
934}
935
936InternalCF*
937InternalPoly::dividecoeff( InternalCF* cc, bool invert )
938{
939    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
940    if ( inExtension() && getReduce( var ) && invert )
941    {
942        InternalCF * dummy;
943        dummy = this->invert();
944        if (is_imm(dummy))
945        {
946          if (is_imm(cc))
947          {
948            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
949            dummy=d;
950          }
951          else
952            dummy=cc->mulcoeff(dummy);
953        }
954        else dummy = dummy->mulcoeff( cc );
955        if ( getRefCount() == 1 )
956        {
957            delete this;
958            return dummy;
959        }
960        else
961        {
962            decRefCount();
963            return dummy;
964        }
965    }
966    if ( invert )
967        if ( getRefCount() == 1 )
968        {
969            delete this;
970            return CFFactory::basic( 0 );
971        }
972        else
973        {
974            decRefCount();
975            return CFFactory::basic( 0 );
976        }
977    if ( c.isOne() )
978        return this;
979    else
980    {
981        if ( getRefCount() == 1 )
982        {
983            firstTerm = divideTermList( firstTerm, c, lastTerm );
984            if ( firstTerm && firstTerm->exp != 0 )
985                return this;
986            else  if ( firstTerm )
987            {
988                InternalCF * res = firstTerm->coeff.getval();
989                delete this;
990                return res;
991            }
992            else
993            {
994                delete this;
995                return CFFactory::basic( 0 );
996            }
997        }
998        else
999        {
1000            decRefCount();
1001            termList last, first = copyTermList( firstTerm, last );
1002            first = divideTermList( first, c, last );
1003            if ( first && first->exp != 0 )
1004                return new InternalPoly( first, last, var );
1005            else  if ( first )
1006            {
1007                InternalCF * res = first->coeff.getval();
1008                delete first;
1009                return res;
1010            }
1011            else
1012            {
1013                delete first;
1014                return CFFactory::basic( 0 );
1015            }
1016        }
1017    }
1018}
1019
1020InternalCF*
1021InternalPoly::divcoeff( InternalCF* cc, bool invert )
1022{
1023    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1024    if ( inExtension() && getReduce( var ) && invert )
1025    {
1026        InternalCF * dummy;
1027        dummy = this->invert();
1028        dummy = dummy->mulcoeff( cc );
1029        if ( getRefCount() == 1 )
1030        {
1031            delete this;
1032            return dummy;
1033        }
1034        else
1035        {
1036            decRefCount();
1037            return dummy;
1038        }
1039    }
1040    if ( invert )
1041        if ( getRefCount() == 1 )
1042        {
1043            delete this;
1044            return CFFactory::basic( 0 );
1045        }
1046        else
1047        {
1048            decRefCount();
1049            return CFFactory::basic( 0 );
1050        }
1051    if ( c.isOne() )
1052        return this;
1053    else
1054    {
1055        if ( getRefCount() == 1 )
1056        {
1057            firstTerm = divTermList( firstTerm, c, lastTerm );
1058            if ( firstTerm && firstTerm->exp != 0 )
1059                return this;
1060            else  if ( firstTerm )
1061            {
1062                InternalCF * res = firstTerm->coeff.getval();
1063                delete this;
1064                return res;
1065            }
1066            else
1067            {
1068                delete this;
1069                return CFFactory::basic( 0 );
1070            }
1071        }
1072        else
1073        {
1074            decRefCount();
1075            termList last, first = copyTermList( firstTerm, last );
1076            first = divTermList( first, c, last );
1077            if ( first && first->exp != 0 )
1078                return new InternalPoly( first, last, var );
1079            else  if ( first )
1080            {
1081                InternalCF * res = first->coeff.getval();
1082                delete first;
1083                return res;
1084            }
1085            else
1086            {
1087                delete first;
1088                return CFFactory::basic( 0 );
1089            }
1090        }
1091    }
1092}
1093
1094InternalCF*
1095InternalPoly::modulocoeff( InternalCF* cc, bool invert )
1096{
1097    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1098    if ( invert )
1099    {
1100        if ( deleteObject() ) delete this;
1101        return c.getval();
1102    }
1103    ASSERT( ! c.isZero(), "divide by zero!" );
1104    if ( deleteObject() ) delete this;
1105    return CFFactory::basic( 0 );
1106}
1107
1108InternalCF*
1109InternalPoly::modcoeff( InternalCF* cc, bool invert )
1110{
1111    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1112    if ( invert )
1113    {
1114        if ( deleteObject() ) delete this;
1115        return c.getval();
1116    }
1117    ASSERT( ! c.isZero(), "divide by zero!" );
1118    if ( c.isOne() )
1119    {
1120        if ( getRefCount() == 1 )
1121        {
1122            delete this;
1123            return CFFactory::basic( 0 );
1124        }
1125        else
1126        {
1127            decRefCount();
1128            return CFFactory::basic( 0 );
1129        }
1130    }
1131    else
1132    {
1133        if ( getRefCount() == 1 )
1134        {
1135            firstTerm = modTermList( firstTerm, c, lastTerm );
1136            if ( firstTerm && firstTerm->exp != 0 )
1137                return this;
1138            else  if ( firstTerm )
1139            {
1140                InternalCF * res = firstTerm->coeff.getval();
1141                delete this;
1142                return res;
1143            }
1144            else
1145            {
1146                delete this;
1147                return CFFactory::basic( 0 );
1148            }
1149        }
1150        else
1151        {
1152            decRefCount();
1153            termList last, first = copyTermList( firstTerm, last );
1154            first = modTermList( first, c, last );
1155            if ( first && first->exp != 0 )
1156                return new InternalPoly( first, last, var );
1157            else  if ( first )
1158            {
1159                InternalCF * res = first->coeff.getval();
1160                delete first;
1161                return res;
1162            }
1163            else
1164            {
1165                delete first;
1166                return CFFactory::basic( 0 );
1167            }
1168        }
1169    }
1170}
1171
1172void
1173InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
1174{
1175    if ( inExtension() && getReduce( var ) )
1176    {
1177        quot = copyObject();
1178        quot = quot->dividecoeff( cc, invert );
1179        rem = CFFactory::basic( 0 );
1180    }
1181    else  if ( invert )
1182    {
1183        if ( is_imm( cc ) )
1184            rem = cc;
1185        else
1186            rem = cc->copyObject();
1187        quot = CFFactory::basic( 0 );
1188    }
1189    else
1190    {
1191        CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1192        ASSERT( ! c.isZero(), "divide by zero!" );
1193        termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
1194        quotfirst = divideTermList( quotfirst, c, quotlast );
1195        if ( quotfirst )
1196            if ( quotfirst->exp == 0 )
1197            {
1198                quot = quotfirst->coeff.getval();
1199                delete quotfirst;
1200            }
1201            else
1202                quot = new InternalPoly( quotfirst, quotlast, var );
1203        else
1204            quot = CFFactory::basic( 0 );
1205        rem = CFFactory::basic( 0 );
1206    }
1207}
1208
1209bool
1210InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
1211{
1212    if ( inExtension() && getReduce( var ) )
1213    {
1214        quot = copyObject();
1215        quot = quot->dividecoeff( cc, invert );
1216        rem = CFFactory::basic( 0 );
1217        return true;
1218    }
1219    else  if ( invert )
1220    {
1221        if ( is_imm( cc ) )
1222            rem = cc;
1223        else
1224            rem = cc->copyObject();
1225        quot = CFFactory::basic( 0 );
1226        return true;
1227    }
1228    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1229    ASSERT( ! c.isZero(), "divide by zero!" );
1230    termList quotfirst, quotcursor;
1231    termList cursor;
1232    CanonicalForm cquot, crem;
1233    bool divideok = true;
1234
1235    cursor = firstTerm;
1236    quotcursor = quotfirst = new term;
1237
1238    while ( cursor && divideok )
1239    {
1240        divideok = divremt( cursor->coeff, c, cquot, crem );
1241        divideok = divideok && crem.isZero();
1242        if ( divideok )
1243        {
1244            if ( ! cquot.isZero() )
1245            {
1246                quotcursor->next = new term( 0, cquot, cursor->exp );
1247                quotcursor = quotcursor->next;
1248            }
1249            cursor = cursor->next;
1250        }
1251    }
1252    quotcursor->next = 0;
1253    if ( divideok )
1254    {
1255        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1256        if ( quotfirst )
1257            if ( quotfirst->exp == 0 )
1258            {
1259                quot = quotfirst->coeff.getval();
1260                delete quotfirst;
1261            }
1262            else
1263                quot = new InternalPoly( quotfirst, quotcursor, var );
1264        else
1265            quot = CFFactory::basic( 0 );
1266        rem = CFFactory::basic( 0 );
1267    }
1268    else
1269    {
1270        freeTermList( quotfirst );
1271    }
1272    return divideok;
1273}
1274
1275// static functions
1276
1277termList
1278InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
1279{
1280    if ( aTermList == 0 )
1281        return 0;
1282    else  if ( negate )
1283    {
1284        termList sourceCursor = aTermList;
1285        termList dummy = new term;
1286        termList targetCursor = dummy;
1287
1288        while ( sourceCursor )
1289        {
1290            targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1291            targetCursor = targetCursor->next;
1292            sourceCursor = sourceCursor->next;
1293        }
1294        targetCursor->next = 0;
1295        theLastTerm = targetCursor;
1296        targetCursor = dummy->next;
1297        delete dummy;
1298        return targetCursor;
1299    }
1300    else
1301    {
1302        termList sourceCursor = aTermList;
1303        termList dummy = new term;
1304        termList targetCursor = dummy;
1305
1306        while ( sourceCursor )
1307        {
1308            targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1309            targetCursor = targetCursor->next;
1310            sourceCursor = sourceCursor->next;
1311        }
1312        targetCursor->next = 0;
1313        theLastTerm = targetCursor;
1314        targetCursor = dummy->next;
1315        delete dummy;
1316        return targetCursor;
1317    }
1318}
1319
1320termList
1321InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
1322{
1323    if ( aTermList == 0 )
1324        return 0;
1325    else
1326    {
1327        termList sourceCursor = aTermList;
1328        termList dummy = new term;
1329        termList targetCursor = dummy;
1330
1331        while ( sourceCursor )
1332        {
1333            targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1334            targetCursor = targetCursor->next;
1335            sourceCursor = sourceCursor->next;
1336        }
1337        targetCursor->next = 0;
1338        theLastTerm = targetCursor;
1339        targetCursor = dummy->next;
1340        delete dummy;
1341        return targetCursor;
1342    }
1343}
1344
1345void
1346InternalPoly::freeTermList ( termList aTermList )
1347{
1348    termList cursor = aTermList;
1349
1350    while ( cursor )
1351    {
1352        cursor = cursor->next;
1353        delete aTermList;
1354        aTermList = cursor;
1355    }
1356}
1357
1358void
1359InternalPoly::negateTermList ( termList terms )
1360{
1361    termList cursor = terms;
1362    while ( cursor )
1363    {
1364        cursor->coeff = -cursor->coeff;
1365        cursor = cursor->next;
1366    }
1367}
1368
1369termList
1370InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
1371{
1372    termList theCursor = theList;
1373    termList aCursor = aList;
1374    termList predCursor = 0;
1375
1376    while ( theCursor && aCursor )
1377    {
1378        if ( theCursor->exp == aCursor->exp )
1379        {
1380            if ( negate )
1381                theCursor->coeff -= aCursor->coeff;
1382            else
1383                theCursor->coeff += aCursor->coeff;
1384            if ( theCursor->coeff.isZero() )
1385            {
1386                if ( predCursor )
1387                {
1388                    predCursor->next = theCursor->next;
1389                    delete theCursor;
1390                    theCursor = predCursor->next;
1391                }
1392                else
1393                {
1394                    theList = theList->next;
1395                    delete theCursor;
1396                    theCursor = theList;
1397                }
1398            }
1399            else
1400            {
1401                predCursor = theCursor;
1402                theCursor = theCursor->next;
1403            }
1404            aCursor = aCursor->next;
1405        }
1406        else if ( theCursor->exp < aCursor->exp )
1407        {
1408            if ( negate )
1409                if ( predCursor )
1410                {
1411                    predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1412                    predCursor = predCursor->next;
1413                }
1414                else
1415                {
1416                    theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1417                    predCursor = theList;
1418                }
1419            else
1420                if ( predCursor )
1421                {
1422                    predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1423                    predCursor = predCursor->next;
1424                }
1425                else
1426                {
1427                    theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1428                    predCursor = theList;
1429                }
1430            aCursor = aCursor->next;
1431        }
1432        else
1433        {
1434            predCursor = theCursor;
1435            theCursor = theCursor->next;
1436        }
1437    }
1438    if ( aCursor )
1439    {
1440        if ( predCursor )
1441            predCursor->next = copyTermList( aCursor, lastTerm, negate );
1442        else
1443            theList = copyTermList( aCursor, lastTerm, negate );
1444    }
1445    else if ( ! theCursor )
1446        lastTerm = predCursor;
1447
1448    return theList;
1449}
1450
1451void
1452InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
1453{
1454    while ( theCursor )
1455    {
1456        theCursor->coeff *= coeff;
1457        theCursor->exp += exp;
1458        theCursor = theCursor->next;
1459    }
1460}
1461
1462termList
1463InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1464{
1465    termList theCursor = firstTerm;
1466    lastTerm = 0;
1467    termList dummy;
1468
1469    while ( theCursor )
1470    {
1471        theCursor->coeff /= coeff;
1472        if ( theCursor->coeff.isZero() )
1473        {
1474            if ( theCursor == firstTerm )
1475                firstTerm = theCursor->next;
1476            else
1477                lastTerm->next = theCursor->next;
1478            dummy = theCursor;
1479            theCursor = theCursor->next;
1480            delete dummy;
1481        }
1482        else
1483        {
1484            lastTerm = theCursor;
1485            theCursor = theCursor->next;
1486        }
1487    }
1488    return firstTerm;
1489}
1490
1491termList
1492InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1493{
1494    termList theCursor = firstTerm;
1495    lastTerm = 0;
1496    termList dummy;
1497
1498    while ( theCursor )
1499    {
1500        theCursor->coeff.div( coeff );
1501        if ( theCursor->coeff.isZero() )
1502        {
1503            if ( theCursor == firstTerm )
1504                firstTerm = theCursor->next;
1505            else
1506                lastTerm->next = theCursor->next;
1507            dummy = theCursor;
1508            theCursor = theCursor->next;
1509            delete dummy;
1510        }
1511        else
1512        {
1513            lastTerm = theCursor;
1514            theCursor = theCursor->next;
1515        }
1516    }
1517    return firstTerm;
1518}
1519
1520termList
1521InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1522{
1523    termList theCursor = firstTerm;
1524    lastTerm = 0;
1525    termList dummy;
1526
1527    while ( theCursor )
1528    {
1529        theCursor->coeff.mod( coeff );
1530        if ( theCursor->coeff.isZero() )
1531        {
1532            if ( theCursor == firstTerm )
1533                firstTerm = theCursor->next;
1534            else
1535                lastTerm->next = theCursor->next;
1536            dummy = theCursor;
1537            theCursor = theCursor-> next;
1538            delete dummy;
1539        }
1540        else
1541        {
1542            lastTerm = theCursor;
1543            theCursor = theCursor->next;
1544        }
1545    }
1546    return firstTerm;
1547}
1548
1549void
1550InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
1551{
1552    if ( last )
1553    {
1554        last->next = new term( 0, coeff, exp );
1555        last = last->next;
1556    }
1557    else
1558    {
1559        first = new term( 0, coeff, exp );
1560        last = first;
1561    }
1562}
1563
1564termList
1565InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
1566{
1567    termList theCursor = theList;
1568    termList aCursor = aList;
1569    termList predCursor = 0;
1570    CanonicalForm coeff;
1571
1572    if ( negate )
1573        coeff = -c;
1574    else
1575        coeff = c;
1576
1577    while ( theCursor && aCursor )
1578    {
1579        if ( theCursor->exp == aCursor->exp + exp )
1580        {
1581            theCursor->coeff += aCursor->coeff * coeff;
1582            if ( theCursor->coeff.isZero() )
1583            {
1584                if ( predCursor )
1585                {
1586                    predCursor->next = theCursor->next;
1587                    delete theCursor;
1588                    theCursor = predCursor->next;
1589                }
1590                else
1591                {
1592                    theList = theList->next;
1593                    delete theCursor;
1594                    theCursor = theList;
1595                }
1596            }
1597            else
1598            {
1599                predCursor = theCursor;
1600                theCursor = theCursor->next;
1601            }
1602            aCursor = aCursor->next;
1603        }
1604        else if ( theCursor->exp < aCursor->exp + exp )
1605        {
1606            if ( predCursor )
1607            {
1608                predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1609                predCursor = predCursor->next;
1610            }
1611            else
1612            {
1613                theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1614                predCursor = theList;
1615            }
1616            aCursor = aCursor->next;
1617        }
1618        else
1619        {
1620            predCursor = theCursor;
1621            theCursor = theCursor->next;
1622        }
1623    }
1624    if ( aCursor )
1625    {
1626        if ( predCursor )
1627        {
1628            predCursor->next = copyTermList( aCursor, lastTerm );
1629            predCursor = predCursor->next;
1630        }
1631        else
1632        {
1633            theList = copyTermList( aCursor, lastTerm );
1634            predCursor = theList;
1635        }
1636        while ( predCursor )
1637        {
1638            predCursor->exp += exp;
1639            predCursor->coeff *= coeff;
1640            predCursor = predCursor->next;
1641        }
1642    }
1643    else if ( ! theCursor )
1644        lastTerm = predCursor;
1645    return theList;
1646}
1647
1648termList
1649InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
1650{
1651    CanonicalForm coeff = redterms->coeff;
1652    CanonicalForm newcoeff;
1653    int newexp;
1654    int exp = redterms->exp;
1655    termList dummy;
1656    while ( first && ( first->exp >= exp ) )
1657    {
1658        newcoeff = first->coeff / coeff;
1659        newexp = first->exp - exp;
1660        dummy = first;
1661        first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
1662        delete dummy;
1663    }
1664    return first;
1665}
Note: See TracBrowser for help on using the repository browser.