9#if defined(WINNT) && ! defined(__GNUC__)
34#define LIKELY(X) (__builtin_expect(!!(X), 1))
35#define UNLIKELY(X) (__builtin_expect(!!(X), 0))
38#define UNLIKELY(X) (X)
55 ASSERT( 0,
"ups, why do you initialize an empty poly" );
67 ASSERT( 0,
"ups there is something wrong in your code" );
91 cursor = cursor->
next;
167 if ( theCursor->
exp ==
i )
168 return theCursor->
coeff;
169 else if ( theCursor->
exp <
i )
172 theCursor = theCursor->
next;
182 aStream << 0 << aString;
189 ostrstream theStream;
190 if ( theCursor->
exp == 0 )
191 theCursor->
coeff.print( aStream, aString );
195 if ( theCursor->
exp != 1 )
196 aStream <<
'^' << theCursor->
exp << aString;
200 else if ( theCursor->
coeff.
sign() < 0 && (-theCursor->
coeff).isOne() )
202 aStream <<
'-' <<
var;
203 if ( theCursor->
exp != 1 )
204 aStream <<
'^' << theCursor->
exp << aString;
210 theStream <<
'*' <<
var;
211 if ( theCursor->
exp != 1 )
212 theStream <<
'^' << theCursor->
exp << aString << ends;
214 theStream << aString << ends;
215 theString = theStream.str();
216 theCursor->
coeff.print( aStream, theString );
219 theCursor = theCursor->
next;
220 if ( theCursor && ( theCursor->
coeff.
sign() >= 0 ) )
311 if ( first && first->
exp != 0 )
351 if ( first && first->
exp != 0 )
370 termList resultFirst = 0, resultLast = 0;
376 theCursor->
coeff, theCursor->
exp, resultLast,
false );
377 theCursor = theCursor->
next;
382 if ( resultFirst == 0 )
395 else if ( resultFirst->
exp == 0 )
433 termList resultFirst = 0, resultLast = 0;
439 theCursor->
coeff, theCursor->
exp, resultLast,
false );
440 theCursor = theCursor->
next;
445 if ( resultFirst == 0 )
458 else if ( resultFirst->
exp == 0 )
504 else dummy = dummy->
mulsame(
this );
517 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
533 while (first && ( first->
exp >=
exp ) )
536 newexp = first->
exp -
exp;
545 if ( resultfirst && resultfirst->
exp != 0 )
551 else if ( resultfirst )
562 ASSERT( 0,
"FATAL ERROR, PLEASE INFORM THE AUTHOR" );
570 if ( resultfirst && resultfirst->
exp != 0 )
572 else if ( resultfirst )
613 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
629 while (first && ( first->
exp >=
exp ) )
637 newcoeff=
reduce (newcoeff,
M);
638 newexp = first->
exp -
exp;
648 if ( resultfirst && resultfirst->
exp != 0 )
654 else if ( resultfirst )
665 ASSERT( 0,
"FATAL ERROR, PLEASE INFORM THE AUTHOR" );
673 if ( resultfirst && resultfirst->
exp != 0 )
675 else if ( resultfirst )
717 while (first && ( first->
exp >=
exp ) )
720 newexp = first->
exp -
exp;
727 if ( first && first->
exp != 0 )
750 if ( first && first->
exp != 0 )
776 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
784 while (first && ( first->
exp >=
exp ) )
787 newexp = first->
exp -
exp;
794 if ( resultfirst->
exp == 0 )
804 if ( first->
exp == 0 )
825 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
828 bool divideok =
true;
837 while (first && ( first->
exp >=
exp ) && divideok )
840 if ( divideok && dummycoeff.
isZero() )
842 newexp = first->
exp -
exp;
854 if ( resultfirst->
exp == 0 )
864 if ( first->
exp == 0 )
897 termList dummy, first,
last, resultfirst = 0, resultlast = 0;
900 bool divideok =
true;
906 while (first && ( first->
exp >=
exp ) && divideok )
914 if ( divideok && dummycoeff.
isZero() )
916 newexp = first->
exp -
exp;
929 if ( resultfirst->
exp == 0 )
939 if ( first->
exp == 0 )
1001 for ( ; cursor1 && cursor2; cursor1 = cursor1->
next, cursor2 = cursor2->
next )
1006 if ( (cursor1->
exp != cursor2->
exp) || (cursor1->
coeff != cursor2->
coeff) )
1008 if ( cursor1->
exp > cursor2->
exp )
1010 else if ( cursor1->
exp < cursor2->
exp )
1018 if ( cursor1 == cursor2 )
1020 else if ( cursor1 != 0 )
1054 cursor = cursor->
next;
1071 if (
last->exp == 0 )
1074 if (
last->coeff.isZero() )
1078 cursor = cursor->
next;
1128 cursor = cursor->
next;
1151 if (
last->exp == 0 )
1157 if (
last->coeff.isZero() )
1161 cursor = cursor->
next;
1197 else if ( c.
isOne() )
1234 else dummy = dummy->
mulcoeff( cc );
1285 if ( first && first->
exp != 0 )
1328 else dummy = dummy->
mulcoeff( cc );
1380 if ( first && first->
exp != 0 )
1457 if ( first && first->
exp != 0 )
1556 if ( first && first->
exp != 0 )
1634 if ( first && first->
exp != 0 )
1675 if ( quotfirst->
exp == 0 )
1712 bool divideok =
true;
1715 quotcursor = quotfirst =
new term;
1717 while ( cursor && divideok )
1720 divideok = divideok && crem.
isZero();
1725 quotcursor->
next =
new term( 0, cquot, cursor->
exp );
1726 quotcursor = quotcursor->
next;
1728 cursor = cursor->
next;
1731 quotcursor->
next = 0;
1734 cursor = quotfirst; quotfirst = quotfirst->
next;
delete cursor;
1736 if ( quotfirst->
exp == 0 )
1780 bool divideok =
true;
1783 quotcursor = quotfirst =
new term;
1785 while ( cursor && divideok )
1793 divideok = divideok && crem.
isZero();
1798 quotcursor->
next =
new term( 0, cquot, cursor->
exp );
1799 quotcursor = quotcursor->
next;
1801 cursor = cursor->
next;
1804 quotcursor->
next = 0;
1807 cursor = quotfirst; quotfirst = quotfirst->
next;
delete cursor;
1809 if ( quotfirst->
exp == 0 )
1840 while (
LIKELY(sourceCursor) )
1842 targetCursor->
next =
new term( 0, -sourceCursor->
coeff, sourceCursor->
exp );
1843 targetCursor = targetCursor->
next;
1844 sourceCursor = sourceCursor->
next;
1846 targetCursor->
next = 0;
1847 theLastTerm = targetCursor;
1848 targetCursor = dummy->
next;
1850 return targetCursor;
1858 while (
LIKELY(sourceCursor) )
1860 targetCursor->
next =
new term( 0, sourceCursor->
coeff, sourceCursor->
exp );
1861 targetCursor = targetCursor->
next;
1862 sourceCursor = sourceCursor->
next;
1864 targetCursor->
next = 0;
1865 theLastTerm = targetCursor;
1866 targetCursor = dummy->
next;
1868 return targetCursor;
1875 if ( aTermList == 0 )
1883 while ( sourceCursor )
1886 targetCursor = targetCursor->
next;
1887 sourceCursor = sourceCursor->
next;
1889 targetCursor->
next = 0;
1890 theLastTerm = targetCursor;
1891 targetCursor = dummy->
next;
1893 return targetCursor;
1904 cursor = cursor->
next;
1917 cursor = cursor->
next;
1929 while ( theCursor && aCursor )
1931 if ( theCursor->
exp == aCursor->
exp )
1938 predCursor->
next = theCursor->
next;
1940 theCursor = predCursor->
next;
1944 theList = theList->
next;
1946 theCursor = theList;
1951 predCursor = theCursor;
1952 theCursor = theCursor->
next;
1954 aCursor = aCursor->
next;
1956 else if ( theCursor->
exp < aCursor->
exp )
1961 predCursor = predCursor->
next;
1965 theList =
new term( theCursor, -aCursor->
coeff, aCursor->
exp );
1966 predCursor = theList;
1968 aCursor = aCursor->
next;
1972 predCursor = theCursor;
1973 theCursor = theCursor->
next;
1977 while ( theCursor && aCursor )
1979 if ( theCursor->
exp == aCursor->
exp )
1986 predCursor->
next = theCursor->
next;
1988 theCursor = predCursor->
next;
1992 theList = theList->
next;
1994 theCursor = theList;
1999 predCursor = theCursor;
2000 theCursor = theCursor->
next;
2002 aCursor = aCursor->
next;
2004 else if ( theCursor->
exp < aCursor->
exp )
2009 predCursor = predCursor->
next;
2013 theList =
new term( theCursor, aCursor->
coeff, aCursor->
exp );
2014 predCursor = theList;
2016 aCursor = aCursor->
next;
2020 predCursor = theCursor;
2021 theCursor = theCursor->
next;
2031 else if ( ! theCursor )
2040 while (
LIKELY(theCursor) )
2044 theCursor = theCursor->
next;
2055 while (
LIKELY(theCursor) )
2065 theCursor = theCursor->
next;
2071 theCursor = theCursor->
next;
2084 while (
LIKELY(theCursor) )
2094 theCursor = theCursor->
next;
2100 theCursor = theCursor->
next;
2125 theCursor = theCursor->
next;
2131 theCursor = theCursor->
next;
2154 theCursor = theCursor->
next;
2160 theCursor = theCursor->
next;
2194 while ( theCursor && aCursor )
2196 if ( theCursor->
exp == aCursor->
exp +
exp )
2203 predCursor->
next = theCursor->
next;
2205 theCursor = predCursor->
next;
2209 theList = theList->
next;
2211 theCursor = theList;
2216 predCursor = theCursor;
2217 theCursor = theCursor->
next;
2219 aCursor = aCursor->
next;
2221 else if ( theCursor->
exp < aCursor->
exp +
exp )
2226 predCursor = predCursor->
next;
2231 predCursor = theList;
2233 aCursor = aCursor->
next;
2237 predCursor = theCursor;
2238 theCursor = theCursor->
next;
2246 predCursor = predCursor->
next;
2251 predCursor = theList;
2253 while ( predCursor )
2257 predCursor = predCursor->
next;
2260 else if ( ! theCursor )
2273 while ( first && ( first->
exp >=
exp ) )
2276 newexp = first->
exp -
exp;
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
#define ASSERT(expression, message)
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
static InternalCF * basic(int value)
virtual class for internal CanonicalForm's
virtual InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
InternalCF * copyObject()
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
virtual InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
virtual InternalCF * dividecoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
virtual InternalCF * tryInvert(const CanonicalForm &, bool &)
virtual void print(OSTREAM &, char *) PVIRT_VOID("print")
virtual InternalCF * invert()
virtual int level() const
virtual InternalCF * mulsame(InternalCF *) PVIRT_INTCF("mulsame")
factory's class for integers
factory's class for polynomials
InternalCF * addsame(InternalCF *)
static termList divideTermList(termList, const CanonicalForm &, termList &)
static termList addTermList(termList, termList, termList &, bool negate)
InternalCF * mulcoeff(InternalCF *)
static termList reduceTermList(termList first, termList redterms, termList &last)
InternalCF * modsame(InternalCF *)
int degree()
int InternalPoly::degree ()
static void freeTermList(termList)
InternalCF * deepCopyObject() const
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
InternalCF * neg()
InternalCF * InternalPoly::neg ()
InternalCF * tryDivcoeff(InternalCF *, bool, const CanonicalForm &, bool &)
static const omBin InternalPoly_bin
static void mulTermList(termList, const CanonicalForm &, const int)
bool isUnivariate() const
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
int comparesame(InternalCF *)
comparesame(), comparecoeff() - compare with an InternalPoly.
InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
InternalCF * modulocoeff(InternalCF *, bool)
InternalCF * subsame(InternalCF *)
InternalCF * divcoeff(InternalCF *, bool)
InternalCF * modcoeff(InternalCF *, bool)
InternalCF * modulosame(InternalCF *)
static void negateTermList(termList)
static termList tryDivTermList(termList, const CanonicalForm &, termList &, const CanonicalForm &, bool &)
static termList mulAddTermList(termList theList, termList aList, const CanonicalForm &c, const int exp, termList &lastTerm, bool negate)
bool tryDivremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
InternalCF * dividesame(InternalCF *)
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
CanonicalForm coeff(int i)
CanonicalForm InternalPoly::coeff ( int i )
InternalCF * dividecoeff(InternalCF *, bool)
int comparecoeff(InternalCF *)
comparecoeff() always returns 1 since CO is defined to be larger than anything which is a coefficient...
CanonicalForm tailcoeff()
CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
static termList deepCopyTermList(termList, termList &)
InternalCF * divsame(InternalCF *)
InternalCF * addcoeff(InternalCF *)
InternalCF * subcoeff(InternalCF *, bool)
bool tryDivremsamet(InternalCF *, InternalCF *&, InternalCF *&, const CanonicalForm &, bool &)
static termList modTermList(termList, const CanonicalForm &, termList &)
static termList copyTermList(termList, termList &, bool negate=false)
static void appendTermList(termList &, termList &, const CanonicalForm &, const int)
static termList divTermList(termList, const CanonicalForm &, termList &)
InternalCF * mulsame(InternalCF *)
InternalCF * tryInvert(const CanonicalForm &, bool &)
InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
int sign() const
int InternalPoly::sign () const
InternalCF * tryDivsame(InternalCF *, const CanonicalForm &, bool &)
factory's class for variables
static const omBin term_bin
const Variable & v
< [in] a sqrfree bivariate poly
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Factory's internal CanonicalForm's.
Factory's internal integers.
Factory's internal polynomials.
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
gmp_float exp(const gmp_float &a)
#define omGetSpecBin(size)
void setReduce(const Variable &alpha, bool reduce)
bool getReduce(const Variable &alpha)
InternalPoly * getInternalMipo(const Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)