FORM 4.3
|
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) | |
poly & | operator+= (const poly &) |
poly & | operator-= (const poly &) |
poly & | operator*= (const poly &) |
poly & | operator/= (const poly &) |
poly & | operator%= (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 |
poly & | operator= (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 poly & | normalize () |
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 |
poly | ( | PHEAD const UWORD * | a, |
WORD | na, | ||
WORD | modp = -1, | ||
WORD | modn = 1 ) |
|
inline |
int is_dense_univariate | ( | ) | const |
Dense univariate detection
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
A univariate polynomial is considered dense iff more than half of the coefficients a_0...a_deg are non-zero.
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
Polynomial multiplication
This routine determines which multiplication routine to use for multiplying two polynomials. The logic is as follows:
Definition at line 1191 of file poly.cc.
References is_dense_univariate(), and mul_heap().
Polynomial division
This routine determines which division routine to use for dividing two polynomials. The logic is as follows:
Definition at line 1852 of file poly.cc.
References divmod_heap(), divmod_univar(), and is_dense_univariate().
Multiplication of polynomials with a heap
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:
Definition at line 957 of file poly.cc.
References RaisPowCached().
Referenced by mul().
|
static |
Division of dense univariate polynomials.
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().
|
static |
Division of polynomials with a heap
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:
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().