My Project  debian-1:4.1.1-p2+ds-4build4
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"

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

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

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

1590 {
1591  // check immediate cases
1592  int what = is_imm( g.value );
1593  if ( is_imm( f.value ) )
1594  {
1595  ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" );
1596  if ( what == 0 )
1597  return g.value->bgcdcoeff( f.value );
1598  else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) )
1599  {
1600  // calculate gcd using standard integer
1601  // arithmetic
1602  long fInt = imm2int( f.value );
1603  long gInt = imm2int( g.value );
1604 
1605  if ( fInt < 0 ) fInt = -fInt;
1606  if ( gInt < 0 ) gInt = -gInt;
1607  // swap fInt and gInt
1608  if ( gInt > fInt )
1609  {
1610  long swap = gInt;
1611  gInt = fInt;
1612  fInt = swap;
1613  }
1614 
1615  // now, 0 <= gInt <= fInt. Start the loop.
1616  while ( gInt )
1617  {
1618  // calculate (fInt, gInt) = (gInt, fInt%gInt)
1619  long r = fInt % gInt;
1620  fInt = gInt;
1621  gInt = r;
1622  }
1623 
1624  return CanonicalForm( fInt );
1625  }
1626  else
1627  // we do not go for maximal speed for these stupid
1628  // special cases
1629  return CanonicalForm( f.isZero() && g.isZero() ? 0 : 1 );
1630  }
1631  else if ( what )
1632  return f.value->bgcdcoeff( g.value );
1633 
1634  int fLevel = f.value->level();
1635  int gLevel = g.value->level();
1636 
1637  // check levels
1638  if ( fLevel == gLevel )
1639  {
1640  fLevel = f.value->levelcoeff();
1641  gLevel = g.value->levelcoeff();
1642 
1643  // check levelcoeffs
1644  if ( fLevel == gLevel )
1645  return f.value->bgcdsame( g.value );
1646  else if ( fLevel < gLevel )
1647  return g.value->bgcdcoeff( f.value );
1648  else
1649  return f.value->bgcdcoeff( g.value );
1650  }
1651  else if ( fLevel < gLevel )
1652  return g.value->bgcdcoeff( f.value );
1653  else
1654  return f.value->bgcdcoeff( g.value );
1655 }

◆ blcm()

Definition at line 1757 of file canonicalform.cc.

1758 {
1759  if ( f.isZero() || g.isZero() )
1760  return CanonicalForm( 0L );
1761 /*
1762  else if (f.isOne())
1763  return g;
1764  else if (g.isOne())
1765  return f;
1766 */
1767  else
1768  return (f / bgcd( f, g )) * g;
1769 }
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 967 of file canonicalform.cc.

