canonicalform.cc File Reference

#include "config.h"
#include "cf_assert.h"
#include "cf_factory.h"
#include "cf_defs.h"
#include "cf_globals.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "int_cf.h"
#include "cf_algorithm.h"
#include "imm.h"
#include "int_pp.h"
#include "gfops.h"
#include "facMul.h"
#include "facAlgFuncUtil.h"
#include "FLINTconvert.h"
#include "cf_binom.h"

Go to the source code of this file.

Functions
void	divrem (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
bool	divremt (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
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 More...
bool	operator== (const CanonicalForm &lhs, const CanonicalForm &rhs)
	operator ==() - compare canonical forms on (in)equality. More...
bool	operator!= (const CanonicalForm &lhs, const CanonicalForm &rhs)
	operator !=() returns true iff lhs does not equal rhs. More...
bool	operator> (const CanonicalForm &lhs, const CanonicalForm &rhs)
	operator >() - compare canonical forms. More...
bool	operator< (const CanonicalForm &lhs, const CanonicalForm &rhs)
CanonicalForm	bgcd (const CanonicalForm &f, const CanonicalForm &g)
	CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ) More...
CanonicalForm	bextgcd (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
	CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) More...
CanonicalForm	blcm (const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm	power (const CanonicalForm &f, int n)
	exponentiation More...
CanonicalForm	power (const Variable &v, int n)
	exponentiation More...
void	On (int sw)
	switches More...
void	Off (int sw)
	switches More...
bool	isOn (int sw)
	switches More...

Function Documentation

bextgcd()

CanonicalForm bextgcd	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		CanonicalForm &	a,
		CanonicalForm &	b
	)

CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )

bextgcd() - return base coefficient extended gcd.

Definition at line 1722 of file canonicalform.cc.

{
    // check immediate cases
    int what = is_imm( g.value );
    if ( is_imm( f.value ) ) {
        ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
        if ( what == 0 )
            return g.value->bextgcdcoeff( f.value, b, a );
        else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) {
            // calculate extended gcd using standard integer
            // arithmetic
            long fInt = imm2int( f.value );
            long gInt = imm2int( g.value );
 
            // to avoid any system dpendencies with `%', we work
            // with positive numbers only.  To a pity, we have to
            // redo all the checks when assigning to a and b.
            if ( fInt < 0 ) fInt = -fInt;
            if ( gInt < 0 ) gInt = -gInt;
            // swap fInt and gInt
            if ( gInt > fInt ) {
                long swap = gInt;
                gInt = fInt;
                fInt = swap;
            }
 
            long u = 1; long v = 0;
            long uNext = 0; long vNext = 1;
 
            // at any step, we have:
            // fInt_0 * u + gInt_0 * v = fInt
            // fInt_0 * uNext + gInt_0 * vNext = gInt
            // where fInt_0 and gInt_0 denote the values of fint
            // and gInt, resp., at the beginning
            while ( gInt ) {
                long r = fInt % gInt;
                long q = fInt / gInt;
                long uSwap = u - q * uNext;
                long vSwap = v - q * vNext;
 
                // update variables
                fInt = gInt;
                gInt = r;
                u = uNext; v = vNext;
                uNext = uSwap; vNext = vSwap;
            }
 
            // now, assign to a and b
            long fTest = imm2int( f.value );
            long gTest = imm2int( g.value );
            if ( gTest > fTest ) {
                a = v; b = u;
            } else {
                a = u; b = v;
            }
            if ( fTest < 0 ) a = -a;
            if ( gTest < 0 ) b = -b;
            return CanonicalForm( fInt );
        } else
            // stupid special cases
            if ( ! f.isZero() ) {
                a = 1/f; b = 0; return CanonicalForm( 1L );
            } else if ( ! g.isZero() ) {
                a = 0; b = 1/g; return CanonicalForm( 1L );
            } else {
                a = 0; b = 0; return CanonicalForm( 0L );
            }
    }
    else if ( what )
        return f.value->bextgcdcoeff( g.value, a, b );
 
    int fLevel = f.value->level();
    int gLevel = g.value->level();
 
    // check levels
    if ( fLevel == gLevel ) {
        fLevel = f.value->levelcoeff();
        gLevel = g.value->levelcoeff();
 
        // check levelcoeffs
        if ( fLevel == gLevel )
            return f.value->bextgcdsame( g.value, a, b );
        else if ( fLevel < gLevel )
            return g.value->bextgcdcoeff( f.value, b, a );
        else
            return f.value->bextgcdcoeff( g.value, a, b );
    }
    else if ( fLevel < gLevel )
        return g.value->bextgcdcoeff( f.value, b, a );
    else
        return f.value->bextgcdcoeff( g.value, a, b );
}

