Loading...
Searching...
No Matches
int_poly.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
#include "config.h"
#ifndef NOSTREAMIO
#include <string.h>
#if defined(WINNT) && ! defined(__GNUC__)
#include <strstrea.h>
#else
#if __GNUC__ < 3
#include <strstream.h>
#else
#include <strstream>
using namespace std;
#endif
#endif
#endif /* NOSTREAMIO */
#include "cf_assert.h"
#include "cf_defs.h"
#include "cf_factory.h"
#include "cfUnivarGcd.h"
#include "int_cf.h"
#include "int_int.h"
#include "int_poly.h"
#include "canonicalform.h"
#include "variable.h"
#include "imm.h"
#ifdef __GNUC__
#define LIKELY(X) (__builtin_expect(!!(X), 1))
#define UNLIKELY(X) (__builtin_expect(!!(X), 0))
#else
#define LIKELY(X) (X)
#define UNLIKELY(X) (X)
#endif
#ifdef HAVE_OMALLOC
const omBin term::term_bin = omGetSpecBin(sizeof(term));
const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly));
#endif
InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
{
firstTerm = first;
lastTerm = last;
var = v;
}
InternalPoly::InternalPoly()
{
ASSERT( 0, "ups, why do you initialize an empty poly" );
}
InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
{
var = v;
firstTerm = new term( 0, c, e );
lastTerm = firstTerm;
}
InternalPoly::InternalPoly( const InternalPoly& ):InternalCF()
{
ASSERT( 0, "ups there is something wrong in your code" );
}
InternalPoly::~InternalPoly()
{
freeTermList( firstTerm );
}
InternalCF*
InternalPoly::deepCopyObject() const
{
termList first, last;
first = deepCopyTermList( firstTerm, last );
return new InternalPoly( first, last, var );
}
bool
InternalPoly::isUnivariate() const
{
termList cursor = firstTerm;
while ( cursor )
{
if ( ! cursor->coeff.inCoeffDomain() )
return false;
cursor = cursor->next;
}
return true;
}
/** int InternalPoly::degree ()
* @sa CanonicalForm::sign ()
**/
int
InternalPoly::degree ()
{
return firstTerm->exp;
}
/** int InternalPoly::sign () const
* @sa CanonicalForm::sign()
**/
int
InternalPoly::sign () const
{
return firstTerm->coeff.sign();
}
/**
* @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::Lc (), InternalPoly::LC ()
**/
CanonicalForm
InternalPoly::lc ()
{
return firstTerm->coeff.lc();
}
/**
* @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::LC ()
**/
CanonicalForm
InternalPoly::Lc ()
{
return firstTerm->coeff.Lc();
}
/**
* @sa CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::Lc ()
**/
CanonicalForm
InternalPoly::LC ()
{
return firstTerm->coeff;
}
/** CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
* @sa CanonicalForm::tailcoeff(), taildegree()
**/
CanonicalForm
InternalPoly::tailcoeff ()
{
return lastTerm->coeff;
}
int
InternalPoly::taildegree ()
{
return lastTerm->exp;
}
/** CanonicalForm InternalPoly::coeff ( int i )
* @sa CanonicalForm::operator []()
**/
CanonicalForm
InternalPoly::coeff ( int i )
{
termList theCursor = firstTerm;
while ( theCursor )
{
if ( theCursor->exp == i )
return theCursor->coeff;
else if ( theCursor->exp < i )
return CanonicalForm( 0 );
else
theCursor = theCursor->next;
}
return CanonicalForm( 0 );
}
#ifndef NOSTREAMIO
void
InternalPoly::print(OSTREAM &aStream, char * aString )
{
if ( ! firstTerm )
aStream << 0 << aString;
else
{
char * theString;
termList theCursor = firstTerm;
while ( theCursor )
{
ostrstream theStream;
if ( theCursor->exp == 0 )
theCursor->coeff.print( aStream, aString );
else if ( theCursor->coeff.isOne() )
{
aStream << var;
if ( theCursor->exp != 1 )
aStream << '^' << theCursor->exp << aString;
else
aStream << aString;
}
else if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() )
{
aStream << '-' << var;
if ( theCursor->exp != 1 )
aStream << '^' << theCursor->exp << aString;
else
aStream << aString;
}
else
{
theStream << '*' << var;
if ( theCursor->exp != 1 )
theStream << '^' << theCursor->exp << aString << ends;
else
theStream << aString << ends; // results from error in GNU strstream
theString = theStream.str();
theCursor->coeff.print( aStream, theString );
theStream.freeze(0);//delete [] theString;
}
theCursor = theCursor->next;
if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
aStream << '+';
}
}
}
#endif /* NOSTREAMIO */
/** InternalCF * InternalPoly::neg ()
* @sa CanonicalForm::operator -()
**/
InternalCF *
InternalPoly::neg ()
{
if ( getRefCount() <= 1 )
{
negateTermList( firstTerm );
return this;
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last, true );
return new InternalPoly( first, last, var );
}
}
InternalCF*
InternalPoly::invert()
{
if ( inExtension() && getReduce( var ) )
{
setReduce( var, false );
CanonicalForm a( this->copyObject() );
CanonicalForm b = getMipo( var );
CanonicalForm u, v;
CanonicalForm g = extgcd( a, b, u, v );
setReduce( var, true );
return u.getval();
}
else
return CFFactory::basic( 0 );
}
InternalCF*
InternalPoly::tryInvert ( const CanonicalForm& M, bool& fail)
{
if ( inExtension() && !getReduce ( var ) )
{
CanonicalForm b, inverse;
CanonicalForm F ( this ->copyObject() );
Variable a = M.mvar();
Variable x = Variable(1);
F= mod (F, M); //reduce mod M
CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b );
if(!g.isOne())
fail = true;
else
inverse = replacevar( inverse, x, a ); // change back to alg var
CanonicalForm test= mod (inverse*F, M);
return inverse.getval();
}
else
return CFFactory::basic( 0 );
}
InternalCF*
InternalPoly::addsame( InternalCF* aCoeff )
{
InternalPoly * aPoly = (InternalPoly*)aCoeff;
if ( getRefCount() <= 1 )
{
firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = addTermList( first, aPoly->firstTerm, last, false );
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
return CFFactory::basic( 0 );
}
}
InternalCF*
InternalPoly::subsame( InternalCF* aCoeff )
{
InternalPoly * aPoly = (InternalPoly*)aCoeff;
if ( getRefCount() <= 1 )
{
firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = addTermList( first, aPoly->firstTerm, last, true );
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
return CFFactory::basic( 0 );
}
}
InternalCF*
InternalPoly::mulsame( InternalCF* aCoeff )
{
if (is_imm(aCoeff)) return mulcoeff(aCoeff);
InternalPoly *aPoly = (InternalPoly*)aCoeff;
termList resultFirst = 0, resultLast = 0;
termList theCursor = firstTerm;
while ( theCursor )
{
resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
theCursor->coeff, theCursor->exp, resultLast, false );
theCursor = theCursor->next;
}
if ( inExtension() && getReduce( var ) )
{
resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
if ( resultFirst == 0 )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic(0);
}
else
{
decRefCount();
return CFFactory::basic(0);
}
}
else if ( resultFirst->exp == 0 )
{
if ( getRefCount() <= 1 )
{
InternalCF * res = resultFirst->coeff.getval();
delete resultFirst;
delete this;
return res;
}
else
{
decRefCount();
InternalCF * res = resultFirst->coeff.getval();
delete resultFirst;
return res;
}
}
}
if ( getRefCount() <= 1 )
{
freeTermList( firstTerm );
firstTerm = resultFirst;
lastTerm = resultLast;
return this;
}
else
{
decRefCount();
return new InternalPoly( resultFirst, resultLast, var );
}
}
InternalCF*
InternalPoly::tryMulsame( InternalCF* aCoeff, const CanonicalForm& M)
{
if (is_imm(aCoeff))
return mulcoeff(aCoeff);
InternalPoly *aPoly = (InternalPoly*)aCoeff;
termList resultFirst = 0, resultLast = 0;
termList theCursor = firstTerm;
while ( theCursor )
{
resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
theCursor->coeff, theCursor->exp, resultLast, false );
theCursor = theCursor->next;
}
if ( inExtension() && !getReduce( var ) )
{
resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())->firstTerm, resultLast);
if ( resultFirst == 0 )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic(0);
}
else
{
decRefCount();
return CFFactory::basic(0);
}
}
else if ( resultFirst->exp == 0 )
{
if ( getRefCount() <= 1 )
{
InternalCF * res = resultFirst->coeff.getval();
delete resultFirst;
delete this;
return res;
}
else
{
decRefCount();
InternalCF * res = resultFirst->coeff.getval();
delete resultFirst;
return res;
}
}
}
if ( getRefCount() <= 1 )
{
freeTermList( firstTerm );
firstTerm = resultFirst;
lastTerm = resultLast;
return this;
}
else
{
decRefCount();
return new InternalPoly( resultFirst, resultLast, var );
}
}
InternalCF*
InternalPoly::dividesame( InternalCF* aCoeff )
{
return divsame( aCoeff );
}
InternalCF*
InternalPoly::divsame( InternalCF* aCoeff )
{
if ( inExtension() && getReduce( var ) )
{
InternalCF * dummy = aCoeff->invert();
if (is_imm(dummy)) dummy=this->mulsame(dummy);
else dummy = dummy->mulsame( this );
if ( getRefCount() <= 1 )
{
delete this;
return dummy;
}
else
{
decRefCount();
return dummy;
}
}
InternalPoly *aPoly = (InternalPoly*)aCoeff;
termList dummy, first, last, resultfirst = 0, resultlast = 0;
CanonicalForm coeff, newcoeff;
int exp, newexp;
bool singleObject;
if ( getRefCount() <= 1 )
{
first = firstTerm; last = lastTerm; singleObject = true;
}
else
{
first = copyTermList( firstTerm, last ); singleObject = false;
decRefCount();
}
coeff = aPoly->firstTerm->coeff;
exp = aPoly->firstTerm->exp;
while (first && ( first->exp >= exp ) )
{
newcoeff = first->coeff / coeff;
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
delete dummy;
appendTermList( resultfirst, resultlast, newcoeff, newexp );
}
freeTermList( first );
if ( singleObject )
{
if ( resultfirst && resultfirst->exp != 0 )
{
firstTerm = resultfirst;
lastTerm = resultlast;
return this;
}
else if ( resultfirst )
{
InternalCF * res = resultfirst->coeff.getval();
delete resultfirst;
firstTerm = 0;
delete this;
return res;
}
else
{
// this should not happen (evtl use assertion)
ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
firstTerm = 0;
delete this;
return CFFactory::basic( 0 );
}
}
else
{
if ( resultfirst && resultfirst->exp != 0 )
return new InternalPoly( resultfirst, resultlast, var );
else if ( resultfirst )
{
InternalCF * res = resultfirst->coeff.getval();
delete resultfirst;
return res;
}
else
return CFFactory::basic( 0 );
}
}
InternalCF*
InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail )
{
if ( inExtension() && !getReduce( var ) )
{
InternalCF * dummy = aCoeff->tryInvert(M, fail);
if (fail)
return CFFactory::basic( 0 );
if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M);
else dummy = dummy->tryMulsame( this, M);
if (fail)
{
if (getRefCount() <= 1)
delete this;
else
decRefCount();
return dummy;
}
if ( getRefCount() <= 1 )
{
delete this;
return dummy;
}
else
{
decRefCount();
return dummy;
}
}
InternalPoly *aPoly = (InternalPoly*)aCoeff;
termList dummy, first, last, resultfirst = 0, resultlast = 0;
CanonicalForm coeff, newcoeff;
int exp, newexp;
bool singleObject;
if ( getRefCount() <= 1 )
{
first = firstTerm; last = lastTerm; singleObject = true;
}
else
{
first = copyTermList( firstTerm, last ); singleObject = false;
decRefCount();
}
coeff = aPoly->firstTerm->coeff;
exp = aPoly->firstTerm->exp;
while (first && ( first->exp >= exp ) )
{
newcoeff= first->coeff.tryDiv (coeff, M, fail);
if (fail)
{
freeTermList (first);
return CFFactory::basic (0);
}
newcoeff= reduce (newcoeff, M);
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
delete dummy;
if (!newcoeff.isZero())
appendTermList( resultfirst, resultlast, newcoeff, newexp );
}
freeTermList( first );
if ( singleObject )
{
if ( resultfirst && resultfirst->exp != 0 )
{
firstTerm = resultfirst;
lastTerm = resultlast;
return this;
}
else if ( resultfirst )
{
InternalCF * res = resultfirst->coeff.getval();
delete resultfirst;
firstTerm = 0;
delete this;
return res;
}
else
{
// this should not happen (evtl use assertion)
ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
firstTerm = 0;
delete this;
return CFFactory::basic( 0 );
}
}
else
{
if ( resultfirst && resultfirst->exp != 0 )
return new InternalPoly( resultfirst, resultlast, var );
else if ( resultfirst )
{
InternalCF * res = resultfirst->coeff.getval();
delete resultfirst;
return res;
}
else
return CFFactory::basic( 0 );
}
}
InternalCF*
InternalPoly::modulosame( InternalCF* aCoeff )
{
return modsame( aCoeff );
}
InternalCF*
InternalPoly::modsame( InternalCF* aCoeff )
{
if ( inExtension() && getReduce( var ) )
{
if ( deleteObject() ) delete this;
return CFFactory::basic( 0 );
}
InternalPoly *aPoly = (InternalPoly*)aCoeff;
termList dummy, first, last;
CanonicalForm coeff, newcoeff;
int exp, newexp;
bool singleObject;
if ( getRefCount() <= 1 )
{
first = firstTerm; last = lastTerm; singleObject = true;
}
else
{
first = copyTermList( firstTerm, last ); singleObject = false;
decRefCount();
}
coeff = aPoly->firstTerm->coeff;
exp = aPoly->firstTerm->exp;
while (first && ( first->exp >= exp ) )
{
newcoeff = first->coeff / coeff;
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
delete dummy;
}
if ( singleObject )
{
if ( first && first->exp != 0 )
{
firstTerm = first;
lastTerm = last;
return this;
}
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
firstTerm = 0;
delete this;
return res;
}
else
{
firstTerm = 0;
delete this;
return CFFactory::basic( 0 );
}
}
else
{
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
return CFFactory::basic( 0 );
}
}
void
InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
{
if ( inExtension() && getReduce( var ) )
{
InternalCF * dummy = acoeff->invert();
quot = dummy->mulsame( this );
rem = CFFactory::basic( 0 );
}
else
{
InternalPoly *aPoly = (InternalPoly*)acoeff;
termList dummy, first, last, resultfirst = 0, resultlast = 0;
CanonicalForm coeff, newcoeff;
int exp, newexp;
first = copyTermList( firstTerm, last );
coeff = aPoly->firstTerm->coeff;
exp = aPoly->firstTerm->exp;
while (first && ( first->exp >= exp ) )
{
newcoeff = first->coeff / coeff;
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
delete dummy;
appendTermList( resultfirst, resultlast, newcoeff, newexp );
}
if ( resultfirst )
if ( resultfirst->exp == 0 )
{
quot = resultfirst->coeff.getval();
delete resultfirst;
}
else
quot = new InternalPoly( resultfirst, resultlast, var );
else
quot = CFFactory::basic( 0 );
if ( first )
if ( first->exp == 0 )
{
rem = first->coeff.getval();
delete first;
}
else
rem = new InternalPoly( first, last, var );
else
rem = CFFactory::basic( 0 );
}
}
bool
InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
{
if ( inExtension() && getReduce( var ) )
{
divremsame( acoeff, quot, rem );
return true;
}
InternalPoly *aPoly = (InternalPoly*)acoeff;
termList dummy, first, last, resultfirst = 0, resultlast = 0;
CanonicalForm coeff, newcoeff, dummycoeff;
int exp, newexp;
bool divideok = true;
// if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
// return false;
first = copyTermList( firstTerm, last );
coeff = aPoly->firstTerm->coeff;
exp = aPoly->firstTerm->exp;
while (first && ( first->exp >= exp ) && divideok )
{
divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff );
if ( divideok && dummycoeff.isZero() )
{
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
delete dummy;
appendTermList( resultfirst, resultlast, newcoeff, newexp );
}
else
divideok = false;
}
if ( divideok )
{
if ( resultfirst )
if ( resultfirst->exp == 0 )
{
quot = resultfirst->coeff.getval();
delete resultfirst;
}
else
quot = new InternalPoly( resultfirst, resultlast, var );
else
quot = CFFactory::basic( 0 );
if ( first )
if ( first->exp == 0 )
{
rem = first->coeff.getval();
delete first;
}
else
rem = new InternalPoly( first, last, var );
else
rem = CFFactory::basic( 0 );
}
else
{
freeTermList( resultfirst );
freeTermList( first );
}
return divideok;
}
bool
InternalPoly::tryDivremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem, const CanonicalForm& M, bool& fail)
{
if (inExtension() && !getReduce (var))
{
InternalCF * dummy = acoeff->tryInvert(M, fail);
if (fail)
return false;
quot = dummy->tryMulsame( this, M);
rem = CFFactory::basic( 0 );
if (fail)
return false;
return true;
}
InternalPoly *aPoly = (InternalPoly*)acoeff;
termList dummy, first, last, resultfirst = 0, resultlast = 0;
CanonicalForm coeff, newcoeff, dummycoeff;
int exp, newexp;
bool divideok = true;
first = copyTermList( firstTerm, last );
coeff = aPoly->firstTerm->coeff;
exp = aPoly->firstTerm->exp;
while (first && ( first->exp >= exp ) && divideok )
{
divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail );
if (fail)
{
freeTermList (first);
return false;
}
if ( divideok && dummycoeff.isZero() )
{
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
delete dummy;
if (!newcoeff.isZero())
appendTermList( resultfirst, resultlast, newcoeff, newexp );
}
else
divideok = false;
}
if ( divideok )
{
if ( resultfirst )
if ( resultfirst->exp == 0 )
{
quot = resultfirst->coeff.getval();
delete resultfirst;
}
else
quot = new InternalPoly( resultfirst, resultlast, var );
else
quot = CFFactory::basic( 0 );
if ( first )
if ( first->exp == 0 )
{
rem = first->coeff.getval();
delete first;
}
else
{
if (first->coeff.isZero())
{
rem= CFFactory::basic (0);
delete first;
}
else
rem = new InternalPoly( first, last, var );
}
else
rem = CFFactory::basic( 0 );
}
else
{
freeTermList( resultfirst );
freeTermList( first );
}
return divideok;
}
/**
* comparesame(), comparecoeff() - compare with an
* InternalPoly.
*
* comparesame() compares the coefficient vectors of f=CO and
* g=acoeff w.r.t to a lexicographic order in the following way:
* f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
* i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
* ii) g[i] occurs in g (i.e. is not equal to zero) and
* f[i] does not occur in f or f[i] < g[i] if f[i] occurs
* where f[i] denotes the coefficient to the power x^i of f.
*
* As usual, comparesame() returns 1 if CO is larger than c, 0 if
* CO equals c, and -1 if CO is less than c. However, this
* function is optimized to test on equality since this is its
* most important and frequent usage.
*
* See the respective `CanonicalForm'-methods for an explanation
* why we define such a strange (but total) ordering on
* polynomials.
*
* @sa CanonicalForm::operator <(), CanonicalForm::operator ==()
*
**/
int
InternalPoly::comparesame ( InternalCF * acoeff )
{
ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
InternalPoly* apoly = (InternalPoly*)acoeff;
// check on triviality
if ( this == apoly )
return 0;
else
{
termList cursor1 = firstTerm;
termList cursor2 = apoly->firstTerm;
for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
{
// we test on inequality of coefficients at this
// point instead of testing on "less than" at the
// last `else' in the enclosed `if' statement since a
// test on inequality in general is cheaper
if ( cursor1->exp > cursor2->exp )
return 1;
else if ( cursor1->exp < cursor2->exp )
return -1;
if ( (cursor1->coeff != cursor2->coeff) )
{
if ( cursor1->coeff > cursor2->coeff )
return 1;
else
return -1;
}
}
// check trailing terms
if ( cursor1 == cursor2 )
return 0;
else if ( cursor1 != 0 )
return 1;
else
return -1;
}
}
/**
* comparecoeff() always returns 1 since CO is defined to be
* larger than anything which is a coefficient w.r.t. CO.
**/
int
InternalPoly::comparecoeff ( InternalCF * )
{
return 1;
}
InternalCF*
InternalPoly::addcoeff( InternalCF* cc )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( c.isZero() )
return this;
else
{
if ( getRefCount() <= 1 )
{
if ( lastTerm->exp == 0 )
{
lastTerm->coeff += c;
if ( lastTerm->coeff.isZero() )
{
termList cursor = firstTerm;
while ( cursor->next != lastTerm )
cursor = cursor->next;
delete lastTerm;
cursor->next = 0;
lastTerm = cursor;
}
}
else
{
lastTerm->next = new term( 0, c, 0 );
lastTerm = lastTerm->next;
}
return this;
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last, false );
if ( last->exp == 0 )
{
last->coeff += c;
if ( last->coeff.isZero() )
{
termList cursor = first;
while ( cursor->next != last )
cursor = cursor->next;
delete last;
cursor->next = 0;
last = cursor;
}
}
else
{
last->next = new term( 0, c, 0L );
last = last->next;
}
return new InternalPoly( first, last, var );
}
}
}
InternalCF*
InternalPoly::subcoeff( InternalCF* cc, bool negate )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( c.isZero() )
if ( getRefCount() > 1 )
{
decRefCount();
termList last, first = copyTermList( firstTerm, last, negate );
return new InternalPoly( first, last, var );
}
else
{
if ( negate )
negateTermList( firstTerm );
return this;
}
else
{
if ( getRefCount() <= 1 )
{
if ( lastTerm->exp == 0 )
{
if ( negate )
{
negateTermList( firstTerm );
lastTerm->coeff += c;
}
else
lastTerm->coeff -= c;
if ( lastTerm->coeff.isZero() )
{
termList cursor = firstTerm;
while ( cursor->next != lastTerm )
cursor = cursor->next;
delete lastTerm;
cursor->next = 0;
lastTerm = cursor;
}
}
else
{
if ( negate )
{
negateTermList( firstTerm );
lastTerm->next = new term( 0, c, 0 );
}
else
lastTerm->next = new term( 0, -c, 0 );
lastTerm = lastTerm->next;
}
return this;
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last, negate );
if ( last->exp == 0 )
{
if ( negate )
last->coeff += c;
else
last->coeff -= c;
if ( last->coeff.isZero() )
{
termList cursor = first;
while ( cursor->next != last )
cursor = cursor->next;
delete last;
cursor->next = 0;
last = cursor;
}
}
else
{
if ( negate )
last->next = new term( 0, c, 0 );
else
last->next = new term( 0, -c, 0 );
last = last->next;
}
return new InternalPoly( first, last, var );
}
}
}
InternalCF*
InternalPoly::mulcoeff( InternalCF* cc )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( c.isZero() )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic( 0 );
}
else
{
decRefCount();
return CFFactory::basic( 0 );
}
}
else if ( c.isOne() )
return this;
else
{
if ( getRefCount() <= 1 )
{
mulTermList( firstTerm, c, 0 );
return this;
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
mulTermList( first, c, 0 );
return new InternalPoly( first, last, var );
}
}
}
InternalCF*
InternalPoly::dividecoeff( InternalCF* cc, bool invert )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( inExtension() && getReduce( var ) && invert )
{
InternalCF * dummy;
dummy = this->invert();
if (is_imm(dummy))
{
if (is_imm(cc))
{
InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
dummy=d;
}
else
dummy=cc->mulcoeff(dummy);
}
else dummy = dummy->mulcoeff( cc );
if ( getRefCount() <= 1 )
{
delete this;
return dummy;
}
else
{
decRefCount();
return dummy;
}
}
if ( invert )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic( 0 );
}
else
{
decRefCount();
return CFFactory::basic( 0 );
}
}
if ( c.isOne() )
return this;
else
{
if ( getRefCount() <= 1 )
{
firstTerm = divideTermList( firstTerm, c, lastTerm );
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = divideTermList( first, c, last );
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
{
delete first;
return CFFactory::basic( 0 );
}
}
}
}
InternalCF*
InternalPoly::tryDividecoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( inExtension() && !getReduce( var ) && invert )
{
InternalCF * dummy;
dummy = this->tryInvert(M, fail);
if (fail)
{
if (getRefCount() <= 1)
delete this;
else
decRefCount();
return dummy; //is equal to CFFactory::basic ( 0 ) in this case
}
if (is_imm(dummy))
{
if (is_imm(cc))
{
InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
dummy=d;
}
else
dummy=cc->mulcoeff(dummy);
}
else dummy = dummy->mulcoeff( cc );
if ( getRefCount() <= 1 )
{
delete this;
return dummy;
}
else
{
decRefCount();
return dummy;
}
}
if ( invert )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic( 0 );
}
else
{
decRefCount();
return CFFactory::basic( 0 );
}
}
if ( c.isOne() )
return this;
//one should never get here
else
{
if ( getRefCount() <= 1 )
{
firstTerm = divideTermList( firstTerm, c, lastTerm );
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = divideTermList( first, c, last );
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
{
delete first;
return CFFactory::basic( 0 );
}
}
}
}
InternalCF*
InternalPoly::divcoeff( InternalCF* cc, bool invert )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( inExtension() && getReduce( var ) && invert )
{
InternalCF * dummy;
dummy = this->invert();
dummy = dummy->mulcoeff( cc );
if ( getRefCount() <= 1 )
{
delete this;
return dummy;
}
else
{
decRefCount();
return dummy;
}
}
if ( invert )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic( 0 );
}
else
{
decRefCount();
return CFFactory::basic( 0 );
}
}
if ( c.isOne() )
return this;
else
{
if ( getRefCount() <= 1 )
{
firstTerm = divTermList( firstTerm, c, lastTerm );
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = divTermList( first, c, last );
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
{
delete first;
return CFFactory::basic( 0 );
}
}
}
}
InternalCF*
InternalPoly::tryDivcoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( inExtension() && !getReduce( var ) && invert )
{
InternalCF * dummy;
dummy = this->tryInvert(M, fail);
if (fail)
{
if (getRefCount() <= 1)
delete this;
else
decRefCount();
return dummy;
}
dummy = dummy->mulcoeff( cc );
if ( getRefCount() <= 1 )
{
delete this;
return dummy;
}
else
{
decRefCount();
return dummy;
}
}
if ( invert )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic( 0 );
}
else
{
decRefCount();
return CFFactory::basic( 0 );
}
}
if ( c.isOne() )
return this;
else
{
if ( getRefCount() <= 1 )
{
firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
if (fail)
{
delete this;
return CFFactory::basic (0);
}
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = tryDivTermList( first, c, last, M, fail );
if (fail)
{
delete this;
return CFFactory::basic (0);
}
if (fail)
{
delete first;
return CFFactory::basic (0);
}
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
{
delete first;
return CFFactory::basic( 0 );
}
}
}
}
InternalCF*
InternalPoly::modulocoeff( InternalCF* cc, bool invert )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( invert )
{
if ( deleteObject() ) delete this;
return c.getval();
}
ASSERT( ! c.isZero(), "divide by zero!" );
if ( deleteObject() ) delete this;
return CFFactory::basic( 0 );
}
InternalCF*
InternalPoly::modcoeff( InternalCF* cc, bool invert )
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
if ( invert )
{
if ( deleteObject() ) delete this;
return c.getval();
}
ASSERT( ! c.isZero(), "divide by zero!" );
if ( c.isOne() )
{
if ( getRefCount() <= 1 )
{
delete this;
return CFFactory::basic( 0 );
}
else
{
decRefCount();
return CFFactory::basic( 0 );
}
}
else
{
if ( getRefCount() <= 1 )
{
firstTerm = modTermList( firstTerm, c, lastTerm );
if ( firstTerm && firstTerm->exp != 0 )
return this;
else if ( firstTerm )
{
InternalCF * res = firstTerm->coeff.getval();
delete this;
return res;
}
else
{
delete this;
return CFFactory::basic( 0 );
}
}
else
{
decRefCount();
termList last, first = copyTermList( firstTerm, last );
first = modTermList( first, c, last );
if ( first && first->exp != 0 )
return new InternalPoly( first, last, var );
else if ( first )
{
InternalCF * res = first->coeff.getval();
delete first;
return res;
}
else
{
delete first;
return CFFactory::basic( 0 );
}
}
}
}
void
InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
{
if ( inExtension() && getReduce( var ) )
{
quot = copyObject();
quot = quot->dividecoeff( cc, invert );
rem = CFFactory::basic( 0 );
}
else if ( invert )
{
if ( is_imm( cc ) )
rem = cc;
else
rem = cc->copyObject();
quot = CFFactory::basic( 0 );
}
else
{
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
ASSERT( ! c.isZero(), "divide by zero!" );
termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
quotfirst = divideTermList( quotfirst, c, quotlast );
if ( quotfirst )
if ( quotfirst->exp == 0 )
{
quot = quotfirst->coeff.getval();
delete quotfirst;
}
else
quot = new InternalPoly( quotfirst, quotlast, var );
else
quot = CFFactory::basic( 0 );
rem = CFFactory::basic( 0 );
}
}
bool
InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
{
if ( inExtension() && getReduce( var ) )
{
quot = copyObject();
quot = quot->dividecoeff( cc, invert );
rem = CFFactory::basic( 0 );
return true;
}
else if ( invert )
{
if ( is_imm( cc ) )
rem = cc;
else
rem = cc->copyObject();
quot = CFFactory::basic( 0 );
return true;
}
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
ASSERT( ! c.isZero(), "divide by zero!" );
termList quotfirst, quotcursor;
termList cursor;
CanonicalForm cquot, crem;
bool divideok = true;
cursor = firstTerm;
quotcursor = quotfirst = new term;
while ( cursor && divideok )
{
divideok = divremt( cursor->coeff, c, cquot, crem );
divideok = divideok && crem.isZero();
if ( divideok )
{
if ( ! cquot.isZero() )
{
quotcursor->next = new term( 0, cquot, cursor->exp );
quotcursor = quotcursor->next;
}
cursor = cursor->next;
}
}
quotcursor->next = 0;
if ( divideok )
{
cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
if ( quotfirst )
if ( quotfirst->exp == 0 )
{
quot = quotfirst->coeff.getval();
delete quotfirst;
}
else
quot = new InternalPoly( quotfirst, quotcursor, var );
else
quot = CFFactory::basic( 0 );
rem = CFFactory::basic( 0 );
}
else
{
freeTermList( quotfirst );
}
return divideok;
}
bool
InternalPoly::tryDivremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert, const CanonicalForm& M, bool& fail )
{
if ( inExtension() && !getReduce( var ) )
{
quot = copyObject();
quot = quot->tryDividecoeff( cc, invert, M, fail );
if (fail)
return false;
rem = CFFactory::basic( 0 );
return true;
}
else if ( invert )
{
if ( is_imm( cc ) )
rem = cc;
else
rem = cc->copyObject();
quot = CFFactory::basic( 0 );
return true;
}
CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
ASSERT( ! c.isZero(), "divide by zero!" );
termList quotfirst, quotcursor;
termList cursor;
CanonicalForm cquot, crem;
bool divideok = true;
cursor = firstTerm;
quotcursor = quotfirst = new term;
while ( cursor && divideok )
{
divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail );
if (fail)
{
freeTermList (quotfirst);
return false;
}
divideok = divideok && crem.isZero();
if ( divideok )
{
if ( ! cquot.isZero() )
{
quotcursor->next = new term( 0, cquot, cursor->exp );
quotcursor = quotcursor->next;
}
cursor = cursor->next;
}
}
quotcursor->next = 0;
if ( divideok )
{
cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
if ( quotfirst )
if ( quotfirst->exp == 0 )
{
quot = quotfirst->coeff.getval();
delete quotfirst;
}
else
quot = new InternalPoly( quotfirst, quotcursor, var );
else
quot = CFFactory::basic( 0 );
rem = CFFactory::basic( 0 );
}
else
{
freeTermList( quotfirst );
}
return divideok;
}
// static functions
termList
InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
{
if ( UNLIKELY(aTermList == 0) )
return 0;
else if ( negate )
{
termList sourceCursor = aTermList;
termList dummy = new term;
termList targetCursor = dummy;
while ( LIKELY(sourceCursor) )
{
targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
targetCursor = targetCursor->next;
sourceCursor = sourceCursor->next;
}
targetCursor->next = 0;
theLastTerm = targetCursor;
targetCursor = dummy->next;
delete dummy;
return targetCursor;
}
else
{
termList sourceCursor = aTermList;
termList dummy = new term;
termList targetCursor = dummy;
while ( LIKELY(sourceCursor) )
{
targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
targetCursor = targetCursor->next;
sourceCursor = sourceCursor->next;
}
targetCursor->next = 0;
theLastTerm = targetCursor;
targetCursor = dummy->next;
delete dummy;
return targetCursor;
}
}
termList
InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
{
if ( aTermList == 0 )
return 0;
else
{
termList sourceCursor = aTermList;
termList dummy = new term;
termList targetCursor = dummy;
while ( sourceCursor )
{
targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
targetCursor = targetCursor->next;
sourceCursor = sourceCursor->next;
}
targetCursor->next = 0;
theLastTerm = targetCursor;
targetCursor = dummy->next;
delete dummy;
return targetCursor;
}
}
void
InternalPoly::freeTermList ( termList aTermList )
{
termList cursor = aTermList;
while ( LIKELY(cursor) )
{
cursor = cursor->next;
delete aTermList;
aTermList = cursor;
}
}
void
InternalPoly::negateTermList ( termList terms )
{
termList cursor = terms;
while ( LIKELY(cursor) )
{
cursor->coeff = -cursor->coeff;
cursor = cursor->next;
}
}
termList
InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
{
termList theCursor = theList;
termList aCursor = aList;
termList predCursor = 0;
if (negate)
while ( theCursor && aCursor )
{
if ( theCursor->exp == aCursor->exp )
{
theCursor->coeff -= aCursor->coeff;
if ( theCursor->coeff.isZero() )
{
if ( predCursor )
{
predCursor->next = theCursor->next;
delete theCursor;
theCursor = predCursor->next;
}
else
{
theList = theList->next;
delete theCursor;
theCursor = theList;
}
}
else
{
predCursor = theCursor;
theCursor = theCursor->next;
}
aCursor = aCursor->next;
}
else if ( theCursor->exp < aCursor->exp )
{
if ( predCursor )
{
predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
predCursor = predCursor->next;
}
else
{
theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
predCursor = theList;
}
aCursor = aCursor->next;
}
else
{
predCursor = theCursor;
theCursor = theCursor->next;
}
}
else
while ( theCursor && aCursor )
{
if ( theCursor->exp == aCursor->exp )
{
theCursor->coeff += aCursor->coeff;
if ( theCursor->coeff.isZero() )
{
if ( predCursor )
{
predCursor->next = theCursor->next;
delete theCursor;
theCursor = predCursor->next;
}
else
{
theList = theList->next;
delete theCursor;
theCursor = theList;
}
}
else
{
predCursor = theCursor;
theCursor = theCursor->next;
}
aCursor = aCursor->next;
}
else if ( theCursor->exp < aCursor->exp )
{
if ( predCursor )
{
predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
predCursor = predCursor->next;
}
else
{
theList = new term( theCursor, aCursor->coeff, aCursor->exp );
predCursor = theList;
}
aCursor = aCursor->next;
}
else
{
predCursor = theCursor;
theCursor = theCursor->next;
}
}
if ( aCursor )
{
if ( predCursor )
predCursor->next = copyTermList( aCursor, lastTerm, negate );
else
theList = copyTermList( aCursor, lastTerm, negate );
}
else if ( ! theCursor )
lastTerm = predCursor;
return theList;
}
void
InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
{
while ( LIKELY(theCursor) )
{
theCursor->coeff *= coeff;
theCursor->exp += exp;
theCursor = theCursor->next;
}
}
termList
InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
{
termList theCursor = firstTerm;
lastTerm = 0;
termList dummy;
while ( LIKELY(theCursor) )
{
theCursor->coeff /= coeff;
if ( theCursor->coeff.isZero() )
{
if ( theCursor == firstTerm )
firstTerm = theCursor->next;
else
lastTerm->next = theCursor->next;
dummy = theCursor;
theCursor = theCursor->next;
delete dummy;
}
else
{
lastTerm = theCursor;
theCursor = theCursor->next;
}
}
return firstTerm;
}
termList
InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
{
termList theCursor = firstTerm;
lastTerm = 0;
termList dummy;
while ( LIKELY(theCursor) )
{
theCursor->coeff.div( coeff );
if ( theCursor->coeff.isZero() )
{
if ( theCursor == firstTerm )
firstTerm = theCursor->next;
else
lastTerm->next = theCursor->next;
dummy = theCursor;
theCursor = theCursor->next;
delete dummy;
}
else
{
lastTerm = theCursor;
theCursor = theCursor->next;
}
}
return firstTerm;
}
termList
InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail )
{
termList theCursor = firstTerm;
lastTerm = 0;
termList dummy;
while ( theCursor )
{
theCursor->coeff.tryDiv( coeff, M, fail );
if (fail)
return 0;
if ( theCursor->coeff.isZero() )
{
if ( theCursor == firstTerm )
firstTerm = theCursor->next;
else
lastTerm->next = theCursor->next;
dummy = theCursor;
theCursor = theCursor->next;
delete dummy;
}
else
{
lastTerm = theCursor;
theCursor = theCursor->next;
}
}
return firstTerm;
}
termList
InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
{
termList theCursor = firstTerm;
lastTerm = 0;
termList dummy;
while ( theCursor )
{
theCursor->coeff.mod( coeff );
if ( theCursor->coeff.isZero() )
{
if ( theCursor == firstTerm )
firstTerm = theCursor->next;
else
lastTerm->next = theCursor->next;
dummy = theCursor;
theCursor = theCursor-> next;
delete dummy;
}
else
{
lastTerm = theCursor;
theCursor = theCursor->next;
}
}
return firstTerm;
}
void
InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
{
if ( last )
{
last->next = new term( 0, coeff, exp );
last = last->next;
}
else
{
first = new term( 0, coeff, exp );
last = first;
}
}
termList
InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
{
termList theCursor = theList;
termList aCursor = aList;
termList predCursor = 0;
CanonicalForm coeff;
if ( negate )
coeff = -c;
else
coeff = c;
while ( theCursor && aCursor )
{
if ( theCursor->exp == aCursor->exp + exp )
{
theCursor->coeff += aCursor->coeff * coeff;
if(UNLIKELY(( theCursor->coeff.isZero() )))
{
if ( predCursor )
{
predCursor->next = theCursor->next;
delete theCursor;
theCursor = predCursor->next;
}
else
{
theList = theList->next;
delete theCursor;
theCursor = theList;
}
}
else
{
predCursor = theCursor;
theCursor = theCursor->next;
}
aCursor = aCursor->next;
}
else if ( theCursor->exp < aCursor->exp + exp )
{
if ( predCursor )
{
predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
predCursor = predCursor->next;
}
else
{
theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
predCursor = theList;
}
aCursor = aCursor->next;
}
else
{
predCursor = theCursor;
theCursor = theCursor->next;
}
}
if ( aCursor )
{
if ( predCursor )
{
predCursor->next = copyTermList( aCursor, lastTerm );
predCursor = predCursor->next;
}
else
{
theList = copyTermList( aCursor, lastTerm );
predCursor = theList;
}
while ( predCursor )
{
predCursor->exp += exp;
predCursor->coeff *= coeff;
predCursor = predCursor->next;
}
}
else if ( ! theCursor )
lastTerm = predCursor;
return theList;
}
termList
InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
{
CanonicalForm coeff = CanonicalForm (1)/redterms->coeff;
CanonicalForm newcoeff;
int newexp;
int exp = redterms->exp;
termList dummy;
while ( first && ( first->exp >= exp ) )
{
newcoeff = first->coeff * coeff;
newexp = first->exp - exp;
dummy = first;
first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
delete dummy;
}
return first;
}
UNLIKELY
#define UNLIKELY(X)
Definition auxiliary.h:405
LIKELY
#define LIKELY(X)
Definition auxiliary.h:404
tryDivremt
bool tryDivremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const CanonicalForm &M, bool &fail)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
Definition canonicalform.cc:1108
divremt
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1066
canonicalform.h
Header for factory's main class CanonicalForm.
replacevar
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ).
Definition cf_ops.cc:271
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
is_imm
int is_imm(const InternalCF *const ptr)
Definition canonicalform.h:65
reduce
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition cf_ops.cc:660
i
int i
Definition cfEzgcd.cc:132
x
Variable x
Definition cfModGcd.cc:4090
g
g
Definition cfModGcd.cc:4098
test
CanonicalForm test
Definition cfModGcd.cc:4104
b
CanonicalForm b
Definition cfModGcd.cc:4111
extgcd
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition cfUnivarGcd.cc:174
cfUnivarGcd.h
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
cf_assert.h
assertions for Factory
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
cf_defs.h
factory switches.
LEVELBASE
#define LEVELBASE
Definition cf_defs.h:25
cf_factory.h
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
termList
term * termList
Definition cf_iter.h:36
CFFactory::basic
static InternalCF * basic(int value)
Definition cf_factory.cc:61
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::sign
int sign() const
int CanonicalForm::sign () const
Definition canonicalform.cc:1360
CanonicalForm::deepCopy
CanonicalForm deepCopy() const
Definition canonicalform.cc:43
CanonicalForm::getval
InternalCF * getval() const
Definition canonicalform.cc:34
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::tryDiv
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
Definition canonicalform.cc:905
CanonicalForm::mod
CanonicalForm & mod(const CanonicalForm &)
Definition canonicalform.cc:990
CanonicalForm::print
void print(OSTREAM &, char *) const
input/output
Definition canonicalform.cc:1833
CanonicalForm::div
CanonicalForm & div(const CanonicalForm &)
Definition canonicalform.cc:862
InternalCF
virtual class for internal CanonicalForm's
Definition int_cf.h:47
InternalCF::tryMulsame
virtual InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
Definition int_cf.cc:179
InternalCF::copyObject
InternalCF * copyObject()
Definition int_cf.h:62
InternalCF::mulcoeff
virtual InternalCF * mulcoeff(InternalCF *) PVIRT_INTCF("mulcoeff")
InternalCF::InternalCF
InternalCF()
Definition int_cf.h:55
InternalCF::tryDividecoeff
virtual InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition int_cf.cc:221
InternalCF::dividecoeff
virtual InternalCF * dividecoeff(InternalCF *, bool) PVIRT_INTCF("dividecoeff")
InternalCF::getRefCount
int getRefCount()
Definition int_cf.h:51
InternalCF::tryInvert
virtual InternalCF * tryInvert(const CanonicalForm &, bool &)
Definition int_cf.cc:186
InternalCF::decRefCount
int decRefCount()
Definition int_cf.h:53
InternalCF::invert
virtual InternalCF * invert()
Definition int_cf.cc:172
InternalCF::deleteObject
int deleteObject()
Definition int_cf.h:61
InternalCF::level
virtual int level() const
Definition int_cf.h:67
InternalCF::mulsame
virtual InternalCF * mulsame(InternalCF *) PVIRT_INTCF("mulsame")
InternalInteger
factory's class for integers
Definition int_int.h:56
InternalPoly
factory's class for polynomials
Definition int_poly.h:71
InternalPoly::addsame
InternalCF * addsame(InternalCF *)
Definition int_poly.cc:286
InternalPoly::divideTermList
static termList divideTermList(termList, const CanonicalForm &, termList &)
Definition int_poly.cc:2051
InternalPoly::~InternalPoly
~InternalPoly()
Definition int_poly.cc:70
InternalPoly::taildegree
int taildegree()
Definition int_poly.cc:153
InternalPoly::addTermList
static termList addTermList(termList, termList, termList &, bool negate)
Definition int_poly.cc:1924
InternalPoly::mulcoeff
InternalCF * mulcoeff(InternalCF *)
Definition int_poly.cc:1183
InternalPoly::var
Variable var
Definition int_poly.h:74
InternalPoly::print
void print(OSTREAM &, char *)
Definition int_poly.cc:179
InternalPoly::reduceTermList
static termList reduceTermList(termList first, termList redterms, termList &last)
Definition int_poly.cc:2268
InternalPoly::LC
CanonicalForm LC()
Definition int_poly.cc:138
InternalPoly::modsame
InternalCF * modsame(InternalCF *)
Definition int_poly.cc:693
InternalPoly::degree
int degree()
int InternalPoly::degree ()
Definition int_poly.cc:100
InternalPoly::freeTermList
static void freeTermList(termList)
Definition int_poly.cc:1900
InternalPoly::deepCopyObject
InternalCF * deepCopyObject() const
Definition int_poly.cc:76
InternalPoly::divremsamet
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
Definition int_poly.cc:817
InternalPoly::neg
InternalCF * neg()
InternalCF * InternalPoly::neg ().
Definition int_poly.cc:231
InternalPoly::tryDivcoeff
InternalCF * tryDivcoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition int_poly.cc:1477
InternalPoly::InternalPoly_bin
static const omBin InternalPoly_bin
Definition int_poly.h:159
InternalPoly::mulTermList
static void mulTermList(termList, const CanonicalForm &, const int)
Definition int_poly.cc:2040
InternalPoly::isUnivariate
bool isUnivariate() const
Definition int_poly.cc:84
InternalPoly::divremcoeff
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition int_poly.cc:1654
InternalPoly::comparesame
int comparesame(InternalCF *)
InternalPoly::invert
InternalCF * invert()
Definition int_poly.cc:247
InternalPoly::tryDividecoeff
InternalCF * tryDividecoeff(InternalCF *, bool, const CanonicalForm &, bool &)
Definition int_poly.cc:1305
InternalPoly::modulocoeff
InternalCF * modulocoeff(InternalCF *, bool)
Definition int_poly.cc:1576
InternalPoly::subsame
InternalCF * subsame(InternalCF *)
Definition int_poly.cc:326
InternalPoly::firstTerm
termList firstTerm
Definition int_poly.h:73
InternalPoly::divcoeff
InternalCF * divcoeff(InternalCF *, bool)
Definition int_poly.cc:1401
InternalPoly::modcoeff
InternalCF * modcoeff(InternalCF *, bool)
Definition int_poly.cc:1590
InternalPoly::inExtension
bool inExtension() const
Definition int_poly.h:110
InternalPoly::modulosame
InternalCF * modulosame(InternalCF *)
Definition int_poly.cc:687
InternalPoly::negateTermList
static void negateTermList(termList)
Definition int_poly.cc:1913
InternalPoly::tryDivTermList
static termList tryDivTermList(termList, const CanonicalForm &, termList &, const CanonicalForm &, bool &)
Definition int_poly.cc:2109
InternalPoly::mulAddTermList
static termList mulAddTermList(termList theList, termList aList, const CanonicalForm &c, const int exp, termList &lastTerm, bool negate)
Definition int_poly.cc:2184
InternalPoly::tryDivremcoefft
bool tryDivremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
Definition int_poly.cc:1757
InternalPoly::lastTerm
termList lastTerm
Definition int_poly.h:73
InternalPoly::divremsame
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
Definition int_poly.cc:765
InternalPoly::dividesame
InternalCF * dividesame(InternalCF *)
Definition int_poly.cc:491
InternalPoly::divremcoefft
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition int_poly.cc:1691
InternalPoly::coeff
CanonicalForm coeff(int i)
CanonicalForm InternalPoly::coeff ( int i ).
Definition int_poly.cc:162
InternalPoly::dividecoeff
InternalCF * dividecoeff(InternalCF *, bool)
Definition int_poly.cc:1219
InternalPoly::comparecoeff
int comparecoeff(InternalCF *)
comparesame(), comparecoeff() - compare with an InternalPoly.
Definition int_poly.cc:1034
InternalPoly::tailcoeff
CanonicalForm tailcoeff()
CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ().
Definition int_poly.cc:147
InternalPoly::deepCopyTermList
static termList deepCopyTermList(termList, termList &)
Definition int_poly.cc:1875
InternalPoly::divsame
InternalCF * divsame(InternalCF *)
Definition int_poly.cc:498
InternalPoly::InternalPoly
InternalPoly()
Definition int_poly.cc:53
InternalPoly::addcoeff
InternalCF * addcoeff(InternalCF *)
Definition int_poly.cc:1040
InternalPoly::subcoeff
InternalCF * subcoeff(InternalCF *, bool)
Definition int_poly.cc:1097
InternalPoly::InternalPoly
InternalPoly(termList, termList, const Variable &)
Definition int_poly.cc:46
InternalPoly::tryDivremsamet
bool tryDivremsamet(InternalCF *, InternalCF *&, InternalCF *&, const CanonicalForm &, bool &)
Definition int_poly.cc:883
InternalPoly::lc
CanonicalForm lc()
Definition int_poly.cc:120
InternalPoly::modTermList
static termList modTermList(termList, const CanonicalForm &, termList &)
Definition int_poly.cc:2140
InternalPoly::copyTermList
static termList copyTermList(termList, termList &, bool negate=false)
Definition int_poly.cc:1832
InternalPoly::appendTermList
static void appendTermList(termList &, termList &, const CanonicalForm &, const int)
Definition int_poly.cc:2169
InternalPoly::Lc
CanonicalForm Lc()
Definition int_poly.cc:129
InternalPoly::divTermList
static termList divTermList(termList, const CanonicalForm &, termList &)
Definition int_poly.cc:2080
InternalPoly::mulsame
InternalCF * mulsame(InternalCF *)
Definition int_poly.cc:366
InternalPoly::tryInvert
InternalCF * tryInvert(const CanonicalForm &, bool &)
Definition int_poly.cc:264
InternalPoly::tryMulsame
InternalCF * tryMulsame(InternalCF *, const CanonicalForm &)
Definition int_poly.cc:428
InternalPoly::sign
int sign() const
int InternalPoly::sign () const
Definition int_poly.cc:110
InternalPoly::tryDivsame
InternalCF * tryDivsame(InternalCF *, const CanonicalForm &, bool &)
Definition int_poly.cc:584
Variable
factory's class for variables
Definition factory.h:127
term
Definition int_poly.h:33
term::term_bin
static const omBin term_bin
Definition int_poly.h:39
term::next
term * next
Definition int_poly.h:35
term::coeff
CanonicalForm coeff
Definition int_poly.h:36
term::exp
int exp
Definition int_poly.h:37
res
CanonicalForm res
Definition facAbsFact.cc:60
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
setReduce
void setReduce(const Variable &alpha, bool reduce)
Definition variable.cc:238
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
last
STATIC_VAR poly last
Definition hdegree.cc:1138
imm.h
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
imm2int
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
int_cf.h
Factory's internal CanonicalForm's.
int_int.h
Factory's internal integers.
int_poly.h
Factory's internal polynomials.
OSTREAM
#define OSTREAM
Definition int_poly.h:17
termList
term * termList
Definition int_poly.h:60
next
ListNode * next
Definition janet.h:31
rem
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition minpoly.cc:572
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
omGetSpecBin
#define omGetSpecBin(size)
Definition omBin.h:11
omBin
omBin_t * omBin
Definition omStructs.h:12
M
#define M
Definition sirandom.c:25
getReduce
bool getReduce(const Variable &alpha)
Definition variable.cc:232
getInternalMipo
InternalPoly * getInternalMipo(const Variable &alpha)
Definition variable.cc:201
variable.h
operations on variables