Functions
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 "gfops.h"
#include "facMul.h"
#include "FLINTconvert.h"
#include <factory/cf_gmp.h>

Go to the source code of this file.

Functions

CanonicalForm readCF (ISTREAM &)
 
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)
 
OSTREAMoperator<< (OSTREAM &os, const CanonicalForm &cf)
 
ISTREAMoperator>> (ISTREAM &is, CanonicalForm &cf)
 
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 )

bextgcd() - return base coefficient extended gcd.

Definition at line 1665 of file canonicalform.cc.

1666 {
1667  // check immediate cases
1668  int what = is_imm( g.value );
1669  if ( is_imm( f.value ) ) {
1670  ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
1671  if ( what == 0 )
1672  return g.value->bextgcdcoeff( f.value, b, a );
1673  else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) {
1674  // calculate extended gcd using standard integer
1675  // arithmetic
1676  long fInt = imm2int( f.value );
1677  long gInt = imm2int( g.value );
1678 
1679  // to avoid any system dpendencies with `%', we work
1680  // with positive numbers only. To a pity, we have to
1681  // redo all the checks when assigning to a and b.
1682  if ( fInt < 0 ) fInt = -fInt;
1683  if ( gInt < 0 ) gInt = -gInt;
1684  // swap fInt and gInt
1685  if ( gInt > fInt ) {
1686  long swap = gInt;
1687  gInt = fInt;
1688  fInt = swap;
1689  }
1690 
1691  long u = 1; long v = 0;
1692  long uNext = 0; long vNext = 1;
1693 
1694  // at any step, we have:
1695  // fInt_0 * u + gInt_0 * v = fInt
1696  // fInt_0 * uNext + gInt_0 * vNext = gInt
1697  // where fInt_0 and gInt_0 denote the values of fint
1698  // and gInt, resp., at the beginning
1699  while ( gInt ) {
1700  long r = fInt % gInt;
1701  long q = fInt / gInt;
1702  long uSwap = u - q * uNext;
1703  long vSwap = v - q * vNext;
1704 
1705  // update variables
1706  fInt = gInt;
1707  gInt = r;
1708  u = uNext; v = vNext;
1709  uNext = uSwap; vNext = vSwap;
1710  }
1711 
1712  // now, assign to a and b
1713  long fTest = imm2int( f.value );
1714  long gTest = imm2int( g.value );
1715  if ( gTest > fTest ) {
1716  a = v; b = u;
1717  } else {
1718  a = u; b = v;
1719  }
1720  if ( fTest < 0 ) a = -a;
1721  if ( gTest < 0 ) b = -b;
1722  return CanonicalForm( fInt );
1723  } else
1724  // stupid special cases
1725  if ( ! f.isZero() ) {
1726  a = 1/f; b = 0; return CanonicalForm( 1 );
1727  } else if ( ! g.isZero() ) {
1728  a = 0; b = 1/g; return CanonicalForm( 1 );
1729  } else {
1730  a = 0; b = 0; return CanonicalForm( 0 );
1731  }
1732  }
1733  else if ( what )
1734  return f.value->bextgcdcoeff( g.value, a, b );
1735 
1736  int fLevel = f.value->level();
1737  int gLevel = g.value->level();
1738 
1739  // check levels
1740  if ( fLevel == gLevel ) {
1741  fLevel = f.value->levelcoeff();
1742  gLevel = g.value->levelcoeff();
1743 
1744  // check levelcoeffs
1745  if ( fLevel == gLevel )
1746  return f.value->bextgcdsame( g.value, a, b );
1747  else if ( fLevel < gLevel )
1748  return g.value->bextgcdcoeff( f.value, b, a );
1749  else
1750  return f.value->bextgcdcoeff( g.value, a, b );
1751  }
1752  else if ( fLevel < gLevel )
1753  return g.value->bextgcdcoeff( f.value, b, a );
1754  else
1755  return f.value->bextgcdcoeff( g.value, a, b );
1756 }
const poly a
Definition: syzextra.cc:212
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
virtual InternalCF * bextgcdsame(InternalCF *, CanonicalForm &, CanonicalForm &)
InternalCF * InternalCF::bextgcdsame ( InternalCF *, CanonicalForm & a, CanonicalForm & b ) ...
Definition: int_cf.cc:149
g
Definition: cfModGcd.cc:4031
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
const ring r
Definition: syzextra.cc:208
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
FILE * f
Definition: checklibs.c:9
InternalCF * value
Definition: canonicalform.h:81
virtual InternalCF * bextgcdcoeff(InternalCF *, CanonicalForm &, CanonicalForm &)
Definition: int_cf.cc:157
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
long imm2int(const InternalCF *const imm)
Definition: imm.h:66
#define swap(_i, _j)
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
const long INTMARK
Definition: imm.h:37
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
#define ASSERT(expression, message)
Definition: cf_assert.h:99
const poly b
Definition: syzextra.cc:213