bgcd()

CanonicalForm bgcd	(	const CanonicalForm &	f,
		const CanonicalForm &	g
	)

CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )

bgcd() - return base coefficient gcd.

If both f and g are integers and ‘SW_RATIONAL’ is off the positive greatest common divisor of f and g is returned. Otherwise, if ‘SW_RATIONAL’ is on or one of f and g is not an integer, the greatest common divisor is trivial: either zero if f and g equal zero or one (both from the current domain).

f and g should come from one base domain which should be not the prime power domain.

Implementation:

CanonicalForm::bgcd() handles the immediate case with a standard euclidean algorithm. For the non-immediate cases ‘InternalCF::bgcdsame()’ or ‘InternalCF::bgcdcoeff()’, resp. are called following the usual level/levelcoeff approach.

InternalCF::bgcdsame() and InternalCF::bgcdcoeff() throw an assertion ("not implemented")

InternalInteger::bgcdsame() is a wrapper around ‘mpz_gcd()’ which takes some care about immediate results and the sign of the result InternalInteger::bgcdcoeff() is a wrapper around ‘mpz_gcd_ui()’ which takes some care about the sign of the result

InternalRational::bgcdsame() and InternalRational::bgcdcoeff() always return one

Definition at line 1648 of file canonicalform.cc.

{
    // check immediate cases
    int what = is_imm( g.value );
    if ( is_imm( f.value ) )
    {
        ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
        if ( what == 0 )
            return g.value->bgcdcoeff( f.value );
        else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) )
        {
            // calculate gcd using standard integer
            // arithmetic
            long fInt = imm2int( f.value );
            long gInt = imm2int( g.value );
 
            if ( fInt < 0 ) fInt = -fInt;
            if ( gInt < 0 ) gInt = -gInt;
            // swap fInt and gInt
            if ( gInt > fInt )
            {
                long swap = gInt;
                gInt = fInt;
                fInt = swap;
            }
 
            // now, 0 <= gInt <= fInt.  Start the loop.
            while ( gInt )
            {
                // calculate (fInt, gInt) = (gInt, fInt%gInt)
                long r = fInt % gInt;
                fInt = gInt;
                gInt = r;
            }
 
            return CanonicalForm( fInt );
        }
        else
            // we do not go for maximal speed for these stupid
            // special cases
            return CanonicalForm( f.isZero() && g.isZero() ? 0 : 1 );
    }
    else if ( what )
        return f.value->bgcdcoeff( g.value );
 
    int fLevel = f.value->level();
    int gLevel = g.value->level();
 
    // check levels
    if ( fLevel == gLevel )
    {
        fLevel = f.value->levelcoeff();
        gLevel = g.value->levelcoeff();
 
        // check levelcoeffs
        if ( fLevel == gLevel )
            return f.value->bgcdsame( g.value );
        else if ( fLevel < gLevel )
            return g.value->bgcdcoeff( f.value );
        else
            return f.value->bgcdcoeff( g.value );
    }
    else if ( fLevel < gLevel )
        return g.value->bgcdcoeff( f.value );
    else
        return f.value->bgcdcoeff( g.value );
}

blcm()

CanonicalForm blcm	(	const CanonicalForm &	f,
		const CanonicalForm &	g
	)

Definition at line 1816 of file canonicalform.cc.

{
    if ( f.isZero() || g.isZero() )
        return CanonicalForm( 0L );
/*
    else if (f.isOne())
        return g;
    else if (g.isOne())
        return f;
*/
    else
        return (f / bgcd( f, g )) * g;
}

divrem()

void divrem	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		CanonicalForm &	q,
		CanonicalForm &	r
	)

Definition at line 1032 of file canonicalform.cc.

