source: git/factory/int_poly.cc @ 160f8f7

fieker-DuValspielwiese
Last change on this file since 160f8f7 was 9d7aaa, checked in by Jens Schmidt <schmidt@…>, 27 years ago
#include <config.h> added git-svn-id: file:///usr/local/Singular/svn/trunk@155 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 30.0 KB
Line 
1// emacs edit mode for this file is -*- C++ -*-
2// $Id: int_poly.cc,v 1.3 1997-04-15 09:13:49 schmidt Exp $
3
4/*
5$Log: not supported by cvs2svn $
6Revision 1.2  1997/03/27 10:07:37  schmidt
7stream-io wrapped by NOSTREAMIO
8debug output changed to DEBOUT
9
10Revision 1.1  1996/05/23 09:33:05  stobbe
11"modulocoeff: Bug fix, invert is now handled as it should be.
12"
13
14// Revision 1.0  1996/05/17  10:59:46  stobbe
15// Initial revision
16//
17*/
18
19#include <config.h>
20
21#ifndef NOSTREAMIO
22#include <string.h>
23#include <strstream.h>
24#endif /* NOSTREAMIO */
25
26#include "assert.h"
27
28#include "cf_defs.h"
29#include "cf_factory.h"
30#include "int_cf.h"
31#include "int_poly.h"
32#include "canonicalform.h"
33#include "variable.h"
34#include "imm.h"
35
36
37InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
38{
39    firstTerm = first;
40    lastTerm = last;
41    var = v;
42}
43
44InternalPoly::InternalPoly()
45{
46    ASSERT( 0, "ups, why do you initialize an empty poly" );
47}
48
49InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
50{
51    var = v;
52    firstTerm = new term( 0, c, e );
53    lastTerm = firstTerm;
54}
55
56InternalPoly::InternalPoly( const InternalPoly& )
57{
58    ASSERT( 0, "ups there is something wrong in your code" );
59};
60
61InternalPoly::~InternalPoly()
62{
63    freeTermList( firstTerm );
64}
65
66InternalCF*
67InternalPoly::deepCopyObject() const
68{
69    termList first, last;
70    first = deepCopyTermList( firstTerm, last );
71    return new InternalPoly( first, last, var );
72}
73
74InternalCF*
75InternalPoly::genZero()
76{
77    return firstTerm->coeff.genZero().getval();
78}
79
80InternalCF*
81InternalPoly::genOne()
82{
83    return firstTerm->coeff.genOne().getval();
84}
85
86bool
87InternalPoly::isUnivariate() const
88{
89    termList cursor = firstTerm;
90    while ( cursor ) {
91        if ( ! cursor->coeff.inCoeffDomain() )
92            return false;
93        cursor = cursor->next;
94    }
95    return true;
96}
97
98int
99InternalPoly::degree()
100{
101    return firstTerm->exp;
102}
103
104int
105InternalPoly::sign() const
106{
107    return firstTerm->coeff.sign();
108}
109
110CanonicalForm
111InternalPoly::lc()
112{
113    return firstTerm->coeff.lc();
114}
115
116CanonicalForm
117InternalPoly::LC()
118{
119    return firstTerm->coeff;
120}
121
122int
123InternalPoly::taildegree()
124{
125    return lastTerm->exp;
126}
127
128CanonicalForm
129InternalPoly::tailcoeff()
130{
131    return lastTerm->coeff;
132}
133
134CanonicalForm
135InternalPoly::coeff( int i )
136{
137    termList theCursor = firstTerm;
138    while ( theCursor ) {
139        if ( theCursor->exp == i )
140            return theCursor->coeff;
141        else if ( theCursor->exp > i )
142            theCursor = theCursor->next;
143        else
144            theCursor = 0;
145    }
146    return 0;
147}
148
149#ifndef NOSTREAMIO
150void
151InternalPoly::print(ostream &aStream, char * aString )
152{
153    if ( ! firstTerm )
154        aStream << 0 << aString;
155    else {
156        char * theString;
157        termList theCursor = firstTerm;
158        while ( theCursor ) {
159            ostrstream theStream;
160            if ( theCursor->exp == 0 )
161                theCursor->coeff.print( aStream, aString );
162            else  if ( theCursor->coeff.isOne() ) {
163                aStream << var;
164                if ( theCursor->exp != 1 )
165                    aStream << '^' << theCursor->exp << aString;
166                else
167                    aStream << aString;
168            }
169            else  if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() ) {
170                aStream << '-' << var;
171                if ( theCursor->exp != 1 )
172                    aStream << '^' << theCursor->exp << aString;
173                else
174                    aStream << aString;
175            }
176            else {
177                theStream << '*' << var;
178                if ( theCursor->exp != 1 )
179                    theStream << '^' << theCursor->exp << aString << ends;
180                else
181                    theStream << aString << ends; // results from error in GNU strstream
182                theString = theStream.str();
183                theCursor->coeff.print( aStream, theString );
184                delete [] theString;
185            }
186            theCursor = theCursor->next;
187            if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
188                aStream << '+';
189        }
190    }
191}
192#endif /* NOSTREAMIO */
193
194InternalCF*
195InternalPoly::neg()
196{
197    if ( getRefCount() == 1 ) {
198        negateTermList( firstTerm );
199        return this;
200    }
201    else {
202        decRefCount();
203        termList last, first = copyTermList( firstTerm, last, true );
204        return new InternalPoly( first, last, var );
205    }
206}
207
208InternalCF*
209InternalPoly::invert()
210{
211    if ( inExtension() && getReduce( var ) ) {
212        setReduce( var, false );
213        CanonicalForm a( this->copyObject() );
214        CanonicalForm b = getMipo( var );
215        CanonicalForm u, v;
216        CanonicalForm g = extgcd( a, b, u, v );
217        setReduce( var, true );
218        return u.getval();
219    }
220    else
221        return CFFactory::basic( 0 );
222}
223
224int
225InternalPoly::comparesame ( InternalCF* acoeff )
226{
227    InternalPoly* apoly = (InternalPoly*)acoeff;
228    if ( this == apoly )
229        return 0;
230    else {
231        termList cur1 = firstTerm;
232        termList cur2 = apoly->firstTerm;
233        for ( ; cur1 && cur2; cur1 = cur1->next, cur2 = cur2->next )
234            if ( ( cur1->exp != cur2->exp ) || ( cur1->coeff != cur2->coeff ) )
235                if ( cur1->exp > cur2->exp )
236                    return 1;
237                else  if ( cur1->exp < cur2->exp )
238                    return -1;
239                else  if ( cur1->coeff > cur2->coeff )
240                    return 1;
241                else
242                    return -1;
243        return cur1 != cur2;
244    }
245}
246
247InternalCF*
248InternalPoly::addsame( InternalCF* aCoeff )
249{
250    InternalPoly * aPoly = (InternalPoly*)aCoeff;
251    if ( getRefCount() == 1 ) {
252        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
253        if ( firstTerm && firstTerm->exp != 0 )
254            return this;
255        else  if ( firstTerm ) {
256            InternalCF * res = firstTerm->coeff.getval();
257            delete this;
258            return res;
259        }
260        else {
261            delete this;
262            return CFFactory::basic( 0 );
263        }
264    }
265    else {
266        decRefCount();
267        termList last, first = copyTermList( firstTerm, last );
268        first = addTermList( first, aPoly->firstTerm, last, false );
269        if ( first && first->exp != 0 )
270            return new InternalPoly( first, last, var );
271        else  if ( first ) {
272            InternalCF * res = first->coeff.getval();
273            delete first;
274            return res;
275        }
276        else
277            return CFFactory::basic( 0 );
278
279    }
280}
281
282InternalCF*
283InternalPoly::subsame( InternalCF* aCoeff )
284{
285    InternalPoly * aPoly = (InternalPoly*)aCoeff;
286    if ( getRefCount() == 1 ) {
287        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
288        if ( firstTerm && firstTerm->exp != 0 )
289            return this;
290        else  if ( firstTerm ) {
291            InternalCF * res = firstTerm->coeff.getval();
292            delete this;
293            return res;
294        }
295        else {
296            delete this;
297            return CFFactory::basic( 0 );
298        }
299    }
300    else {
301        decRefCount();
302        termList last, first = copyTermList( firstTerm, last );
303        first = addTermList( first, aPoly->firstTerm, last, true );
304        if ( first && first->exp != 0 )
305            return new InternalPoly( first, last, var );
306        else  if ( first ) {
307            InternalCF * res = first->coeff.getval();
308            delete first;
309            return res;
310        }
311        else
312            return CFFactory::basic( 0 );
313
314    }
315}
316
317InternalCF*
318InternalPoly::mulsame( InternalCF* aCoeff )
319{
320    InternalPoly *aPoly = (InternalPoly*)aCoeff;
321    termList resultFirst = 0, resultLast = 0;
322    termList theCursor = firstTerm;
323
324    while ( theCursor ) {
325        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm, theCursor->coeff, theCursor->exp, resultLast, false );
326        theCursor = theCursor->next;
327    }
328    if ( inExtension() && getReduce( var ) ) {
329        resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
330        if ( resultFirst == 0 )
331            if ( getRefCount() == 1 ) {
332                delete this;
333                return CFFactory::basic(0);
334            }
335            else {
336                decRefCount();
337                return CFFactory::basic(0);
338            }
339        else  if ( resultFirst->exp == 0 )
340            if ( getRefCount() == 1 ) {
341                InternalCF * res = resultFirst->coeff.getval();
342                delete resultFirst;
343                delete this;
344                return res;
345            }
346            else {
347                decRefCount();
348                InternalCF * res = resultFirst->coeff.getval();
349                delete resultFirst;
350                return res;
351            }
352    }
353    if ( getRefCount() == 1 ) {
354        freeTermList( firstTerm );
355        firstTerm = resultFirst;
356        lastTerm = resultLast;
357        return this;
358    }
359    else {
360        decRefCount();
361        return new InternalPoly( resultFirst, resultLast, var );
362    }
363}
364
365InternalCF*
366InternalPoly::dividesame( InternalCF* aCoeff )
367{
368    return divsame( aCoeff );
369}
370
371
372InternalCF*
373InternalPoly::divsame( InternalCF* aCoeff )
374{
375    if ( inExtension() && getReduce( var ) ) {
376        InternalCF * dummy = aCoeff->invert();
377        dummy = dummy->mulsame( this );
378        if ( getRefCount() == 1 ) {
379             delete this;
380             return dummy;
381        }
382        else {
383            decRefCount();
384            return dummy;
385        }
386    }
387    InternalPoly *aPoly = (InternalPoly*)aCoeff;
388    termList dummy, first, last, resultfirst = 0, resultlast = 0;
389    CanonicalForm coeff, newcoeff;
390    int exp, newexp;
391    bool singleObject;
392
393    if ( getRefCount() == 1 ) {
394        first = firstTerm; last = lastTerm; singleObject = true;
395    }
396    else {
397        first = copyTermList( firstTerm, last ); singleObject = false;
398        decRefCount();
399    }
400    coeff = aPoly->firstTerm->coeff;
401    exp = aPoly->firstTerm->exp;
402    while (first && ( first->exp >= exp ) ) {
403        newcoeff = first->coeff / coeff;
404        newexp = first->exp - exp;
405        dummy = first;
406        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
407        delete dummy;
408        appendTermList( resultfirst, resultlast, newcoeff, newexp );
409    }
410    freeTermList( first );
411    if ( singleObject ) {
412        if ( resultfirst && resultfirst->exp != 0 ) {
413            firstTerm = resultfirst;
414            lastTerm = resultlast;
415            return this;
416        }
417        else  if ( resultfirst ) {
418            InternalCF * res = resultfirst->coeff.getval();
419            delete resultfirst;
420            firstTerm = 0;
421            delete this;
422            return res;
423        }
424        else {
425            // this should not happen (evtl use assertion)
426            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
427            firstTerm = 0;
428            delete this;
429            return CFFactory::basic( 0 );
430        }
431    }
432    else {
433        if ( resultfirst && resultfirst->exp != 0 )
434            return new InternalPoly( resultfirst, resultlast, var );
435        else  if ( resultfirst ) {
436            InternalCF * res = resultfirst->coeff.getval();
437            delete resultfirst;
438            return res;
439        }
440        else
441            return CFFactory::basic( 0 );
442    }
443}
444
445InternalCF*
446InternalPoly::modulosame( InternalCF* aCoeff )
447{
448    return modsame( aCoeff );
449}
450
451InternalCF*
452InternalPoly::modsame( InternalCF* aCoeff )
453{
454    if ( inExtension() && getReduce( var ) ) {
455        if ( deleteObject() ) delete this;
456        return CFFactory::basic( 0 );
457    }
458    InternalPoly *aPoly = (InternalPoly*)aCoeff;
459    termList dummy, first, last;
460    CanonicalForm coeff, newcoeff;
461    int exp, newexp;
462    bool singleObject;
463
464    if ( getRefCount() == 1 ) {
465        first = firstTerm; last = lastTerm; singleObject = true;
466    }
467    else {
468        first = copyTermList( firstTerm, last ); singleObject = false;
469        decRefCount();
470    }
471    coeff = aPoly->firstTerm->coeff;
472    exp = aPoly->firstTerm->exp;
473    while (first && ( first->exp >= exp ) ) {
474        newcoeff = first->coeff / coeff;
475        newexp = first->exp - exp;
476        dummy = first;
477        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
478        delete dummy;
479    }
480    if ( singleObject ) {
481        if ( first && first->exp != 0 ) {
482            firstTerm = first;
483            lastTerm = last;
484            return this;
485        }
486        else  if ( first ) {
487            InternalCF * res = first->coeff.getval();
488            delete first;
489            firstTerm = 0;
490            delete this;
491            return res;
492        }
493        else {
494            firstTerm = 0;
495            delete this;
496            return CFFactory::basic( 0 );
497        }
498    }
499    else {
500        if ( first && first->exp != 0 )
501            return new InternalPoly( first, last, var );
502        else  if ( first ) {
503            InternalCF * res = first->coeff.getval();
504            delete first;
505            return res;
506        }
507        else
508            return CFFactory::basic( 0 );
509    }
510}
511
512
513void
514InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
515{
516    if ( inExtension() && getReduce( var ) ) {
517        InternalCF * dummy = acoeff->invert();
518        quot = dummy->mulsame( this );
519        rem = CFFactory::basic( 0 );
520    }
521    else {
522        InternalPoly *aPoly = (InternalPoly*)acoeff;
523        termList dummy, first, last, resultfirst = 0, resultlast = 0;
524        CanonicalForm coeff, newcoeff;
525        int exp, newexp;
526
527        first = copyTermList( firstTerm, last );
528
529        coeff = aPoly->firstTerm->coeff;
530        exp = aPoly->firstTerm->exp;
531        while (first && ( first->exp >= exp ) ) {
532            newcoeff = first->coeff / coeff;
533            newexp = first->exp - exp;
534            dummy = first;
535            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
536            delete dummy;
537            appendTermList( resultfirst, resultlast, newcoeff, newexp );
538        }
539        if ( resultfirst )
540            if ( resultfirst->exp == 0 ) {
541                quot = resultfirst->coeff.getval();
542                delete resultfirst;
543            }
544            else
545                quot = new InternalPoly( resultfirst, resultlast, var );
546        else
547            quot = CFFactory::basic( 0 );
548        if ( first )
549            if ( first->exp == 0 ) {
550                rem = first->coeff.getval();
551                delete first;
552            }
553            else
554                rem = new InternalPoly( first, last, var );
555        else
556            rem = CFFactory::basic( 0 );
557    }
558}
559
560
561bool
562InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
563{
564    if ( inExtension() && getReduce( var ) ) {
565        divremsame( acoeff, quot, rem );
566        return true;
567    }
568    InternalPoly *aPoly = (InternalPoly*)acoeff;
569    termList dummy, first, last, resultfirst = 0, resultlast = 0;
570    CanonicalForm coeff, newcoeff, dummycoeff;
571    int exp, newexp;
572    bool divideok = true;
573
574//    if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
575//      return false;
576
577    first = copyTermList( firstTerm, last );
578
579    coeff = aPoly->firstTerm->coeff;
580    exp = aPoly->firstTerm->exp;
581    while (first && ( first->exp >= exp ) && divideok ) {
582        divideok = ::divremt( first->coeff, coeff, newcoeff, dummycoeff );
583        if ( divideok && dummycoeff.isZero() ) {
584            newexp = first->exp - exp;
585            dummy = first;
586            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
587            delete dummy;
588            appendTermList( resultfirst, resultlast, newcoeff, newexp );
589        }
590        else
591            divideok = false;
592    }
593    if ( divideok ) {
594        if ( resultfirst )
595            if ( resultfirst->exp == 0 ) {
596                quot = resultfirst->coeff.getval();
597                delete resultfirst;
598            }
599            else
600                quot = new InternalPoly( resultfirst, resultlast, var );
601        else
602            quot = CFFactory::basic( 0 );
603        if ( first )
604            if ( first->exp == 0 ) {
605                rem = first->coeff.getval();
606                delete first;
607            }
608            else
609                rem = new InternalPoly( first, last, var );
610        else
611            rem = CFFactory::basic( 0 );
612    }
613    else {
614        freeTermList( resultfirst );
615        freeTermList( first );
616    }
617    return divideok;
618}
619
620int
621InternalPoly::comparecoeff ( InternalCF* acoeff )
622{
623    return 1;
624}
625
626InternalCF*
627InternalPoly::addcoeff( InternalCF* cc )
628{
629    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
630    if ( c.isZero() )
631        return this;
632    else {
633        if ( getRefCount() == 1 ) {
634            if ( lastTerm->exp == 0 ) {
635                lastTerm->coeff += c;
636                if ( lastTerm->coeff.isZero() ) {
637                    termList cursor = firstTerm;
638                    while ( cursor->next != lastTerm )
639                        cursor = cursor->next;
640                    delete lastTerm;
641                    cursor->next = 0;
642                    lastTerm = cursor;
643                }
644            }
645            else {
646                lastTerm->next = new term( 0, c, 0 );
647                lastTerm = lastTerm->next;
648            }
649            return this;
650        }
651        else {
652            decRefCount();
653            termList last, first = copyTermList( firstTerm, last, false );
654            if ( last->exp == 0 ) {
655                last->coeff += c;
656                if ( last->coeff.isZero() ) {
657                    termList cursor = first;
658                    while ( cursor->next != last )
659                        cursor = cursor->next;
660                    delete last;
661                    cursor->next = 0;
662                    last = cursor;
663                }
664            }
665            else {
666                last->next = new term( 0, c, 0 );
667                last = last->next;
668            }
669            return new InternalPoly( first, last, var );
670        }
671    }
672}
673
674InternalCF*
675InternalPoly::subcoeff( InternalCF* cc, bool negate )
676{
677    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
678    if ( c.isZero() )
679        if ( getRefCount() > 1 ) {
680            decRefCount();
681            termList last, first = copyTermList( firstTerm, last, negate );
682            return new InternalPoly( first, last, var );
683        }
684        else {
685            if ( negate )
686                negateTermList( firstTerm );
687            return this;
688        }
689    else {
690        if ( getRefCount() == 1 ) {
691            if ( lastTerm->exp == 0 ) {
692                if ( negate ) {
693                    negateTermList( firstTerm );
694                    lastTerm->coeff += c;
695                }
696                else
697                    lastTerm->coeff -= c;
698                if ( lastTerm->coeff.isZero() ) {
699                    termList cursor = firstTerm;
700                    while ( cursor->next != lastTerm )
701                        cursor = cursor->next;
702                    delete lastTerm;
703                    cursor->next = 0;
704                    lastTerm = cursor;
705                }
706            }
707            else {
708                if ( negate ) {
709                    negateTermList( firstTerm );
710                    lastTerm->next = new term( 0, c, 0 );
711                }
712                else
713                    lastTerm->next = new term( 0, -c, 0 );
714                lastTerm = lastTerm->next;
715            }
716            return this;
717        }
718        else {
719            decRefCount();
720            termList last, first = copyTermList( firstTerm, last, negate );
721            if ( last->exp == 0 ) {
722                if ( negate )
723                    last->coeff += c;
724                else
725                    last->coeff -= c;
726                if ( last->coeff.isZero() ) {
727                    termList cursor = first;
728                    while ( cursor->next != last )
729                        cursor = cursor->next;
730                    delete last;
731                    cursor->next = 0;
732                    last = cursor;
733                }
734            }
735            else {
736                if ( negate )
737                    last->next = new term( 0, c, 0 );
738                else
739                    last->next = new term( 0, -c, 0 );
740                last = last->next;
741            }
742            return new InternalPoly( first, last, var );
743        }
744    }
745}
746
747InternalCF*
748InternalPoly::mulcoeff( InternalCF* cc )
749{
750    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
751    if ( c.isZero() ) {
752        if ( getRefCount() == 1 ) {
753            delete this;
754            return CFFactory::basic( 0 );
755        }
756        else {
757            decRefCount();
758            return CFFactory::basic( 0 );
759        }
760    }
761    else  if ( c.isOne() )
762        return this;
763    else {
764        if ( getRefCount() == 1 ) {
765            mulTermList( firstTerm, c, 0 );
766            return this;
767        }
768        else {
769            decRefCount();
770            termList last, first = copyTermList( firstTerm, last );
771            mulTermList( first, c, 0 );
772            return new InternalPoly( first, last, var );
773        }
774    }
775}
776
777InternalCF*
778InternalPoly::dividecoeff( InternalCF* c, bool invert )
779{
780    return divcoeff( c, invert );
781}
782
783InternalCF*
784InternalPoly::divcoeff( InternalCF* cc, bool invert )
785{
786    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
787    if ( inExtension() && getReduce( var ) && invert ) {
788        InternalCF * dummy;
789        dummy = this->invert();
790        dummy = dummy->mulcoeff( cc );
791        if ( getRefCount() == 1 ) {
792            delete this;
793            return dummy;
794        }
795        else {
796            decRefCount();
797            return dummy;
798        }
799    }
800    if ( invert )
801        if ( getRefCount() == 1 ) {
802            delete this;
803            return CFFactory::basic( 0 );
804        }
805        else {
806            decRefCount();
807            return CFFactory::basic( 0 );
808        }
809    if ( c.isOne() )
810        return this;
811    else {
812        if ( getRefCount() == 1 ) {
813            firstTerm = divTermList( firstTerm, c, lastTerm );
814            if ( firstTerm && firstTerm->exp != 0 )
815                return this;
816            else  if ( firstTerm ) {
817                InternalCF * res = firstTerm->coeff.getval();
818                delete this;
819                return res;
820            }
821            else {
822                delete this;
823                return CFFactory::basic( 0 );
824            }
825        }
826        else {
827            decRefCount();
828            termList last, first = copyTermList( firstTerm, last );
829            first = divTermList( first, c, last );
830            if ( first && first->exp != 0 )
831                return new InternalPoly( first, last, var );
832            else  if ( first ) {
833                InternalCF * res = first->coeff.getval();
834                delete first;
835                return res;
836            }
837            else {
838                delete first;
839                return CFFactory::basic( 0 );
840            }
841        }
842    }
843}
844
845InternalCF*
846InternalPoly::modulocoeff( InternalCF* cc, bool invert )
847{
848    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
849    if ( invert ) {
850        if ( deleteObject() ) delete this;
851        return c.getval();
852    }
853    ASSERT( ! c.isZero(), "divide by zero!" );
854    if ( deleteObject() ) delete this;
855    return CFFactory::basic( 0 );
856}
857
858InternalCF*
859InternalPoly::modcoeff( InternalCF* cc, bool invert )
860{
861    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
862    if ( invert ) {
863        if ( deleteObject() ) delete this;
864        return c.getval();
865    }
866    ASSERT( ! c.isZero(), "divide by zero!" );
867    if ( c.isOne() ) {
868        if ( getRefCount() == 1 ) {
869            delete this;
870            return CFFactory::basic( 0 );
871        }
872        else {
873            decRefCount();
874            return CFFactory::basic( 0 );
875        }
876    }
877    else {
878        if ( getRefCount() == 1 ) {
879            firstTerm = modTermList( firstTerm, c, lastTerm );
880            if ( firstTerm && firstTerm->exp != 0 )
881                return this;
882            else  if ( firstTerm ) {
883                InternalCF * res = firstTerm->coeff.getval();
884                delete this;
885                return res;
886            }
887            else {
888                delete this;
889                return CFFactory::basic( 0 );
890            }
891        }
892        else {
893            decRefCount();
894            termList last, first = copyTermList( firstTerm, last );
895            first = modTermList( first, c, last );
896            if ( first && first->exp != 0 )
897                return new InternalPoly( first, last, var );
898            else  if ( first ) {
899                InternalCF * res = first->coeff.getval();
900                delete first;
901                return res;
902            }
903            else {
904                delete first;
905                return CFFactory::basic( 0 );
906            }
907        }
908    }
909}
910
911void
912InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
913{
914    if ( inExtension() && getReduce( var ) ) {
915        quot = copyObject();
916        quot = quot->dividecoeff( cc, invert );
917        rem = CFFactory::basic( 0 );
918    }
919    else  if ( invert ) {
920        if ( is_imm( cc ) )
921            rem = cc;
922        else
923            rem = cc->copyObject();
924        quot = CFFactory::basic( 0 );
925    }
926    else {
927        CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
928        ASSERT( ! c.isZero(), "divide by zero!" );
929        termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
930        quotfirst = divTermList( quotfirst, c, quotlast );
931        if ( quotfirst )
932            if ( quotfirst->exp == 0 ) {
933                quot = quotfirst->coeff.getval();
934                delete quotfirst;
935            }
936            else
937                quot = new InternalPoly( quotfirst, quotlast, var );
938        else
939            quot = CFFactory::basic( 0 );
940        rem = CFFactory::basic( 0 );
941    }
942}
943
944bool
945InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
946{
947    if ( inExtension() && getReduce( var ) ) {
948        quot = copyObject();
949        quot = quot->dividecoeff( cc, invert );
950        rem = CFFactory::basic( 0 );
951        return true;
952    }
953    else  if ( invert ) {
954        if ( is_imm( cc ) )
955            rem = cc;
956        else
957            rem = cc->copyObject();
958        quot = CFFactory::basic( 0 );
959        return true;
960    }
961    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
962    ASSERT( ! c.isZero(), "divide by zero!" );
963    termList quotfirst, quotcursor;
964    termList cursor;
965    CanonicalForm cquot, crem;
966    bool divideok = true;
967
968    cursor = firstTerm;
969    quotcursor = quotfirst = new term;
970
971    while ( cursor && divideok ) {
972        divideok = ::divremt( cursor->coeff, c, cquot, crem );
973        divideok = divideok && crem.isZero();
974        if ( divideok ) {
975            if ( ! cquot.isZero() ) {
976                quotcursor->next = new term( 0, cquot, cursor->exp );
977                quotcursor = quotcursor->next;
978            }
979            cursor = cursor->next;
980        }
981    }
982    quotcursor->next = 0;
983    if ( divideok ) {
984        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
985        if ( quotfirst )
986            if ( quotfirst->exp == 0 ) {
987                quot = quotfirst->coeff.getval();
988                delete quotfirst;
989            }
990            else
991                quot = new InternalPoly( quotfirst, quotcursor, var );
992        else
993            quot = CFFactory::basic( 0 );
994        rem = CFFactory::basic( 0 );
995    }
996    else {
997        freeTermList( quotfirst );
998    }
999    return divideok;
1000}
1001
1002// static functions
1003
1004termList
1005InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
1006{
1007    if ( aTermList == 0 )
1008        return 0;
1009    else  if ( negate ) {
1010        termList sourceCursor = aTermList;
1011        termList dummy = new term;
1012        termList targetCursor = dummy;
1013
1014        while ( sourceCursor ) {
1015            targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1016            targetCursor = targetCursor->next;
1017            sourceCursor = sourceCursor->next;
1018        }
1019        targetCursor->next = 0;
1020        theLastTerm = targetCursor;
1021        targetCursor = dummy->next;
1022        delete dummy;
1023        return targetCursor;
1024    }
1025    else {
1026        termList sourceCursor = aTermList;
1027        termList dummy = new term;
1028        termList targetCursor = dummy;
1029
1030        while ( sourceCursor ) {
1031            targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1032            targetCursor = targetCursor->next;
1033            sourceCursor = sourceCursor->next;
1034        }
1035        targetCursor->next = 0;
1036        theLastTerm = targetCursor;
1037        targetCursor = dummy->next;
1038        delete dummy;
1039        return targetCursor;
1040    }
1041}
1042
1043termList
1044InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
1045{
1046    if ( aTermList == 0 )
1047        return 0;
1048    else {
1049        termList sourceCursor = aTermList;
1050        termList dummy = new term;
1051        termList targetCursor = dummy;
1052
1053        while ( sourceCursor ) {
1054            targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1055            targetCursor = targetCursor->next;
1056            sourceCursor = sourceCursor->next;
1057        }
1058        targetCursor->next = 0;
1059        theLastTerm = targetCursor;
1060        targetCursor = dummy->next;
1061        delete dummy;
1062        return targetCursor;
1063    }
1064}
1065
1066void
1067InternalPoly::freeTermList ( termList aTermList )
1068{
1069    termList cursor = aTermList;
1070
1071    while ( cursor ) {
1072        cursor = cursor->next;
1073        delete aTermList;
1074        aTermList = cursor;
1075    }
1076}
1077
1078void
1079InternalPoly::negateTermList ( termList terms )
1080{
1081    termList cursor = terms;
1082    while ( cursor ) {
1083        cursor->coeff = -cursor->coeff;
1084        cursor = cursor->next;
1085    }
1086}
1087
1088termList
1089InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
1090{
1091    termList theCursor = theList;
1092    termList aCursor = aList;
1093    termList predCursor = 0;
1094
1095    while ( theCursor && aCursor ) {
1096        if ( theCursor->exp == aCursor->exp ) {
1097            if ( negate )
1098                theCursor->coeff -= aCursor->coeff;
1099            else
1100                theCursor->coeff += aCursor->coeff;
1101            if ( theCursor->coeff.isZero() ) {
1102                if ( predCursor ) {
1103                    predCursor->next = theCursor->next;
1104                    delete theCursor;
1105                    theCursor = predCursor->next;
1106                }
1107                else {
1108                    theList = theList->next;
1109                    delete theCursor;
1110                    theCursor = theList;
1111                }
1112            }
1113            else {
1114                predCursor = theCursor;
1115                theCursor = theCursor->next;
1116            }
1117            aCursor = aCursor->next;
1118        }
1119        else if ( theCursor->exp < aCursor->exp ) {
1120            if ( negate )
1121                if ( predCursor ) {
1122                    predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1123                    predCursor = predCursor->next;
1124                }
1125                else {
1126                    theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1127                    predCursor = theList;
1128                }
1129            else
1130                if ( predCursor ) {
1131                    predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1132                    predCursor = predCursor->next;
1133                }
1134                else {
1135                    theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1136                    predCursor = theList;
1137                }
1138            aCursor = aCursor->next;
1139        }
1140        else {
1141            predCursor = theCursor;
1142            theCursor = theCursor->next;
1143        }
1144    }
1145    if ( aCursor ) {
1146        if ( predCursor )
1147            predCursor->next = copyTermList( aCursor, lastTerm, negate );
1148        else
1149            theList = copyTermList( aCursor, lastTerm, negate );
1150    }
1151    else if ( ! theCursor )
1152        lastTerm = predCursor;
1153
1154    return theList;
1155}
1156
1157void
1158InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
1159{
1160    while ( theCursor ) {
1161        theCursor->coeff *= coeff;
1162        theCursor->exp += exp;
1163        theCursor = theCursor->next;
1164    }
1165}
1166
1167termList
1168InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1169{
1170    termList theCursor = firstTerm;
1171    lastTerm = 0;
1172    termList dummy;
1173
1174    while ( theCursor ) {
1175        theCursor->coeff /= coeff;
1176        if ( theCursor->coeff.isZero() ) {
1177            if ( theCursor == firstTerm )
1178                firstTerm = theCursor->next;
1179            else
1180                lastTerm->next = theCursor->next;
1181            dummy = theCursor;
1182            theCursor = theCursor->next;
1183            delete dummy;
1184        }
1185        else {
1186            lastTerm = theCursor;
1187            theCursor = theCursor->next;
1188        }
1189    }
1190    return firstTerm;
1191}
1192
1193termList
1194InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1195{
1196    termList theCursor = firstTerm;
1197    lastTerm = 0;
1198    termList dummy;
1199
1200    while ( theCursor ) {
1201        theCursor->coeff.mod( coeff );
1202        if ( theCursor->coeff.isZero() ) {
1203            if ( theCursor == firstTerm )
1204                firstTerm = theCursor->next;
1205            else
1206                lastTerm->next = theCursor->next;
1207            dummy = theCursor;
1208            theCursor = theCursor-> next;
1209            delete dummy;
1210        }
1211        else {
1212            lastTerm = theCursor;
1213            theCursor = theCursor->next;
1214        }
1215    }
1216    return firstTerm;
1217}
1218
1219void
1220InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
1221{
1222    if ( last ) {
1223        last->next = new term( 0, coeff, exp );
1224        last = last->next;
1225    }
1226    else {
1227        first = new term( 0, coeff, exp );
1228        last = first;
1229    }
1230}
1231
1232termList
1233InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
1234{
1235    termList theCursor = theList;
1236    termList aCursor = aList;
1237    termList predCursor = 0;
1238    CanonicalForm coeff;
1239
1240    if ( negate )
1241        coeff = -c;
1242    else
1243        coeff = c;
1244
1245    while ( theCursor && aCursor ) {
1246        if ( theCursor->exp == aCursor->exp + exp ) {
1247            theCursor->coeff += aCursor->coeff * coeff;
1248            if ( theCursor->coeff.isZero() ) {
1249                if ( predCursor ) {
1250                    predCursor->next = theCursor->next;
1251                    delete theCursor;
1252                    theCursor = predCursor->next;
1253                }
1254                else {
1255                    theList = theList->next;
1256                    delete theCursor;
1257                    theCursor = theList;
1258                }
1259            }
1260            else {
1261                predCursor = theCursor;
1262                theCursor = theCursor->next;
1263            }
1264            aCursor = aCursor->next;
1265        }
1266        else if ( theCursor->exp < aCursor->exp + exp ) {
1267            if ( predCursor ) {
1268                predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1269                predCursor = predCursor->next;
1270            }
1271            else {
1272                theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1273                predCursor = theList;
1274            }
1275            aCursor = aCursor->next;
1276        }
1277        else {
1278            predCursor = theCursor;
1279            theCursor = theCursor->next;
1280        }
1281    }
1282    if ( aCursor ) {
1283        if ( predCursor ) {
1284            predCursor->next = copyTermList( aCursor, lastTerm );
1285            predCursor = predCursor->next;
1286        }
1287        else {
1288            theList = copyTermList( aCursor, lastTerm );
1289            predCursor = theList;
1290        }
1291        while ( predCursor ) {
1292            predCursor->exp += exp;
1293            predCursor->coeff *= coeff;
1294            predCursor = predCursor->next;
1295        }
1296    }
1297    else if ( ! theCursor )
1298        lastTerm = predCursor;
1299    return theList;
1300}
1301
1302termList
1303InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
1304{
1305    CanonicalForm coeff = redterms->coeff;
1306    CanonicalForm newcoeff;
1307    int newexp;
1308    int exp = redterms->exp;
1309    termList dummy;
1310    while ( first && ( first->exp >= exp ) ) {
1311        newcoeff = first->coeff / coeff;
1312        newexp = first->exp - exp;
1313        dummy = first;
1314        first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
1315        delete dummy;
1316    }
1317    return first;
1318}
Note: See TracBrowser for help on using the repository browser.