FORM 4.3
poly Class Reference

Public Member Functions

 poly (PHEAD int, WORD=-1, WORD=1)
 poly (PHEAD const UWORD *, WORD, WORD=-1, WORD=1)
 poly (const poly &, WORD=-1, WORD=1)
polyoperator+= (const poly &)
polyoperator-= (const poly &)
polyoperator*= (const poly &)
polyoperator/= (const poly &)
polyoperator%= (const poly &)
const poly operator+ (const poly &) const
const poly operator- (const poly &) const
const poly operator* (const poly &) const
const poly operator/ (const poly &) const
const poly operator% (const poly &) const
bool operator== (const poly &) const
bool operator!= (const poly &) const
polyoperator= (const poly &)
WORD & operator[] (int)
const WORD & operator[] (int) const
void termscopy (const WORD *, int, int)
void check_memory (int)
void expand_memory (int)
bool is_zero () const
bool is_one () const
bool is_integer () const
bool is_monomial () const
int is_dense_univariate () const
int sign () const
int degree (int) const
int total_degree () const
int first_variable () const
int number_of_terms () const
const std::vector< int > all_variables () const
const poly integer_lcoeff () const
const poly lcoeff_univar (int) const
const poly lcoeff_multivar (int) const
const poly coefficient (int, int) const
const poly derivative (int) const
void setmod (WORD, WORD=1)
void coefficients_modulo (UWORD *, WORD, bool)
int size_of_form_notation () const
int size_of_form_notation_with_den (WORD) const
const polynormalize ()
const std::string to_string () const
WORD last_monomial_index () const
WORD * last_monomial () const
int compare_degree_vector (const poly &) const
std::vector< int > degree_vector () const
int compare_degree_vector (const std::vector< int > &) const

Static Public Member Functions

static const poly simple_poly (PHEAD int, int=0, int=1, int=0, int=1)
static const poly simple_poly (PHEAD int, const poly &, int=1, int=0, int=1)
static void get_variables (PHEAD std::vector< WORD * >, bool, bool)
static const poly argument_to_poly (PHEAD WORD *, bool, bool, poly *den=NULL)
static void poly_to_argument (const poly &, WORD *, bool)
static void poly_to_argument_with_den (const poly &, WORD, const UWORD *, WORD *, bool)
static const poly from_coefficient_list (PHEAD const std::vector< WORD > &, int, WORD)
static const std::vector< WORD > to_coefficient_list (const poly &)
static const std::vector< WORD > coefficient_list_divmod (const std::vector< WORD > &, const std::vector< WORD > &, WORD, int)
static int monomial_compare (PHEAD const WORD *, const WORD *)
static void add (const poly &, const poly &, poly &)
static void sub (const poly &, const poly &, poly &)
static void mul (const poly &, const poly &, poly &)
static void div (const poly &, const poly &, poly &)
static void mod (const poly &, const poly &, poly &)
static void divmod (const poly &, const poly &, poly &, poly &, bool only_divides)
static bool divides (const poly &, const poly &)
static void mul_one_term (const poly &, const poly &, poly &)
static void mul_univar (const poly &, const poly &, poly &, int)
static void mul_heap (const poly &, const poly &, poly &)
static void divmod_one_term (const poly &, const poly &, poly &, poly &, bool)
static void divmod_univar (const poly &, const poly &, poly &, poly &, int, bool)
static void divmod_heap (const poly &, const poly &, poly &, poly &, bool, bool, bool &)
static void push_heap (PHEAD WORD **, int)
static void pop_heap (PHEAD WORD **, int)

Data Fields

WORD * terms
LONG size_of_terms
WORD modp
WORD modn

Detailed Description

Definition at line 49 of file poly.h.

Constructor & Destructor Documentation

◆ poly() [1/3]

poly ( PHEAD int a,
WORD modp = -1,
WORD modn = 1 )

Definition at line 53 of file poly.cc.

◆ poly() [2/3]

poly ( PHEAD const UWORD * a,
WORD na,
WORD modp = -1,
WORD modn = 1 )

Definition at line 82 of file poly.cc.

◆ poly() [3/3]

poly ( const poly & a,
WORD modp = -1,
WORD modn = 1 )