{
    InternalCF * qq = 0, * rr = 0;
    int what = is_imm( f.value );
    if ( what )
        if ( is_imm( g.value ) ) {
            if ( what == FFMARK )
                imm_divrem_p( f.value, g.value, qq, rr );
            else  if ( what == GFMARK )
                imm_divrem_gf( f.value, g.value, qq, rr );
            else
                imm_divrem( f.value, g.value, qq, rr );
        }
        else
            g.value->divremcoeff( f.value, qq, rr, true );
    else  if ( (what=is_imm( g.value )) )
        f.value->divremcoeff( g.value, qq, rr, false );
    else  if ( f.value->level() == g.value->level() )
        if ( f.value->levelcoeff() == g.value->levelcoeff() )
            f.value->divremsame( g.value, qq, rr );
        else  if ( f.value->levelcoeff() > g.value->levelcoeff() )
            f.value->divremcoeff( g.value, qq, rr, false );
        else
            g.value->divremcoeff( f.value, qq, rr, true );
    else  if ( f.value->level() > g.value->level() )
        f.value->divremcoeff( g.value, qq, rr, false );
    else
        g.value->divremcoeff( f.value, qq, rr, true );
    ASSERT( qq != 0 && rr != 0, "error in divrem" );
    q = CanonicalForm( qq );
    r = CanonicalForm( rr );
}

divremt()

bool divremt	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		CanonicalForm &	q,
		CanonicalForm &	r
	)

Definition at line 1066 of file canonicalform.cc.

{
    InternalCF * qq = 0, * rr = 0;
    int what = is_imm( f.value );
    bool result = true;
    if ( what )
        if ( is_imm( g.value ) ) {
            if ( what == FFMARK )
                imm_divrem_p( f.value, g.value, qq, rr );
            else  if ( what == GFMARK )
                imm_divrem_gf( f.value, g.value, qq, rr );
            else
                imm_divrem( f.value, g.value, qq, rr );
        }
        else
            result = g.value->divremcoefft( f.value, qq, rr, true );
    else  if ( (what=is_imm( g.value )) )
        result = f.value->divremcoefft( g.value, qq, rr, false );
    else  if ( f.value->level() == g.value->level() )
        if ( f.value->levelcoeff() == g.value->levelcoeff() )
            result = f.value->divremsamet( g.value, qq, rr );
        else  if ( f.value->levelcoeff() > g.value->levelcoeff() )
            result = f.value->divremcoefft( g.value, qq, rr, false );
        else
            result = g.value->divremcoefft( f.value, qq, rr, true );
    else  if ( f.value->level() > g.value->level() )
        result = f.value->divremcoefft( g.value, qq, rr, false );
    else
        result = g.value->divremcoefft( f.value, qq, rr, true );
    if ( result ) {
        ASSERT( qq != 0 && rr != 0, "error in divrem" );
        q = CanonicalForm( qq );
        r = CanonicalForm( rr );
    }
    else {
        q = 0; r = 0;
    }
    return result;
}

isOn()

bool isOn

(

int

sw

)

switches

Definition at line 1971 of file canonicalform.cc.

{
    return cf_glob_switches.isOn( sw );
}

Off()

void Off

(

int

sw

)

switches

Definition at line 1964 of file canonicalform.cc.

{
    cf_glob_switches.Off( sw );
}

On()

void On

(

int

sw

)

switches

Definition at line 1957 of file canonicalform.cc.

{
    cf_glob_switches.On( sw );
}

operator!=()

bool operator!=	(	const CanonicalForm &	lhs,
		const CanonicalForm &	rhs
	)

operator !=() returns true iff lhs does not equal rhs.

See also

CanonicalForm::operator ==()

Definition at line 1492 of file canonicalform.cc.

{
    if ( lhs.value == rhs.value )
        return false;
    else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
        ASSERT( ! is_imm( rhs.value ) ||
                ! is_imm( lhs.value ) ||
                is_imm( rhs.value ) == is_imm( lhs.value ),
                "incompatible operands" );
        return true;
    }
    else  if ( lhs.value->level() != rhs.value->level() )
        return true;
    else  if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
        return true;
    else        return rhs.value->comparesame( lhs.value ) != 0;
}

operator<()

bool operator<	(	const CanonicalForm &	lhs,
		const CanonicalForm &	rhs
	)