◆ bgcd()

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 1591 of file canonicalform.cc.

1592 {
1593  // check immediate cases
1594  int what = is_imm( g.value );
1595  if ( is_imm( f.value ) )
1596  {
1597  ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
1598  if ( what == 0 )
1599  return g.value->bgcdcoeff( f.value );
1600  else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) )
1601  {
1602  // calculate gcd using standard integer
1603  // arithmetic
1604  long fInt = imm2int( f.value );
1605  long gInt = imm2int( g.value );
1606 
1607  if ( fInt < 0 ) fInt = -fInt;
1608  if ( gInt < 0 ) gInt = -gInt;
1609  // swap fInt and gInt
1610  if ( gInt > fInt )
1611  {
1612  long swap = gInt;
1613  gInt = fInt;
1614  fInt = swap;
1615  }
1616 
1617  // now, 0 <= gInt <= fInt. Start the loop.
1618  while ( gInt )
1619  {
1620  // calculate (fInt, gInt) = (gInt, fInt%gInt)
1621  long r = fInt % gInt;
1622  fInt = gInt;
1623  gInt = r;
1624  }
1625 
1626  return CanonicalForm( fInt );
1627  }
1628  else
1629  // we do not go for maximal speed for these stupid
1630  // special cases
1631  return CanonicalForm( f.isZero() && g.isZero() ? 0 : 1 );
1632  }
1633  else if ( what )
1634  return f.value->bgcdcoeff( g.value );
1635 
1636  int fLevel = f.value->level();
1637  int gLevel = g.value->level();
1638 
1639  // check levels
1640  if ( fLevel == gLevel )
1641  {
1642  fLevel = f.value->levelcoeff();
1643  gLevel = g.value->levelcoeff();
1644 
1645  // check levelcoeffs
1646  if ( fLevel == gLevel )
1647  return f.value->bgcdsame( g.value );
1648  else if ( fLevel < gLevel )
1649  return g.value->bgcdcoeff( f.value );
1650  else
1651  return f.value->bgcdcoeff( g.value );
1652  }
1653  else if ( fLevel < gLevel )
1654  return g.value->bgcdcoeff( f.value );
1655  else
1656  return f.value->bgcdcoeff( g.value );
1657 }
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
virtual InternalCF * bgcdcoeff(const InternalCF *const)
Definition: int_cf.cc:139
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
const ring r
Definition: syzextra.cc:208
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
InternalCF * value
Definition: canonicalform.h:81
long imm2int(const InternalCF *const imm)
Definition: imm.h:66
#define swap(_i, _j)
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
virtual InternalCF * bgcdsame(const InternalCF *const) const
InternalCF * InternalCF::bgcdsame, bgcdcoeff ( const InternalCF * const )
Definition: int_cf.cc:132
const long INTMARK
Definition: imm.h:37
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ blcm()

Definition at line 1759 of file canonicalform.cc.