968 {
969  InternalCF * qq = 0, * rr = 0;
970  int what = is_imm( f.value );
971  if ( what )
972  if ( is_imm( g.value ) ) {
973  if ( what == FFMARK )
974  imm_divrem_p( f.value, g.value, qq, rr );
975  else if ( what == GFMARK )
976  imm_divrem_gf( f.value, g.value, qq, rr );
977  else
978  imm_divrem( f.value, g.value, qq, rr );
979  }
980  else
981  g.value->divremcoeff( f.value, qq, rr, true );
982  else if ( (what=is_imm( g.value )) )
983  f.value->divremcoeff( g.value, qq, rr, false );
984  else if ( f.value->level() == g.value->level() )
985  if ( f.value->levelcoeff() == g.value->levelcoeff() )
986  f.value->divremsame( g.value, qq, rr );
987  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
988  f.value->divremcoeff( g.value, qq, rr, false );
989  else
990  g.value->divremcoeff( f.value, qq, rr, true );
991  else if ( f.value->level() > g.value->level() )
992  f.value->divremcoeff( g.value, qq, rr, false );
993  else
994  g.value->divremcoeff( f.value, qq, rr, true );
995  ASSERT( qq != 0 && rr != 0, "error in divrem" );
996  q = CanonicalForm( qq );
997  r = CanonicalForm( rr );
998 }
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:446
const long FFMARK
Definition: imm.h:38
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:440
const long GFMARK
Definition: imm.h:39
void imm_divrem(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:428

◆ divremt()

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

Definition at line 1001 of file canonicalform.cc.

1002 {
1003  InternalCF * qq = 0, * rr = 0;
1004  int what = is_imm( f.value );
1005  bool result = true;
1006  if ( what )
1007  if ( is_imm( g.value ) ) {
1008  if ( what == FFMARK )
1009  imm_divrem_p( f.value, g.value, qq, rr );
1010  else if ( what == GFMARK )
1011  imm_divrem_gf( f.value, g.value, qq, rr );
1012  else
1013  imm_divrem( f.value, g.value, qq, rr );
1014  }
1015  else
1016  result = g.value->divremcoefft( f.value, qq, rr, true );
1017  else if ( (what=is_imm( g.value )) )
1018  result = f.value->divremcoefft( g.value, qq, rr, false );
1019  else if ( f.value->level() == g.value->level() )
1020  if ( f.value->levelcoeff() == g.value->levelcoeff() )
1021  result = f.value->divremsamet( g.value, qq, rr );
1022  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1023  result = f.value->divremcoefft( g.value, qq, rr, false );
1024  else
1025  result = g.value->divremcoefft( f.value, qq, rr, true );
1026  else if ( f.value->level() > g.value->level() )
1027  result = f.value->divremcoefft( g.value, qq, rr, false );
1028  else
1029  result = g.value->divremcoefft( f.value, qq, rr, true );
1030  if ( result ) {
1031  ASSERT( qq != 0 && rr != 0, "error in divrem" );
1032  q = CanonicalForm( qq );
1033  r = CanonicalForm( rr );
1034  }
1035  else {
1036  q = 0; r = 0;
1037  }
1038  return result;
1039 }
return result
Definition: facAbsBiFact.cc:76

◆ isOn()

bool isOn ( int  sw)

switches

Definition at line 1912 of file canonicalform.cc.

1913 {
1914  return cf_glob_switches.isOn( sw );
1915 }

◆ Off()

void Off ( int  sw)

switches

Definition at line 1905 of file canonicalform.cc.

1906 {
1907  cf_glob_switches.Off( sw );
1908 }
void Off(int s)
switch 's' off
Definition: cf_switches.h:53

◆ On()

void On ( int  sw)

switches

Definition at line 1898 of file canonicalform.cc.

1899 {
1900  cf_glob_switches.On( sw );
1901 }
void On(int s)
switch 's' on
Definition: cf_switches.h:51

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

1434 {
1435  if ( lhs.value == rhs.value )
1436  return false;
1437  else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
1438  ASSERT( ! is_imm( rhs.value ) ||
1439  ! is_imm( lhs.value ) ||
1440  is_imm( rhs.value ) == is_imm( lhs.value ),
1441  "incompatible operands" );
1442  return true;
1443  }
1444  else if ( lhs.value->level() != rhs.value->level() )
1445  return true;
1446  else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
1447  return true;
1448  else return rhs.value->comparesame( lhs.value ) != 0;
1449 }
InternalCF * value
Definition: canonicalform.h:85
virtual int levelcoeff() const
Definition: int_cf.h:68
virtual int comparesame(InternalCF *) PVIRT_INT("comparesame")
virtual int level() const
Definition: int_cf.h:67

◆ operator<()

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

Definition at line 1526 of file canonicalform.cc.

1528 {
1529  int what = is_imm( rhs.value );
1530  if ( is_imm( lhs.value ) ) {
1531  ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
1532  if ( what == 0 )
1533  return rhs.value->comparecoeff( lhs.value ) > 0;
1534  else if ( what == INTMARK )
1535  return imm_cmp( lhs.value, rhs.value ) < 0;
1536  else if ( what == FFMARK )
1537  return imm_cmp_p( lhs.value, rhs.value ) < 0;
1538  else
1539  return imm_cmp_gf( lhs.value, rhs.value ) < 0;
1540  }
1541  else if ( what )
1542  return lhs.value->comparecoeff( rhs.value ) < 0;
1543  else if ( lhs.value->level() == rhs.value->level() )
1544  if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
1545  return lhs.value->comparesame( rhs.value ) < 0;
1546  else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
1547  return lhs.value->comparecoeff( rhs.value ) < 0;
1548  else
1549  return rhs.value->comparecoeff( lhs.value ) > 0;
1550  else
1551  return lhs.value->level() < rhs.value->level();
1552 }
virtual int comparecoeff(InternalCF *) PVIRT_INT("comparecoeff")
int imm_cmp_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:245
int imm_cmp_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:256
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:234

◆ operator<<()

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

Definition at line 1791 of file canonicalform.cc.

1793 {
1794  cf.print( os, "" );
1795  return os;
1796 }
CanonicalForm cf
Definition: cfModGcd.cc:4024
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 ‘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 1408 of file canonicalform.cc.

1409 {
1410  if ( lhs.value == rhs.value )
1411  return true;
1412  else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) {
1413  ASSERT( ! is_imm( rhs.value ) ||
1414  ! is_imm( lhs.value ) ||
1415  is_imm( rhs.value ) == is_imm( lhs.value ),
1416  "incompatible operands" );
1417  return false;
1418  }
1419  else if ( lhs.value->level() != rhs.value->level() )
1420  return false;
1421  else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() )
1422  return false;
1423  else
1424  return rhs.value->comparesame( lhs.value ) == 0;
1425 }

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