Definition at line 110 of file poly.cc.

◆ ~poly()

~poly ( )

Definition at line 129 of file poly.cc.

Member Function Documentation

◆ operator+=()

poly & operator+= ( const poly & a)

Definition at line 1960 of file poly.cc.

◆ operator-=()

poly & operator-= ( const poly & a)

Definition at line 1961 of file poly.cc.

◆ operator*=()

poly & operator*= ( const poly & a)

Definition at line 1962 of file poly.cc.

◆ operator/=()

poly & operator/= ( const poly & a)

Definition at line 1963 of file poly.cc.

◆ operator%=()

poly & operator%= ( const poly & a)

Definition at line 1964 of file poly.cc.

◆ operator+()

const poly operator+ ( const poly & a) const

Definition at line 1953 of file poly.cc.

◆ operator-()

const poly operator- ( const poly & a) const

Definition at line 1954 of file poly.cc.

◆ operator*()

const poly operator* ( const poly & a) const

Definition at line 1955 of file poly.cc.

◆ operator/()

const poly operator/ ( const poly & a) const

Definition at line 1956 of file poly.cc.

◆ operator%()

const poly operator% ( const poly & a) const

Definition at line 1957 of file poly.cc.

◆ operator==()

bool operator== ( const poly & a) const

Definition at line 1967 of file poly.cc.

◆ operator!=()

bool operator!= ( const poly & a) const

Definition at line 1973 of file poly.cc.

◆ operator=()

poly & operator= ( const poly & a)

Definition at line 1935 of file poly.cc.

◆ operator[]() [1/2]

WORD & operator[] ( int i)
inline

Definition at line 201 of file poly.h.

◆ operator[]() [2/2]

const WORD & operator[] ( int i) const
inline

Definition at line 205 of file poly.h.

◆ termscopy()

void termscopy ( const WORD * source,
int dest,
int num )
inline

Definition at line 212 of file poly.h.

◆ check_memory()

void check_memory ( int i)
inline

Definition at line 194 of file poly.h.

◆ expand_memory()

void expand_memory ( int i)

Definition at line 145 of file poly.cc.

◆ is_zero()

bool is_zero ( ) const

Definition at line 2203 of file poly.cc.

◆ is_one()

bool is_one ( ) const

Definition at line 2213 of file poly.cc.

◆ is_integer()

bool is_integer ( ) const

Definition at line 2233 of file poly.cc.

◆ is_monomial()

bool is_monomial ( ) const

Definition at line 2253 of file poly.cc.

◆ is_dense_univariate()

int is_dense_univariate ( ) const

Dense univariate detection

Description

This method returns whether the polynomial is dense and univariate. The possible return values are:

-2 is not dense univariate -1 is no variables n>=0 is univariate in n

Notes

A univariate polynomial is considered dense iff more than half of the coefficients a_0...a_deg are non-zero.

Definition at line 2278 of file poly.cc.

Referenced by divmod(), and mul().

◆ sign()

int sign ( ) const

Definition at line 2033 of file poly.cc.

◆ degree()

int degree ( int x) const

Definition at line 2044 of file poly.cc.

◆ total_degree()

int total_degree ( ) const

Definition at line 2057 of file poly.cc.

◆ first_variable()

int first_variable ( ) const

Definition at line 1994 of file poly.cc.

◆ number_of_terms()

int number_of_terms ( ) const

Definition at line 1980 of file poly.cc.

◆ all_variables()

const vector< int > all_variables ( ) const

Definition at line 2010 of file poly.cc.

◆ integer_lcoeff()

const poly integer_lcoeff ( ) const

Definition at line 2077 of file poly.cc.

◆ lcoeff_univar()

const poly lcoeff_univar ( int x) const

Definition at line 2127 of file poly.cc.

◆ lcoeff_multivar()

const poly lcoeff_multivar ( int x) const

Definition at line 2134 of file poly.cc.

◆ coefficient()

const poly coefficient ( int x,
int n ) const

Definition at line 2099 of file poly.cc.

◆ derivative()

const poly derivative ( int x) const

Definition at line 2166 of file poly.cc.

◆ setmod()

void setmod ( WORD _modp,
WORD _modn = 1 )