See also

CanonicalForm::operator >()

Definition at line 1585 of file canonicalform.cc.

{
    int what = is_imm( rhs.value );
    if ( is_imm( lhs.value ) ) {
        ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
        if ( what == 0 )
            return rhs.value->comparecoeff( lhs.value ) > 0;
        else if ( what == INTMARK )
            return imm_cmp( lhs.value, rhs.value ) < 0;
        else if ( what == FFMARK )
            return imm_cmp_p( lhs.value, rhs.value ) < 0;
        else
            return imm_cmp_gf( lhs.value, rhs.value ) < 0;
    }
    else  if ( what )
        return lhs.value->comparecoeff( rhs.value ) < 0;
    else  if ( lhs.value->level() == rhs.value->level() )
        if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
            return lhs.value->comparesame( rhs.value ) < 0;
        else  if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
            return lhs.value->comparecoeff( rhs.value ) < 0;
        else
            return rhs.value->comparecoeff( lhs.value ) > 0;
    else
        return lhs.value->level() < rhs.value->level();
}

operator==()

bool operator==	(	const CanonicalForm &	lhs,
		const CanonicalForm &	rhs
	)

operator ==() - compare canonical forms on (in)equality.

operator ==() returns true iff lhs equals rhs.

This is the point in factory where we essentially use that CanonicalForms in fact are canonical. There must not be two different representations of the same mathematical object, otherwise, such (in)equality will not be recognized by these operators. In other word, we rely on the fact that structural different factory objects in any case represent different mathematical objects.

So we use the following procedure to test on equality (and analogously on inequality). First, we check whether lhs.value equals rhs.value. If so we are ready and return true. Second, if one of the operands is immediate, but the other one not, we return false. Third, if the operand's levels differ we return false. Fourth, if the operand's levelcoeffs differ we return false. At last, we call the corresponding internal method to compare both operands.

Both operands should have coefficients from the same base domain.

Note: To compare with the zero or the unit of the current domain, you better use the methods ‘CanonicalForm::isZero()’ or ‘CanonicalForm::isOne()’, resp., than something like ‘f == 0’, since the latter is quite a lot slower.

See also

CanonicalForm::operator !=(), InternalCF::comparesame(), InternalInteger::comparesame(), InternalRational::comparesame(), InternalPoly::comparesame()

Definition at line 1467 of file canonicalform.cc.

{
    if ( lhs.value == rhs.value )
        return true;
    else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
        ASSERT( ! is_imm( rhs.value ) ||
                ! is_imm( lhs.value ) ||
                is_imm( rhs.value ) == is_imm( lhs.value ),
                "incompatible operands" );
        return false;
    }
    else  if ( lhs.value->level() != rhs.value->level() )
        return false;
    else  if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
        return false;
    else
        return rhs.value->comparesame( lhs.value ) == 0;
}

operator>()

bool operator>	(	const CanonicalForm &	lhs,
		const CanonicalForm &	rhs
	)

operator >() - compare canonical forms.

on size or level.

The most common and most useful application of these operators is to compare two integers or rationals, of course. However, these operators are defined on all other base domains and on polynomials, too. From a mathematical point of view this may seem meaningless, since there is no ordering on finite fields or on polynomials respecting the algebraic structure. Nevertheless, from a programmer's point of view it may be sensible to order these objects, e.g. to sort them.

Therefore, the ordering defined by these operators in any case is a total ordering which fulfills the law of trichotomy.

It is clear how this is done in the case of the integers and the rationals. For finite fields, all you can say is that zero is the minimal element w.r.t. the ordering, the other elements are ordered in an arbitrary (but total!) way. For polynomials, you have an ordering derived from the lexicographical ordering of monomials. E.g. if lm(f) < lm(g) w.r.t. lexicographic ordering, then f < g. For more details, refer to the documentation of ‘InternalPoly::operator <()’.

Both operands should have coefficients from the same base domain.

The scheme how both operators are implemented is allmost the same as for the assignment operators (check for immediates, then check levels, then check levelcoeffs, then call the appropriate internal comparesame()/comparecoeff() method). For more information, confer to the overview for the arithmetic operators.

See also

