source: git/factory/int_poly.cc @ cd86ac

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