1760 {
1761  if ( f.isZero() || g.isZero() )
1762  return CanonicalForm( 0 );
1763 /*
1764  else if (f.isOne())
1765  return g;
1766  else if (g.isOne())
1767  return f;
1768 */
1769  else
1770  return (f / bgcd( f, g )) * g;
1771 }
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )

◆ divrem()

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

Definition at line 969 of file canonicalform.cc.

970 {
971  InternalCF * qq = 0, * rr = 0;
972  int what = is_imm( f.value );
973  if ( what )
974  if ( is_imm( g.value ) ) {
975  if ( what == FFMARK )
976  imm_divrem_p( f.value, g.value, qq, rr );
977  else if ( what == GFMARK )
978  imm_divrem_gf( f.value, g.value, qq, rr );
979  else
980  imm_divrem( f.value, g.value, qq, rr );
981  }
982  else
983  g.value->divremcoeff( f.value, qq, rr, true );
984  else if ( (what=is_imm( g.value )) )
985  f.value->divremcoeff( g.value, qq, rr, false );
986  else if ( f.value->level() == g.value->level() )
987  if ( f.value->levelcoeff() == g.value->levelcoeff() )
988  f.value->divremsame( g.value, qq, rr );
989  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
990  f.value->divremcoeff( g.value, qq, rr, false );
991  else
992  g.value->divremcoeff( f.value, qq, rr, true );
993  else if ( f.value->level() > g.value->level() )
994  f.value->divremcoeff( g.value, qq, rr, false );
995  else
996  g.value->divremcoeff( f.value, qq, rr, true );
997  ASSERT( qq != 0 && rr != 0, "error in divrem" );
998  q = CanonicalForm( qq );
999  r = CanonicalForm( rr );
1000 }
const long GFMARK
Definition: imm.h:39
virtual void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool) PVIRT_VOID("divremcoeff")
factory&#39;s main class
Definition: canonicalform.h:75
const long FFMARK
Definition: imm.h:38
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
void imm_divrem(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:424
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:442
InternalCF * value
Definition: canonicalform.h:81
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:436
#define ASSERT(expression, message)
Definition: cf_assert.h:99
virtual void divremsame(InternalCF *, InternalCF *&, InternalCF *&) PVIRT_VOID("divremsame")

◆ divremt()

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

Definition at line 1003 of file canonicalform.cc.

1004 {
1005  InternalCF * qq = 0, * rr = 0;
1006  int what = is_imm( f.value );
1007  bool result = true;
1008  if ( what )
1009  if ( is_imm( g.value ) ) {
1010  if ( what == FFMARK )
1011  imm_divrem_p( f.value, g.value, qq, rr );
1012  else if ( what == GFMARK )
1013  imm_divrem_gf( f.value, g.value, qq, rr );
1014  else
1015  imm_divrem( f.value, g.value, qq, rr );
1016  }
1017  else
1018  result = g.value->divremcoefft( f.value, qq, rr, true );
1019  else if ( (what=is_imm( g.value )) )
1020  result = f.value->divremcoefft( g.value, qq, rr, false );
1021  else if ( f.value->level() == g.value->level() )
1022  if ( f.value->levelcoeff() == g.value->levelcoeff() )
1023  result = f.value->divremsamet( g.value, qq, rr );
1024  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1025  result = f.value->divremcoefft( g.value, qq, rr, false );
1026  else
1027  result = g.value->divremcoefft( f.value, qq, rr, true );
1028  else if ( f.value->level() > g.value->level() )
1029  result = f.value->divremcoefft( g.value, qq, rr, false );
1030  else
1031  result = g.value->divremcoefft( f.value, qq, rr, true );
1032  if ( result ) {
1033  ASSERT( qq != 0 && rr != 0, "error in divrem" );
1034  q = CanonicalForm( qq );
1035  r = CanonicalForm( rr );
1036  }
1037  else {
1038  q = 0; r = 0;
1039  }
1040  return result;
1041 }
const long GFMARK
Definition: imm.h:39
factory&#39;s main class
Definition: canonicalform.h:75
const long FFMARK
Definition: imm.h:38
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
void imm_divrem(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:424
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:442
InternalCF * value
Definition: canonicalform.h:81
virtual bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool) PVIRT_BOOL("divremcoefft")
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:436
virtual bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&) PVIRT_BOOL("divremsamet")
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76

◆ isOn()

bool isOn ( int  sw)

switches

Definition at line 1914 of file canonicalform.cc.

1915 {
1916  return cf_glob_switches.isOn( sw );
1917 }
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75

◆ Off()

void Off ( int  sw)

switches

Definition at line 1907 of file canonicalform.cc.

1908 {
1909  cf_glob_switches.Off( sw );
1910 }
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75

◆ On()

void On ( int  sw)

switches

Definition at line 1900 of file canonicalform.cc.

1901 {
1902  cf_glob_switches.On( sw );
1903 }
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75

◆ 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 1435 of file canonicalform.cc.

1436 {
1437  if ( lhs.value == rhs.value )
1438  return false;
1439  else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
1440  ASSERT( ! is_imm( rhs.value ) ||
1441  ! is_imm( lhs.value ) ||
1442  is_imm( rhs.value ) == is_imm( lhs.value ),
1443  "incompatible operands" );
1444  return true;
1445  }
1446  else if ( lhs.value->level() != rhs.value->level() )
1447  return true;
1448  else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
1449  return true;
1450  else return rhs.value->comparesame( lhs.value ) != 0;
1451 }
virtual int comparesame(InternalCF *) PVIRT_INT("comparesame")
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
InternalCF * value
Definition: canonicalform.h:81
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ operator<()

bool operator< ( const CanonicalForm lhs,
const CanonicalForm rhs 
)
See also
CanonicalForm::operator >()

Definition at line 1529 of file canonicalform.cc.

1530 {
1531  int what = is_imm( rhs.value );
1532  if ( is_imm( lhs.value ) ) {
1533  ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
1534  if ( what == 0 )
1535  return rhs.value->comparecoeff( lhs.value ) > 0;
1536  else if ( what == INTMARK )
1537  return imm_cmp( lhs.value, rhs.value ) < 0;
1538  else if ( what == FFMARK )
1539  return imm_cmp_p( lhs.value, rhs.value ) < 0;
1540  else
1541  return imm_cmp_gf( lhs.value, rhs.value ) < 0;
1542  }
1543  else if ( what )
1544  return lhs.value->comparecoeff( rhs.value ) < 0;
1545  else if ( lhs.value->level() == rhs.value->level() )
1546  if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
1547  return lhs.value->comparesame( rhs.value ) < 0;
1548  else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
1549  return lhs.value->comparecoeff( rhs.value ) < 0;
1550  else
1551  return rhs.value->comparecoeff( lhs.value ) > 0;
1552  else
1553  return lhs.value->level() < rhs.value->level();
1554 }
const long FFMARK
Definition: imm.h:38
int imm_cmp_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:241
virtual int comparesame(InternalCF *) PVIRT_INT("comparesame")
int imm_cmp(const InternalCF *const lhs, const InternalCF *const rhs)
imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
Definition: imm.h:230
virtual int comparecoeff(InternalCF *) PVIRT_INT("comparecoeff")
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
InternalCF * value
Definition: canonicalform.h:81
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
const long INTMARK
Definition: imm.h:37
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int imm_cmp_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:252

◆ operator<<()

OSTREAM& operator<< ( OSTREAM os,
const CanonicalForm cf 
)

Definition at line 1794 of file canonicalform.cc.

1795 {
1796  cf.print( os, "" );
1797  return os;
1798 }
void print(OSTREAM &, char *) const
input/output

