9 #if defined(WINNT) && ! defined(__GNUC__) 13 #include <strstream.h> 47 ASSERT( 0,
"ups, why do you initialize an empty poly" );
53 firstTerm =
new term( 0, c, e );
59 ASSERT( 0,
"ups there is something wrong in your code" );
95 cursor = cursor->
next;
171 if ( theCursor->
exp == i )
172 return theCursor->
coeff;
173 else if ( theCursor->
exp < i )
176 theCursor = theCursor->
next;
186 aStream << 0 << aString;
193 ostrstream theStream;
194 if ( theCursor->
exp == 0 )
199 if ( theCursor->
exp != 1 )
200 aStream <<
'^' << theCursor->
exp << aString;
206 aStream <<
'-' <<
var;
207 if ( theCursor->
exp != 1 )
208 aStream <<
'^' << theCursor->
exp << aString;
214 theStream <<
'*' <<
var;
215 if ( theCursor->
exp != 1 )
216 theStream <<
'^' << theCursor->
exp << aString << ends;
218 theStream << aString << ends;
219 theString = theStream.str();
223 theCursor = theCursor->
next;
224 if ( theCursor && ( theCursor->
coeff.
sign() >= 0 ) )
315 if ( first && first->
exp != 0 )
355 if ( first && first->
exp != 0 )
374 termList resultFirst = 0, resultLast = 0;
380 theCursor->
coeff, theCursor->
exp, resultLast,
false );
381 theCursor = theCursor->
next;
386 if ( resultFirst == 0 )
399 else if ( resultFirst->
exp == 0 )
437 termList resultFirst = 0, resultLast = 0;
443 theCursor->
coeff, theCursor->
exp, resultLast,
false );
444 theCursor = theCursor->
next;
449 if ( resultFirst == 0 )
462 else if ( resultFirst->
exp == 0 )
508 else dummy = dummy->
mulsame(
this );
521 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
537 while (first && ( first->
exp >= exp ) )
540 newexp = first->
exp -
exp;
549 if ( resultfirst && resultfirst->
exp != 0 )
555 else if ( resultfirst )
566 ASSERT( 0,
"FATAL ERROR, PLEASE INFORM THE AUTHOR" );
574 if ( resultfirst && resultfirst->
exp != 0 )
576 else if ( resultfirst )
617 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
633 while (first && ( first->
exp >= exp ) )
641 newcoeff=
reduce (newcoeff, M);
642 newexp = first->
exp -
exp;
652 if ( resultfirst && resultfirst->
exp != 0 )
658 else if ( resultfirst )
669 ASSERT( 0,
"FATAL ERROR, PLEASE INFORM THE AUTHOR" );
677 if ( resultfirst && resultfirst->
exp != 0 )
679 else if ( resultfirst )
721 while (first && ( first->
exp >= exp ) )
724 newexp = first->
exp -
exp;
731 if ( first && first->
exp != 0 )
754 if ( first && first->
exp != 0 )
780 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
788 while (first && ( first->
exp >= exp ) )
791 newexp = first->
exp -
exp;
798 if ( resultfirst->
exp == 0 )
808 if ( first->
exp == 0 )
829 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
832 bool divideok =
true;
841 while (first && ( first->
exp >= exp ) && divideok )
843 divideok =
divremt( first->
coeff, coeff, newcoeff, dummycoeff );
844 if ( divideok && dummycoeff.
isZero() )
846 newexp = first->
exp -
exp;
858 if ( resultfirst->
exp == 0 )
868 if ( first->
exp == 0 )
901 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
904 bool divideok =
true;
910 while (first && ( first->
exp >= exp ) && divideok )
912 divideok =
tryDivremt( first->
coeff, coeff, newcoeff, dummycoeff, M, fail );
918 if ( divideok && dummycoeff.
isZero() )
920 newexp = first->
exp -
exp;
933 if ( resultfirst->
exp == 0 )
943 if ( first->
exp == 0 )
1004 termList cursor2 = apoly->firstTerm;
1005 for ( ; cursor1 && cursor2; cursor1 = cursor1->
next, cursor2 = cursor2->
next )
1010 if ( (cursor1->
exp != cursor2->exp) || (cursor1->
coeff != cursor2->coeff) )
1012 if ( cursor1->
exp > cursor2->exp )
1014 else if ( cursor1->
exp < cursor2->exp )
1016 else if ( cursor1->
coeff > cursor2->coeff )
1022 if ( cursor1 == cursor2 )
1024 else if ( cursor1 != 0 )
1058 cursor = cursor->
next;
1075 if ( last->
exp == 0 )
1081 while ( cursor->
next != last )
1082 cursor = cursor->
next;
1132 cursor = cursor->
next;
1155 if ( last->
exp == 0 )
1164 while ( cursor->
next != last )
1165 cursor = cursor->
next;
1201 else if ( c.isOne() )
1238 else dummy = dummy->
mulcoeff( cc );
1289 if ( first && first->
exp != 0 )
1332 else dummy = dummy->
mulcoeff( cc );
1384 if ( first && first->
exp != 0 )
1461 if ( first && first->
exp != 0 )
1560 if ( first && first->
exp != 0 )
1586 ASSERT( ! c.isZero(),
"divide by zero!" );
1600 ASSERT( ! c.isZero(),
"divide by zero!" );
1638 if ( first && first->
exp != 0 )
1675 ASSERT( ! c.isZero(),
"divide by zero!" );
1679 if ( quotfirst->exp == 0 )
1712 ASSERT( ! c.isZero(),
"divide by zero!" );
1716 bool divideok =
true;
1719 quotcursor = quotfirst =
new term;
1721 while ( cursor && divideok )
1724 divideok = divideok && crem.
isZero();
1729 quotcursor->next =
new term( 0, cquot, cursor->
exp );
1730 quotcursor = quotcursor->next;
1732 cursor = cursor->
next;
1735 quotcursor->
next = 0;
1738 cursor = quotfirst; quotfirst = quotfirst->
next;
delete cursor;
1740 if ( quotfirst->exp == 0 )
1780 ASSERT( ! c.isZero(),
"divide by zero!" );
1784 bool divideok =
true;
1787 quotcursor = quotfirst =
new term;
1789 while ( cursor && divideok )
1797 divideok = divideok && crem.
isZero();
1802 quotcursor->next =
new term( 0, cquot, cursor->
exp );
1803 quotcursor = quotcursor->next;
1805 cursor = cursor->
next;
1808 quotcursor->
next = 0;
1811 cursor = quotfirst; quotfirst = quotfirst->
next;
delete cursor;
1813 if ( quotfirst->exp == 0 )
1836 if ( aTermList == 0 )
1844 while ( sourceCursor )
1846 targetCursor->
next =
new term( 0, -sourceCursor->
coeff, sourceCursor->
exp );
1847 targetCursor = targetCursor->
next;
1848 sourceCursor = sourceCursor->
next;
1850 targetCursor->
next = 0;
1851 theLastTerm = targetCursor;
1852 targetCursor = dummy->
next;
1854 return targetCursor;
1862 while ( sourceCursor )
1864 targetCursor->
next =
new term( 0, sourceCursor->
coeff, sourceCursor->
exp );
1865 targetCursor = targetCursor->
next;
1866 sourceCursor = sourceCursor->
next;
1868 targetCursor->
next = 0;
1869 theLastTerm = targetCursor;
1870 targetCursor = dummy->
next;
1872 return targetCursor;
1879 if ( aTermList == 0 )
1887 while ( sourceCursor )
1890 targetCursor = targetCursor->
next;
1891 sourceCursor = sourceCursor->
next;
1893 targetCursor->
next = 0;
1894 theLastTerm = targetCursor;
1895 targetCursor = dummy->
next;
1897 return targetCursor;
1908 cursor = cursor->
next;
1921 cursor = cursor->
next;
1932 while ( theCursor && aCursor )
1934 if ( theCursor->
exp == aCursor->
exp )
1944 predCursor->
next = theCursor->
next;
1946 theCursor = predCursor->
next;
1950 theList = theList->
next;
1952 theCursor = theList;
1957 predCursor = theCursor;
1958 theCursor = theCursor->
next;
1960 aCursor = aCursor->
next;
1962 else if ( theCursor->
exp < aCursor->
exp )
1968 predCursor = predCursor->
next;
1972 theList =
new term( theCursor, -aCursor->
coeff, aCursor->
exp );
1973 predCursor = theList;
1979 predCursor = predCursor->
next;
1983 theList =
new term( theCursor, aCursor->
coeff, aCursor->
exp );
1984 predCursor = theList;
1986 aCursor = aCursor->
next;
1990 predCursor = theCursor;
1991 theCursor = theCursor->
next;
2001 else if ( ! theCursor )
2002 lastTerm = predCursor;
2014 theCursor = theCursor->
next;
2030 if ( theCursor == firstTerm )
2031 firstTerm = theCursor->
next;
2035 theCursor = theCursor->
next;
2040 lastTerm = theCursor;
2041 theCursor = theCursor->
next;
2059 if ( theCursor == firstTerm )
2060 firstTerm = theCursor->
next;
2064 theCursor = theCursor->
next;
2069 lastTerm = theCursor;
2070 theCursor = theCursor->
next;
2090 if ( theCursor == firstTerm )
2091 firstTerm = theCursor->
next;
2095 theCursor = theCursor->
next;
2100 lastTerm = theCursor;
2101 theCursor = theCursor->
next;
2119 if ( theCursor == firstTerm )
2120 firstTerm = theCursor->
next;
2124 theCursor = theCursor->
next;
2129 lastTerm = theCursor;
2130 theCursor = theCursor->
next;
2141 last->
next =
new term( 0, coeff, exp );
2146 first =
new term( 0, coeff, exp );
2164 while ( theCursor && aCursor )
2166 if ( theCursor->
exp == aCursor->
exp + exp )
2173 predCursor->
next = theCursor->
next;
2175 theCursor = predCursor->
next;
2179 theList = theList->
next;
2181 theCursor = theList;
2186 predCursor = theCursor;
2187 theCursor = theCursor->
next;
2189 aCursor = aCursor->
next;
2191 else if ( theCursor->
exp < aCursor->
exp + exp )
2195 predCursor->
next =
new term( theCursor, aCursor->
coeff * coeff, aCursor->
exp + exp );
2196 predCursor = predCursor->
next;
2200 theList =
new term( theCursor, aCursor->
coeff * coeff, aCursor->
exp + exp );
2201 predCursor = theList;
2203 aCursor = aCursor->
next;
2207 predCursor = theCursor;
2208 theCursor = theCursor->
next;
2216 predCursor = predCursor->
next;
2221 predCursor = theList;
2223 while ( predCursor )
2227 predCursor = predCursor->
next;
2230 else if ( ! theCursor )
2231 lastTerm = predCursor;
2243 while ( first && ( first->
exp >= exp ) )
2246 newexp = first->
exp -
exp;
friend class InternalInteger
InternalCF * neg()
InternalCF * InternalPoly::neg ()
static void mulTermList(termList, const CanonicalForm &, const int)
int comparesame(InternalCF *)
comparesame(), comparecoeff() - compare with an InternalPoly.
InternalCF * mulsame(InternalCF *)
virtual bool isOne() const
bool InternalCF::isOne, isZero () const
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
static void negateTermList(termList)
static termList modTermList(termList, const CanonicalForm &, termList &)
InternalCF * tryDivsame(InternalCF *, const CanonicalForm &, bool &)
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
InternalCF * dividecoeff(InternalCF *, bool)
int sign() const
int InternalPoly::sign () const
factory's class for variables
virtual InternalCF * tryInvert(const CanonicalForm &, bool &)
static void appendTermList(termList &, termList &, const CanonicalForm &, const int)
InternalCF * divsame(InternalCF *)
static termList divideTermList(termList, const CanonicalForm &, termList &)
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
InternalCF * copyObject()
CanonicalForm tailcoeff()
CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
InternalCF * modulocoeff(InternalCF *, bool)
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
InternalCF * deepCopyObject() const
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
static const omBin InternalPoly_bin
virtual class for internal CanonicalForm's
InternalCF * tryInvert(const CanonicalForm &, bool &)
InternalCF * subsame(InternalCF *)
virtual int level() const
bool isUnivariate() const
InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
InternalCF * dividesame(InternalCF *)
CanonicalForm coeff(int i)
CanonicalForm InternalPoly::coeff ( int i )
static termList divTermList(termList, const CanonicalForm &, termList &)
static termList deepCopyTermList(termList, termList &)
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
InternalCF * tryDivcoeff(InternalCF *, bool, const CanonicalForm &, bool &)
InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
static termList addTermList(termList, termList, termList &, bool negate)
virtual CanonicalForm coeff(int i)
CanonicalForm InternalCF::coeff ( int i )
void setReduce(const Variable &alpha, bool reduce)
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
bool getReduce(const Variable &alpha)
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
factory's class for polynomials
virtual InternalCF * dividecoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
static InternalCF * basic(long value)
InternalCF * modulosame(InternalCF *)
InternalCF * modsame(InternalCF *)
virtual InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
static void freeTermList(termList)
void print(OSTREAM &, char *)
static termList tryDivTermList(termList, const CanonicalForm &, termList &, const CanonicalForm &, bool &)
InternalPoly * getInternalMipo(const Variable &alpha)
static termList mulAddTermList(termList theList, termList aList, const CanonicalForm &c, const int exp, termList &lastTerm, bool negate)
static const omBin term_bin
#define omGetSpecBin(size)
Factory's internal polynomials.
const Variable & v
< [in] a sqrfree bivariate poly
virtual InternalCF * invert()
InternalCF * modcoeff(InternalCF *, bool)
long imm2int(const InternalCF *const imm)
static termList copyTermList(termList, termList &, bool negate=false)
InternalCF * divcoeff(InternalCF *, bool)
int degree()
int InternalPoly::degree ()
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int...
InternalCF * addsame(InternalCF *)
static termList reduceTermList(termList first, termList redterms, termList &last)
bool tryDivremsamet(InternalCF *, InternalCF *&, InternalCF *&, const CanonicalForm &, bool &)
Factory's internal CanonicalForm's.
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
#define ASSERT(expression, message)
virtual InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
virtual InternalCF * mulsame(InternalCF *) PVIRT_INTCF("mulsame")
factory's class for integers
bool tryDivremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
InternalCF * mulcoeff(InternalCF *)
int comparecoeff(InternalCF *)
comparecoeff() always returns 1 since CO is defined to be larger than anything which is a coefficient...
Factory's internal integers.
InternalCF * addcoeff(InternalCF *)
InternalCF * subcoeff(InternalCF *, bool)