1497 {
1498  int what = is_imm( rhs.value );
1499  if ( is_imm( lhs.value ) ) {
1500  ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" );
1501  if ( what == 0 )
1502  return rhs.value->comparecoeff( lhs.value ) < 0;
1503  else if ( what == INTMARK )
1504  return imm_cmp( lhs.value, rhs.value ) > 0;
1505  else if ( what == FFMARK )
1506  return imm_cmp_p( lhs.value, rhs.value ) > 0;
1507  else
1508  return imm_cmp_gf( lhs.value, rhs.value ) > 0;
1509  }
1510  else if ( what )
1511  return lhs.value->comparecoeff( rhs.value ) > 0;
1512  else if ( lhs.value->level() == rhs.value->level() )
1513  if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
1514  return lhs.value->comparesame( rhs.value ) > 0;
1515  else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
1516  return lhs.value->comparecoeff( rhs.value ) > 0;
1517  else
1518  return rhs.value->comparecoeff( lhs.value ) < 0;
1519  else
1520  return lhs.value->level() > rhs.value->level();
1521 }

◆ operator>>()

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

Definition at line 1799 of file canonicalform.cc.

1800 {
1801  cf = readCF( is );
1802  return is;
1803 }
CanonicalForm readCF(ISTREAM &)

◆ power() [1/2]

CanonicalForm power ( const CanonicalForm f,
int  n 
)

exponentiation

Definition at line 1837 of file canonicalform.cc.

1838 {
1839  ASSERT( n >= 0, "illegal exponent" );
1840  if ( f.isZero() )
1841  return CanonicalForm(0L);
1842  else if ( f.isOne() )
1843  return f;
1844  else if ( f == -1 )
1845  {
1846  if ( n % 2 == 0 )
1847  return CanonicalForm(1L);
1848  else
1849  return CanonicalForm(-1L);
1850  }
1851  else if ( n == 0 )
1852  return CanonicalForm(1L);
1853 
1854  //else if (f.inGF())
1855  //{
1856  //}
1857  else
1858  {
1859  CanonicalForm g,h;
1860  h=f;
1861  while(n%2==0)
1862  {
1863  h*=h;
1864  n/=2;
1865  }
1866  g=h;
1867  while(1)
1868  {
1869  n/=2;
1870  if(n==0)
1871  return g;
1872  h*=h;
1873  if(n%2!=0) g*=h;
1874  }
1875  }
1876 }
static Poly * h
Definition: janet.cc:972

◆ power() [2/2]

CanonicalForm power ( const Variable v,
int  n 
)

exponentiation

Definition at line 1880 of file canonicalform.cc.

1881 {
1882  //ASSERT( n >= 0, "illegal exponent" );
1883  if ( n == 0 )
1884  return 1;
1885  else if ( n == 1 )
1886  return v;
1887  else if (( v.level() < 0 ) && (hasMipo(v)))
1888  {
1889  CanonicalForm result( v, n-1 );
1890  return result * v;
1891  }
1892  else
1893  return CanonicalForm( v, n );
1894 }
int level() const
Definition: factory.h:134
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226

◆ readCF()

CanonicalForm readCF ( ISTREAM )

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

1044 {
1045  ASSERT (getCharacteristic() > 0, "expected positive characteristic");
1046  ASSERT (!getReduce (M.mvar()), "do not reduce modulo M");
1047  fail= false;
1048  InternalCF * qq = 0, * rr = 0;
1049  int what = is_imm( f.value );
1050  bool result = true;
1051  if ( what )
1052  if ( is_imm( g.value ) ) {
1053  if ( what == FFMARK )
1054  imm_divrem_p( f.value, g.value, qq, rr );
1055  else if ( what == GFMARK )
1056  imm_divrem_gf( f.value, g.value, qq, rr );
1057  }
1058  else
1059  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1060  else if ( (what=is_imm( g.value )) )
1061  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1062  else if ( f.value->level() == g.value->level() )
1063  if ( f.value->levelcoeff() == g.value->levelcoeff() )
1064  result = f.value->tryDivremsamet( g.value, qq, rr, M, fail );
1065  else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1066  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1067  else
1068  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1069  else if ( f.value->level() > g.value->level() )
1070  result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail );
1071  else
1072  result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail );
1073  if (fail)
1074  {
1075  q= 0;
1076  r= 0;
1077  return false;
1078  }
1079  if ( result ) {
1080  ASSERT( qq != 0 && rr != 0, "error in divrem" );
1081  q = CanonicalForm( qq );
1082  r = CanonicalForm( rr );
1083  q= reduce (q, M);
1084  r= reduce (r, M);
1085  }
1086  else {
1087  q = 0; r = 0;
1088  }
1089  return result;
1090 }
int getCharacteristic()
Definition: cf_char.cc:51
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
#define M
Definition: sirandom.c:24
bool getReduce(const Variable &alpha)
Definition: variable.cc:232