Definition at line 175 of file poly.cc.

◆ coefficients_modulo()

void coefficients_modulo ( UWORD * a,
WORD na,
bool small )

Definition at line 211 of file poly.cc.

◆ simple_poly() [1/2]

const poly simple_poly ( PHEAD int x,
int a = 0,
int b = 1,
int p = 0,
int n = 1 )
static

Definition at line 2311 of file poly.cc.

◆ simple_poly() [2/2]

const poly simple_poly ( PHEAD int x,
const poly & a,
int b = 1,
int p = 0,
int n = 1 )
static

Definition at line 2350 of file poly.cc.

◆ get_variables()

void get_variables ( PHEAD std::vector< WORD * > ,
bool ,
bool  )
static

Definition at line 2389 of file poly.cc.

◆ argument_to_poly()

const poly argument_to_poly ( PHEAD WORD * e,
bool with_arghead,
bool sort_univar,
poly * den = NULL )
static

Definition at line 2483 of file poly.cc.

◆ poly_to_argument()

void poly_to_argument ( const poly & a,
WORD * res,
bool with_arghead )
static

Definition at line 2584 of file poly.cc.

◆ poly_to_argument_with_den()

void poly_to_argument_with_den ( const poly & a,
WORD nden,
const UWORD * den,
WORD * res,
bool with_arghead )
static

Definition at line 2656 of file poly.cc.

◆ size_of_form_notation()

int size_of_form_notation ( ) const

Definition at line 2739 of file poly.cc.

◆ size_of_form_notation_with_den()

int size_of_form_notation_with_den ( WORD nden) const

Definition at line 2768 of file poly.cc.

◆ normalize()

const poly & normalize ( )

Definition at line 358 of file poly.cc.

◆ from_coefficient_list()

const poly from_coefficient_list ( PHEAD const std::vector< WORD > & ,
int ,
WORD  )
static

Definition at line 2858 of file poly.cc.

◆ to_coefficient_list()

const vector< WORD > to_coefficient_list ( const poly & a)
static

Definition at line 2796 of file poly.cc.

◆ coefficient_list_divmod()

const vector< WORD > coefficient_list_divmod ( const std::vector< WORD > & ,
const std::vector< WORD > & ,
WORD ,
int  )
static

Definition at line 2819 of file poly.cc.

◆ to_string()

const string to_string ( ) const

Definition at line 263 of file poly.cc.

◆ monomial_compare()

int monomial_compare ( PHEAD const WORD * a,
const WORD * b )
static

Definition at line 346 of file poly.cc.

◆ last_monomial_index()

WORD last_monomial_index ( ) const

Definition at line 461 of file poly.cc.

◆ last_monomial()

WORD * last_monomial ( ) const

Definition at line 468 of file poly.cc.

◆ compare_degree_vector()

int compare_degree_vector ( const poly & b) const

Definition at line 477 of file poly.cc.

◆ degree_vector()

std::vector< int > degree_vector ( ) const

Definition at line 499 of file poly.cc.

◆ add()

void add ( const poly & a,
const poly & b,
poly & c )
static

Definition at line 534 of file poly.cc.

◆ sub()

void sub ( const poly & a,
const poly & b,
poly & c )
static

Definition at line 618 of file poly.cc.

◆ mul()

void mul ( const poly & a,
const poly & b,
poly & c )
static

Polynomial multiplication

Description

This routine determines which multiplication routine to use for multiplying two polynomials. The logic is as follows:

  • If a or b consists of only one term, call mul_one_term;
  • Otherwise, if both are univariate and dense, call mul_univar;
  • Otherwise, call mul_heap.

Definition at line 1191 of file poly.cc.

References is_dense_univariate(), and mul_heap().

◆ div()

void div ( const poly & a,
const poly & b,
poly & c )
static

Definition at line 1911 of file poly.cc.

◆ mod()

void mod ( const poly & a,
const poly & b,
poly & c )
static

Definition at line 1923 of file poly.cc.

◆ divmod()

void divmod ( const poly & a,
const poly & b,
poly & q,
poly & r,
bool only_divides )
static

Polynomial division

Description