CanonicalForm::operator <(), InternalCF::comparesame(), InternalInteger::comparesame(), InternalRational::comparesame(), InternalPoly::comparesame(), InternalCF::comparecoeff(), InternalInteger::comparecoeff(), InternalRational::comparecoeff(), InternalPoly::comparecoeff(), imm_cmp(), imm_cmp_p(), imm_cmp_gf()

Definition at line 1555 of file canonicalform.cc.

{
    int what = is_imm( rhs.value );
    if ( is_imm( lhs.value ) ) {
        ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
        if ( what == 0 )
            return rhs.value->comparecoeff( lhs.value ) < 0;
        else if ( what == INTMARK )
            return imm_cmp( lhs.value, rhs.value ) > 0;
        else if ( what == FFMARK )
            return imm_cmp_p( lhs.value, rhs.value ) > 0;
        else
            return imm_cmp_gf( lhs.value, rhs.value ) > 0;
    }
    else  if ( what )
        return lhs.value->comparecoeff( rhs.value ) > 0;
    else  if ( lhs.value->level() == rhs.value->level() )
        if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
            return lhs.value->comparesame( rhs.value ) > 0;
        else  if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
            return lhs.value->comparecoeff( rhs.value ) > 0;
        else
            return rhs.value->comparecoeff( lhs.value ) < 0;
    else
        return lhs.value->level() > rhs.value->level();
}

power() [1/2]

CanonicalForm power	(	const CanonicalForm &	f,
		int	n
	)

exponentiation

Definition at line 1896 of file canonicalform.cc.

{
  ASSERT( n >= 0, "illegal exponent" );
  if ( f.isZero() )
    return CanonicalForm(0L);
  else  if ( f.isOne() )
    return f;
  else  if ( f == -1 )
  {
    if ( n % 2 == 0 )
      return CanonicalForm(1L);
    else
      return CanonicalForm(-1L);
  }
  else  if ( n == 0 )
    return CanonicalForm(1L);
 
  //else if (f.inGF())
  //{
  //}
  else
  {
    CanonicalForm g,h;
    h=f;
    while(n%2==0)
    {
      h*=h;
      n/=2;
    }
    g=h;
    while(1)
    {
      n/=2;
      if(n==0)
        return g;
      h*=h;
      if(n%2!=0) g*=h;
    }
  }
}

power() [2/2]

CanonicalForm power	(	const Variable &	v,
		int	n
	)

exponentiation

Definition at line 1939 of file canonicalform.cc.

{
    //ASSERT( n >= 0, "illegal exponent" );
    if ( n == 0 )
        return 1;
    else  if ( n == 1 )
        return v;
    else  if (( v.level() < 0 ) && (hasMipo(v)))
    {
        CanonicalForm result( v, n-1 );
        return result * v;
    }
    else
        return CanonicalForm( v, n );
}

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 at line 1108 of file canonicalform.cc.

{
    ASSERT (getCharacteristic() > 0, "expected positive characteristic");
    ASSERT (!getReduce (M.mvar()), "do not reduce modulo M");
    fail= false;
    InternalCF * qq = 0, * rr = 0;
    int what = is_imm( f.value );
    bool result = true;
    if ( what )
        if ( is_imm( g.value ) ) {
            if ( what == FFMARK )
                imm_divrem_p( f.value, g.value, qq, rr );
            else  if ( what == GFMARK )
                imm_divrem_gf( f.value, g.value, qq, rr );
        }
        else
            result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
    else  if ( (what=is_imm( g.value )) )
        result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
    else  if ( f.value->level() == g.value->level() )
        if ( f.value->levelcoeff() == g.value->levelcoeff() )
            result = f.value->tryDivremsamet( g.value, qq, rr, M, fail );
        else  if ( f.value->levelcoeff() > g.value->levelcoeff() )
            result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
        else
            result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
    else  if ( f.value->level() > g.value->level() )
        result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
    else
        result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
    if (fail)
    {
      q= 0;
      r= 0;
      return false;
    }
    if ( result ) {
        ASSERT( qq != 0 && rr != 0, "error in divrem" );
        q = CanonicalForm( qq );
        r = CanonicalForm( rr );
        q= reduce (q, M);
        r= reduce (r, M);
    }
    else {
        q = 0; r = 0;
    }
    return result;
}