◆ 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 `CanonicalFormisZero()' 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 1410 of file canonicalform.cc.

1411 {
1412  if ( lhs.value == rhs.value )
1413  return true;
1414  else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
1415  ASSERT( ! is_imm( rhs.value ) ||
1416  ! is_imm( lhs.value ) ||
1417  is_imm( rhs.value ) == is_imm( lhs.value ),
1418  "incompatible operands" );
1419  return false;
1420  }
1421  else if ( lhs.value->level() != rhs.value->level() )
1422  return false;
1423  else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
1424  return false;
1425  else
1426  return rhs.value->comparesame( lhs.value ) == 0;
1427 }
virtual int comparesame(InternalCF *) PVIRT_INT("comparesame")
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
InternalCF * value
Definition: canonicalform.h:81
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ 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 `InternalPolyoperator <()'.

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 1498 of file canonicalform.cc.

1499 {
1500  int what = is_imm( rhs.value );
1501  if ( is_imm( lhs.value ) ) {
1502  ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
1503  if ( what == 0 )
1504  return rhs.value->comparecoeff( lhs.value ) < 0;
1505  else if ( what == INTMARK )
1506  return imm_cmp( lhs.value, rhs.value ) > 0;
1507  else if ( what == FFMARK )
1508  return imm_cmp_p( lhs.value, rhs.value ) > 0;
1509  else
1510  return imm_cmp_gf( lhs.value, rhs.value ) > 0;
1511  }
1512  else if ( what )
1513  return lhs.value->comparecoeff( rhs.value ) > 0;
1514  else if ( lhs.value->level() == rhs.value->level() )
1515  if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
1516  return lhs.value->comparesame( rhs.value ) > 0;
1517  else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
1518  return lhs.value->comparecoeff( rhs.value ) > 0;
1519  else
1520  return rhs.value->comparecoeff( lhs.value ) < 0;
1521  else
1522  return lhs.value->level() > rhs.value->level();
1523 }
const long FFMARK
Definition: imm.h:38
int imm_cmp_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:241
virtual int comparesame(InternalCF *) PVIRT_INT("comparesame")
int imm_cmp(const InternalCF *const lhs, const InternalCF *const rhs)
imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
Definition: imm.h:230
virtual int comparecoeff(InternalCF *) PVIRT_INT("comparecoeff")
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
InternalCF * value
Definition: canonicalform.h:81
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
const long INTMARK
Definition: imm.h:37
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int imm_cmp_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:252

◆ operator>>()

ISTREAM& operator>> ( ISTREAM is,
CanonicalForm cf 
)

Definition at line 1801 of file canonicalform.cc.

1802 {
1803  cf = readCF( is );
1804  return is;
1805 }
CanonicalForm readCF(ISTREAM &)
Definition: readcf.cc:1616

◆ power() [1/2]

CanonicalForm power ( const CanonicalForm f,
int  n 
)

exponentiation

Definition at line 1839 of file canonicalform.cc.

1840 {
1841  ASSERT( n >= 0, "illegal exponent" );
1842  if ( f.isZero() )
1843  return 0;
1844  else if ( f.isOne() )
1845  return f;
1846  else if ( f == -1 )
1847  {
1848  if ( n % 2 == 0 )
1849  return 1;
1850  else
1851  return -1;
1852  }
1853  else if ( n == 0 )
1854  return 1;
1855 
1856  //else if (f.inGF())
1857  //{
1858  //}
1859  else
1860  {
1861  CanonicalForm g,h;
1862  h=f;
1863  while(n%2==0)
1864  {
1865  h*=h;
1866  n/=2;
1867  }
1868  g=h;
1869  while(1)
1870  {
1871  n/=2;
1872  if(n==0)
1873  return g;
1874  h*=h;
1875  if(n%2!=0) g*=h;
1876  }
1877  }
1878 }
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
FILE * f
Definition: checklibs.c:9
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static Poly * h
Definition: janet.cc:978

◆ power() [2/2]

CanonicalForm power ( const Variable v,
int  n 
)

exponentiation

Definition at line 1882 of file canonicalform.cc.

1883 {
1884  //ASSERT( n >= 0, "illegal exponent" );
1885  if ( n == 0 )
1886  return 1;
1887  else if ( n == 1 )
1888  return v;
1889  else if (( v.level() < 0 ) && (hasMipo(v)))
1890  {
1891  CanonicalForm result( v, n-1 );
1892  return result * v;
1893  }
1894  else
1895  return CanonicalForm( v, n );
1896 }
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
Definition: factory.h:132
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226
return result
Definition: facAbsBiFact.cc:76

◆ readCF()

CanonicalForm readCF ( ISTREAM )

Definition at line 1616 of file readcf.cc.

1617 {
1618  CanonicalForm theRetvalue;
1619  retvalue = new CanonicalForm();
1620 #ifdef BISONPP
1621  YY_parse_CLASS my_parser;
1622  defaultin = &str;
1623  if ( my_parser.yyparse() == 0 ) {
1624  theRetvalue = *retvalue;
1625  delete retvalue;
1626  return theRetvalue;
1627  }
1628  else {
1629  delete retvalue;
1630  return 0;
1631  }
1632 #else
1633  defaultin = &str;
1634  if ( yyparse() == 0 ) {
1635  theRetvalue = *retvalue;
1636  delete retvalue;
1637  return theRetvalue;
1638  }
1639  else {
1640  delete retvalue;
1641  return 0;
1642  }
1643 #endif
1644 }
static CanonicalForm * retvalue
Definition: readcf.cc:121
static ISTREAM * defaultin
Definition: readcf.cc:119
factory&#39;s main class
Definition: canonicalform.h:75
int yyparse(void)
Definition: readcf.cc:1026

◆ 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 1045 of file canonicalform.cc.

1046 {
1047  ASSERT (getCharacteristic() > 0, "expected positive characteristic");
1048  ASSERT (!getReduce (M.mvar()), "do not reduce modulo M");
1049  fail= false;
1050  InternalCF * qq = 0, * rr = 0;
1051  int what = is_imm( f.value );
1052  bool result = true;
1053  if ( what )
1054  if ( is_imm( g.value ) ) {
1055  if ( what == FFMARK )
1056  imm_divrem_p( f.value, g.value, qq, rr );
1057  else if ( what == GFMARK )
1058  imm_divrem_gf( f.value, g.value, qq, rr );
1059  }
1060  else
1061  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1062  else if ( (what=is_imm( g.value )) )
1063  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1064  else if ( f.value->level() == g.value->level() )
1065  if ( f.value->levelcoeff() == g.value->levelcoeff() )
1066  result = f.value->tryDivremsamet( g.value, qq, rr, M, fail );
1067  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1068  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1069  else
1070  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1071  else if ( f.value->level() > g.value->level() )
1072  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1073  else
1074  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1075  if (fail)
1076  {
1077  q= 0;
1078  r= 0;
1079  return false;
1080  }
1081  if ( result ) {
1082  ASSERT( qq != 0 && rr != 0, "error in divrem" );
1083  q = CanonicalForm( qq );
1084  r = CanonicalForm( rr );
1085  q= reduce (q, M);
1086  r= reduce (r, M);
1087  }
1088  else {
1089  q = 0; r = 0;
1090  }
1091  return result;
1092 }
const long GFMARK
Definition: imm.h:39
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:646
factory&#39;s main class
Definition: canonicalform.h:75
const long FFMARK
Definition: imm.h:38
int getCharacteristic()
Definition: cf_char.cc:51
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
virtual int levelcoeff() const
Definition: int_cf.h:64
virtual int level() const
Definition: int_cf.h:63
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:442
virtual bool tryDivremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
Definition: int_cf.cc:200
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
InternalCF * value
Definition: canonicalform.h:81
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:436
#define ASSERT(expression, message)
Definition: cf_assert.h:99
virtual bool tryDivremsamet(InternalCF *, InternalCF *&, InternalCF *&, const CanonicalForm &, bool &)
Definition: int_cf.cc:193
return result
Definition: facAbsBiFact.cc:76