This routine determines which division routine to use for dividing two polynomials. The logic is as follows:

  • If b consists of only one term, call divmod_one_term;
  • Otherwise, if both are univariate and dense, call divmod_univar;
  • Otherwise, call divmod_heap.

Definition at line 1852 of file poly.cc.

References divmod_heap(), divmod_univar(), and is_dense_univariate().

◆ divides()

bool divides ( const poly & a,
const poly & b )
static

Definition at line 1898 of file poly.cc.

◆ mul_one_term()

void mul_one_term ( const poly & a,
const poly & b,
poly & c )
static

Definition at line 751 of file poly.cc.

◆ mul_univar()

void mul_univar ( const poly & a,
const poly & b,
poly & c,
int var )
static

Definition at line 825 of file poly.cc.

◆ mul_heap()

void mul_heap ( const poly & a,
const poly & b,
poly & c )
static

Multiplication of polynomials with a heap

Description

Multiplies two multivariate polynomials. The next element of the product is efficiently determined by using a heap. If the product of the maximum power in all variables is small, a hash table is used to add equal terms for extra speed.

A heap element h is formatted as follows:

  • h[0] = index in a
  • h[1] = index in b
  • h[2] = hash code (-1 if no hash is used)
  • h[3] = length of coefficient with sign
  • h[4...4+AN.poly_num_vars-1] = powers
  • h[4+AN.poly_num_vars...4+h[3]-1] = coefficient

Definition at line 957 of file poly.cc.

References RaisPowCached().

Referenced by mul().

◆ divmod_one_term()

void divmod_one_term ( const poly & a,
const poly & b,
poly & q,
poly & r,
bool only_divides )
static

Definition at line 1241 of file poly.cc.

◆ divmod_univar()

void divmod_univar ( const poly & a,
const poly & b,
poly & q,
poly & r,
int var,
bool only_divides )
static

Division of dense univariate polynomials.

Description

Divides two dense univariate polynomials. For each power, the method collects all terms that result in that power.

Relevant formula [Q=A/B, P=SUM(p_i*x^i), n=deg(A), m=deg(B)]: q_k = [ a_{m+k} - SUM(i=k+1...n-m, b_{m+k-i}*q_i) ] / b_m

Definition at line 1372 of file poly.cc.

References GetModInverses(), and RaisPowCached().

Referenced by divmod().

◆ divmod_heap()

void divmod_heap ( const poly & a,
const poly & b,
poly & q,
poly & r,
bool only_divides,
bool check_div,
bool & div_fail )
static

Division of polynomials with a heap

Description

Divides two multivariate polynomials. The next element of the quotient/remainder is efficiently determined by using a heap. If the product of the maximum power in all variables is small, a hash table is used to add equal terms for extra speed.

If the input flag check_div is set then if the result of any coefficient division results in a non-zero remainder (indicating that division has failed over the integers) the output flag div_fail will be set and the division will be terminated early (q, r will be incorrect). If check_div is not set then non-zero remainders from coefficient division will be written into r.

A heap element h is formatted as follows:

  • h[0] = index in a
  • h[1] = index in b
  • h[2] = -1 (no hash is used)
  • h[3] = length of coefficient with sign
  • h[4...4+AN.poly_num_vars-1] = powers
  • h[4+AN.poly_num_vars...4+h[3]-1] = coefficient

Note: the hashing trick as in multiplication cannot be used easily, since there is no tight upperbound on the exponents in the answer.

For details, see M. Monagan, "Polynomial Division using Dynamic Array, Heaps, and Packed Exponent Vectors"

Definition at line 1575 of file poly.cc.

References GetModInverses(), and RaisPowCached().

Referenced by divmod().

◆ push_heap()

void push_heap ( PHEAD WORD ** heap,
int n )
static

Definition at line 735 of file poly.cc.

◆ pop_heap()

void pop_heap ( PHEAD WORD ** heap,
int n )
static

Definition at line 703 of file poly.cc.

Field Documentation

◆ terms

WORD* terms

Definition at line 58 of file poly.h.

◆ size_of_terms

LONG size_of_terms

Definition at line 59 of file poly.h.

◆ modp

WORD modp

Definition at line 60 of file poly.h.

◆ modn

WORD modn

Definition at line 60 of file poly.h.


The documentation for this class was generated from the following files: