source: git/factory/int_poly.cc @ 6b503c

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