/ 
Math-Polynomial-1.008
River stage one • 5 direct dependents • 5 total dependents
/ Math::Polynomial

NAME

Math::Polynomial - Perl class for polynomials in one variable

VERSION

This documentation refers to version 1.008 of Math::Polynomial.

SYNOPSIS

use Math::Polynomial 1.000;

$p = Math::Polynomial->new(0, -2, 0, 1);    # x^3 - 2 x

print "p = $p\n";                           # p = (x^3 + -2 x)

$p->string_config({ fold_sign => 1 });
print "p = $p\n";                           # p = (x^3 - 2 x)

$q = $p->new(0, 3, 0, -4, 0, 1);            # x^5 - 4 x^3 + 3 x

$r = $p ** 2 - $p * $q;                     # arithmetic expression
$bool = $p == $q;                           # boolean expression

($s, $t) = $r->divmod($q);                  # q * s + t = r

$u = $r->gcd($q);                        # greatest common divisor,
                                         # here: u = 3 x
$v = $u->monize;                         # v = x

$y = $p->evaluate(0.5);                     # y = p(0.5) = -0.875
$d = $q->degree;                            # d = degree(q) = 5

$w = $p->interpolate([0..2], [-1, 0, 3]);   # w(0) = -1, w(1) = 0,
                                            # w(2) = 3

use Math::Complex;
$p = Math::Polynomial->new(i, 1+i);         # p(x) = (1+i)*x + i

DESCRIPTION

Math::Polynomial objects represent polynomials in one variable, i.e. expressions built with finitely many additions, subtractions and multiplications of the variable and some constants. A standard way of writing down a polynomial in one variable is as a sum of products of some constant and a power of x, ordered by powers of x. The constants in those terms are called coefficients.

The polynomial p(x) = 0 is called the zero polynomial. For polynomials other than the zero polynomial, the exponent of the highest power of x with a nonzero coefficient is called the degree of the polynomial.

New Math::Polynomial objects can be created using a variety of constructors, or as results of expressions composed from existing objects. Math::Polynomial objects are immutable with respect to mathematical properties; all operations on polynomials create and return new objects rather than modifying anything.

The module works with various types of coefficients, like ordinary floating point numbers, complex numbers, arbitrary precision rationals, matrices, elements of finite fields, and lots of others. All that is required is that the coefficients are either Perl numbers or objects with suitably overloaded arithmetic operators. Operations on polynomials are carried out by reducing them to basic operations in the domain of their coefficients.

Math::Polynomial objects are implicitly bound to their coefficient space, which will be inherited when new polynomials are derived from existing ones, or determined from actual coefficients when polynomials are created from scratch. It is the responsibility of the application not to mix coefficients that cannot be added to or multiplied by each other.

Note that ordinary Perl numbers used as coefficients have the disadvantage that rounding errors may lead to undesired effects, such as unexpectedly non-zero division remainders or failing equality checks.

CLASS VARIABLES

$VERSION

$VERSION contains the current version number of the module. Its most typical use is the statement:

use Math::Polynomial 1.000;

This will make sure the module version used is at least 1.000, which is recommended because previous versions had a different API.

$max_degree

$max_degree limits the arguments for the pow and shift_up operators and the monomial constructor, see "pow". Its default value is ten thousand. It can be undefined to disable any size checks.

CLASS METHODS

Constructors

new($coeff0, $coeff1, $coeff2, ...)

Math::Polynomial->new(@coeff) creates a new polynomial with the given coefficients for x to the power of zero, one, two, etc. For example, Math::Polynomial->new(7, 1) creates an object representing p(x) = 7+x.

Note that coefficients are specified in ascending order of powers of x. The degree of the polynomial will be at most n-1 if n coefficients are given, less if one or more of the highest-order coefficients are zero.

Specifying at least one coefficient (which may be zero) ensures that the created polynomials use the desired coefficient space. Without any parameters, new creates a zero polynomial on Perl numeric values.

monomial($degree)
monomial($degree, $coeff)

Math::Polynomial->monomial($degree, $coeff) creates a polynomial with $coeff as the coefficient for x to the power of $degree, and all other coefficients zero. The degree must be a non-negative integer number. If $coeff is omitted, it defaults to the Perl scalar 1.

To prevent accidential excessive memory consumption, $degree must be at most $Math::Polynomial::max_degree.

interpolate([$x1, $x2, ...], [$y1, $y2, ...])

Math::Polynomial->interpolate(\@x_values, \@y_values) creates a Newton/Lagrange interpolation polynomial passing through support points with the given x- and y-coordinates. The x-values must be mutually distinct. The number of y-values must be equal to the number of x-values. For n support points this takes O(n**2) additions, subtractions, multiplications, divisions and comparisons each in the coefficient space. The result will be a polynomial of degree n-1 at most.

Note that with increasing numbers of support points, interpolation tends to get inaccurate if carried out with limited numerical precision. Furthermore, high-degree interpolation polynomials can oscillate wildly in the neighbourhood of the support points, let alone elswhere, unless the support point x-values are carefully chosen. This is due to the nature of these functions and not a fault of the module. A script demonstrating this phenomenon can be found in the Math-Polynomial examples directory.

from_roots($x1, $x2, ...)

Math::Polynomial->from_roots(@x_values) creates the monic polynomial with the given set of roots, i.e. for x-values x1, x2, ..., xn the product (x-x1)*(x-x2)*...*(x-xn). This is a Polynomial of degree n if n roots are given. The x-values can be given in any order and do not need to be distinct. For n roots this takes O(n*n) multiplications and subtractions in the coefficient space.

Other class methods

Some properties governing default behaviour can be accessed through the class method string_config. See "String Representation".

OBJECT METHODS

Constructors

Each class-level constructor can be used as an object method, too, i.e. be invoked from an object rather than a class name. This way, coefficient space properties are passed on from the invocant object to the new object, saving some initial coefficient analysis. Other properties like per-object stringification settings (explained below) are inherited likewise.

new($coeff0, $coeff1, $coeff2, ...)

If $p refers to a Math::Polynomial object, the object method $p->new(@coeff) creates and returns a new polynomial sharing inheritable properties with $p, but with its own list of coefficients as specified in @coeff.

monomial($degree)
monomial($degree, $coeff)

$p->monomial($degree, $coeff) creates a monomial like Math::Polynomial->monomial($degree, $coeff), but sharing inheritable properties with $p. If $coeff is omitted it defaults to the multiplicative unit element of the coefficient space of $p.

To prevent accidential excessive memory consumption, $degree must be at most $Math::Polynomial::max_degree.

interpolate([$x1, $x2, ...], [$y1, $y2, ...])

$p->interpolate(\@x_values, \@y_values) is the object method usage of the Newton/Lagrange interpolation polynomial constructor (see above). It creates a polynomial passing through support points with the given x- and y-coordinates. The x-values must be mutually distinct. The number of y-values must be equal to the number of x-values. All values must belong to the coefficient space of $p.

from_roots($x1, $x2, ...)

If $p refers to a Math::Polynomial object, the object method $p->from_roots(@x_values) creates the monic polynomial with the given set of roots, i.e. for x-values x1, x2, ..., xn the product (x-x1)*(x-x2)*...*(x-xn), sharing inheritable properties with $p. For n roots this takes O(n*n) multiplications and subtractions in the coefficient space.

clone

$p->clone returns a new object equal to $p. This method will rarely be needed as Math::Polynomial objects are immutable except for their stringification configuration (cf. "string_config").

Property Accessors

coefficients

$p->coefficients returns the coefficients of $p in ascending order of exponents, including zeroes, up to the highest-order non-zero coefficient. The result will be a list of n+1 coefficients for polynomials of degree n, or a single zero coefficient for zero polynomials.

coeff

$p->coeff returns the coefficients of $p much like $p->coefficients, but for zero polynomials the result will be an empty list.

(Mnemonic for coeff versus coefficients: Shorter name, shorter list.)

coeff($exp)

$p->coeff($exp) returns the coefficient of degree $exp of $p. If $exp is less than zero or larger than the degree of $p, the zero element of the coefficient space is returned.

coeff_zero

$p->coeff_zero returns the zero element of the coefficient space of $p, i.e. the neutral element with respect to addition.

coeff_one

$p->coeff_one returns the multiplicative unit element of the coefficient space of $p, i.e. the neutral element with respect to multiplication.

degree

$p->degree returns -1 if $p is a zero polynomial, otherwise the degree of $p.

proper_degree

$p->proper_degree returns undef if $p is a zero polynomial, otherwise the degree of $p. This can be useful in order to catch incorrect numerical uses of degrees where zero polynomials might be involved.

is_monic

$p->is_monic returns a boolean value which is true if $p is monic, which means it is not the zero polynomial and its highest-degree coefficient is equal to one. Cf. "monize".

Evaluation

evaluate

$p->evaluate($x) computes the value of the polynomial function given by $p at the position $x. For polynomials of degree n, this takes n multiplications and n additions in the coefficient space.

Comparison Operators

All comparison operators return boolean results.

Note that there are no order-checking comparisons (<, <=, >, <=>, ...) as neither polynomial nor coefficient spaces in general need to be ordered spaces.

!
is_zero

$p->is_zero or short !$p or not $p checks whether $p is a zero polynomial.

is_nonzero

$p->is_nonzero checks whether $p is not a zero polynomial. This method may be implicitly called if an object is used in boolean context such as the condition of a while loop or in an expression with boolean operators such as && or ||.

==
is_equal

$p->is_equal($q) or short $p == $q checks whether $p is equivalent to $q. The result is true if both polynomials have the same degree and the same coefficients. For polynomials of equal degree n, this takes at most n+1 equality checks in the coefficient space.

Note that p == q implies that p(x) == q(x) for every x, but the converse implication is not true for some coefficient spaces.

!=
is_unequal

$p->is_unequal($q) or short $p != $q checks whether $p is not equivalent to $q. The result is true if the polynomials have different degree or at least one pair of coefficients of same degree is different. For polynomials of equal degree n, this takes at most n+1 equality checks in the coefficient space.

Arithmetic Operators

unary -
neg

$p->neg or short -$p calculates the negative of a polynomial. For a polynomial of degree n, this takes n+1 negations in the coefficient space.

+
add

$p->add($q) or short $p + $q calculates the sum of two polynomials. For polynomials of degree m and n, this takes 1+min(m, n) additions in the coefficient space.

-
sub_

$p->sub_($q) or short $p - $q calculates the difference of two polynomials. For polynomials of degree m and n, this takes 1+min(m, n) subtractions in the coefficient space, plus n-m negations if n is greater than m.

The trailing underscore in the method name may look a bit odd but will prevent primitive syntax-aware tools from stumbling over "misplaced" sub keywords.

*
mul

$p->mul($q) or short $p * $q calculates the product of two polynomials. For polynomials of degree m and n, this takes (m+1)*(n+1) multiplications and m*n additions in the coefficient space.

divmod

($q, $r) = $p1->divmod($p2) divides a polynomial by another polynomial and returns the polynomial part of the quotient, and the remainder. The second polynomial must not be a zero polynomial. The remainder is a polynomial of lesser degree than the second polynomial and satisfies the equation $p1 == $p2*$q + $r. For polynomials of degree m and n, m>=n, this takes m+1-n divisions, (m+1-n)*n multiplications and (m+1-n)*n subtractions in the coefficient space.

/
div

$p->div($q) or short $p / $q calculates the polynomial part of the quotient of two polynomials. This takes the same operations in the coefficient space as divmod.

%
mod

$p->mod($q) or short $p % $q calculates the remainder from dividing one polynomial by another. This takes the same operations in the coefficient space as divmod.

mmod

$p->mmod($q) (modified mod) calculates the remainder from dividing one polynomial by another, multiplied by some constant. The constant is a**d where a is the highest coefficient of q and d = degree(p) - degree(q) + 1, if degree(p) > degree(q), otherwise d = 0. This operation is suitable to substitute mod in the Euclidean algorithm and can be calculated without division in the coefficient space. For polynomials of degree m and n, m>=n, this takes (m+1-n)*(m+3*n)/2 multiplications and (m+1-n)*n subtractions in the coefficient space.

**
pow

$p->pow($n) or short $p ** $n calculates a power of a polynomial. The exponent $n must be a non-negative integer. To prevent accidential excessive time and memory consumption, the degree of the result must be at most $Math::Polynomial::max_degree. The degree limit can be configured, see "$max_degree". Calculating the n-th power of a polynomial of degree m takes O(m*m*n*n) multiplications and additions in the coefficient space.

pow_mod

$p1->pow_mod($n, $p2) is equivalent to ($p1 ** $n) % $p2, except that the modulo operation is repeatedly applied to intermediate results in order to keep their degrees small. The exponent $n must be a non-negative integer.

exp_mod

$p->exp_mod($n) is equivalent to (x ** $n) % $p. The exponent $n must be a non-negative integer.

add_const
sub_const
mul_const
div_const

The arithmetic operations add_const, sub_const, mul_const and div_const can be used to efficiently add a constant to or subtract a constant from a polynomial, or multiply or divide a polynomial by a constant, respectively.

Overloaded arithmetic operators (+, -, *, ...) work with constants in place of polynomial operands, too, by converting non-polynomial arguments into constant polynomials first. However, this usage is both less efficient and less obvious, and therefore not recommended.

Note that there is no use for a mod_const method, as polynomial division by a constant always yields a zero remainder.

<<
shift_up

$p->shift_up($n) or short $p << $n calculates the product of a polynomial and a power of x. The exponent $n must be a non-negative integer. To prevent accidential excessive memory consumption, the degree of the result must be at most $Math::Polynomial::max_degree.

>>
shift_down

$p->shift_down($n) or short $p >> $n divides a polynomial by a power of x and returns the polynomial part of the result, i.e. discarding negative powers of x. The exponent $n must be a non-negative integer.

Shifting up or down is more efficient than multiplication or division as it does not take any operations in the coefficient space.

slice

$p->slice($m, $n) is equivalent to:

$xm = $p->make_monomial($m);
$xn = $p->make_monomial($n);
($p / $xm) % $xn

I.e., it returns a polynomial built from a slice of the coefficients of the original polynomial starting with degree $m, and at most $n coefficients. However, it is more efficient than division and modulo as it does not perform any operations in the coefficient space. The indexes $m and $n must be non-negative integers.

mul_root

$p->mul_root($c) calculates the product of a polynomial p and the linear term (x - c). The result is a polynomial that evaluates to zero at the given root c. For polynomials of degree n, this takes n+1 multiplications and n+1 subtractions.

div_root

$p->div_root($c) divides a polynomial p by a linear factor (x - c), discarding any remainder. For polynomials of degree n, this takes n multiplications and n additions in the coefficient space.

This method originally had an optional second argument $check, enabling a check to make sure the value of $c is actually a root of $p, i.e. the discarded remainder is zero. This usage is deprecated, however, in favour of using divmod_root and explicitly checking the remainder.

divmod_root

($q, $r) = $p->divmod_root($c) divides a polynomial p by a linear factor (x - c) and returns the result and remainder. The remainder will be a zero polynomial if c is a root of p, otherwise a constant polynomial. For polynomials of degree n, this takes n multiplications and n additions.

This method must be called in array context.

Note that there is no need for a mod_root method, as that would be equivalent to evaluate.

monize

$p->monize converts an arbitrary non-zero polynomial to a monic polynomial via division by its highest-order coefficient. The result will be monic, i.e. with a highest-order coefficient of one, if the invocant was not the zero polynomial, otherwise the zero polynomial. Monization of a non-zero polynomial of degree n takes n divisions in the coefficient space.

Assignment Operators

=
+=
-=
*=
/=
%=
**=
<<=
>>=
&&=
||=

As Math::Polynomial objects are immutable with respect to their arithmetic properties, assignment operators like =, +=, -=, *= etc. will always replace the object that is being assigned to, rather than mutate it. Thus polynomial objects can safely be "modified" using assignment operators, without side effects on other variables referencing the same objects.

Note that the short-circuit behaviour of && and ||, which return the last expression evaluated, implies that &&= and ||= conditionally replace a polynomial by a given expression (another polynomial, say), not just a boolean value.

Miscellaneous Operators

nest

$p1->nest($p2) calculates the nested polynomial p1(p2(x)) from two polynomials p1(x) and p2(x). For polynomials of degree m and n this takes O(m*m*n*n) multiplications and additions in the coefficient space. The result will be a polynomial of degree m*n if neither of the polynomials is a zero polynomial, otherwise a constant or zero polynomial.

gcd

$p1->gcd($p2, $mod) calculates a greatest common divisor of two polynomials, using the Euclidean algorithm and the modulo operator as specified by name. The $mod parameter is optional and defaults to 'mod'. With polynomials of degree m and n, m>=n, and the default modulo operator mod, this takes at most n polynomial divisions of decreasing degrees or O(m+n) divisions and O(m*n) multiplications and subtractions in the coefficient space. With the mmod operator, this takes O(m*n) multiplications and subtractions in the coefficient space.

mmod can have advantages over mod in situations where division in the coefficient space is much more expensive than multiplication.

xgcd

($d, $d1, $d2, $m1, $m2) = $p1->xgcd($p2) calculates a greatest common divisor d and four polynomials d1, d2, m1, m2, such that d = p1*d1 + p2*d2, 0 = p1*m1 + p2*m2, degree(m1*d) = degree(p2), degree(m2*d) = degree(p1), using the extended Euclidean algorithm. With polynomials of degree m and n, m>=n, this takes at most n polynomial divisions and 2*n polynomial multiplications and subtractions of decreasing degrees, or, in the coefficient space: O(m+n) divisions and O(m*n) multiplications and subtractions.

inv_mod

$q = $p1->inv_mod($p2) calculates the multiplicative pseudo-inverse q of a polynomial p1 modulo another polynomial p2. p2 must not be a zero polynomial, and p1 must not be equivalent to zero modulo p2.

If p1 and p2 are relatively prime, the result will be a true modular inverse, i.e. q * p1 % p2 will be the same as p2 ** 0. In any case, q will be chosen such that q * p1 % p2 is the monic greatest common divisor of p1 and p2.

inv_mod takes the same operations in the coefficient space as xgcd plus monize.

Calculus Operators

Calculus operators as presented here are most meaningful on spaces such rational or real or complex numbers. Starting with version 1.005 of Math::Polynomial, calculus operators are no longer restricted to coefficient spaces compatible with Perl integers. This means these operators do not mix coefficients and Perl integers any more, but does not imply they are equally useful with every kind of coefficients.

differentiate

$p->differentiate calculates the first derivative of a polynomial. For a polynomial of degree n, this takes n multiplications and n additions in the coefficient space.

integrate

$p->integrate calculates an antiderivative of a polynomial. The coefficient of degree zero of the result will be zero. $p->integrate($c) does the same but adds the constant $c. For a polynomial of degree n, both forms of integration take n+1 comparisons with zero, at most n+1 divisions, and n+1 additions in the coefficient space. Note that in coefficient spaces with zero divisors this operation might fail due to division by zero.

definite_integral

$p->definite_integral($x1, $x2) calculates the value of the definite integral from $x1 to $x2 over the polynomial function given by $p. For real numbers x1 < x2, this can be interpreted as the signed area bound by the lines x=x1, y=0, x=x2 and the graph of p(x), where parts below the x-axis are regarded as negative.

For a polynomial of degree n, this takes the same operations as integrate plus twice evaluate plus a subtraction in the coefficient space. If you need to calculate more than one definite integral over the same polynomial function, it is more efficient to store an antiderivative once (see "integrate") and evaluate it at the different interval limits. The statement...

$a = $p->definite_integral($x1, $x2);

... is essentially equivalent to:

$p_int = $p->integrate;
$a     = $p_int->evaluate($x2) - $p_int->evaluate($x1);

String Representation

""
as_string

In string context, Math::Polynomial objects will automatically be converted to a character string, which is the same as the result of the as_string() method when called without parameter.

An optional configuration hashref controls many layout aspects of the string representation. In the absence of an explicit configuration, a per-object default configuration is used, and in the absence of that, a per-class default configuration (see "string_config").

Each individual configuration setting has a default value as defined in the next section.

string_config

$p->string_config($hashref) sets the per-object default stringification configuration to $hashref. $hashref may be undef to remove a previously set configuration.

$p->string_config returns the per-object default stringification configuration as a reference to a hash, if present, otherwise undef.

Math::Polynomial->string_config($hashref) sets the per-class default stringification configuration to $hashref. Math::Polynomial->string_config returns that configuration. It should always refer to an existing hash, which may be empty.

A per-object configuration will be propagated to any new objects created from an object. Thus it is easy to use consistent settings without having to touch global parameters.

Stringification Configuration Options

ascending

True value: order coefficients from lowest to highest degree; False value (default): from highest to lowest.

with_variable

True value (default): display coefficients together with powers of the variable; false value: display coefficients alone. False implies that fold_zero, times, power and variable will have no effect.

fold_sign

True value: contract the addition symbol and the sign of a negative value to a single subtraction symbol; false value (default): do not carry out this kind of replacement. True is only allowed if the coefficient space defines a native "less than" operator or the configuration parameter sign_of_coeff (see below) is set.

fold_zero

True value (default): suppress terms with coefficients equal to zero; false value: do not suppress any terms. Zero polynomials are represented with a zero constant term in any case.

fold_one

True value (default): suppress coefficients equal to one when multiplied by a variable power; false value: do not suppress factors of one. Note that coefficients very close but not quite equal to one might be stringified to one without being caught by this rule.

fold_exp_zero

True value (default): suppress the variable and the zero exponent in the constant term; false value: display even the constant term with a variable power.

fold_exp_one

True value (default): suppress the exponent in the term of the variable to the power of one; false value: display even the linear term with an exponent.

convert_coeff

Code reference specifying a function that takes a coefficient value and returns a string representing that value. Default is ordinary stringification.

sign_of_coeff

If defined, code reference specifying a function that takes a coefficient value and returns a negative, zero, or positive integer if the argument is negative, zero, or positive, respectively. Default is undef.

This parameter can be used to let stringification distinguish "negative" from other values where the coefficient space is not an ordered space, i.e. lacking operators like < (less than).

plus

Addition symbol to put between terms. Default is a plus character surrounded by blanks.

minus

Subtraction symbol replacing a plus symbol and a negative sign, if applicable (see fold_sign). Default is a minus character surrounded by blanks.

leading_plus

Sign symbol to put before the first term unless fold_sign is true and the coefficient is negative. Default is an empty string.

leading_minus

Sign symbol replacing a negative sign at the first term, if fold_sign is true. Default is a minus followed by a blank.

times

Multiplication symbol to put between the coefficient and the variable in each term. Default is a blank.

power

Exponentiation symbol to put between the variable and the exponent in each term. Default is a caret (^).

variable

Symbol representing the variable. Default is a lower case x.

prefix

Prefix to prepend to the entire polynomial. Default is a left parenthesis.

suffix

Suffix to append to the entire polynomial. Default is a right parenthesis.

wrap

Wrapping or post-processing function: Coderef called with the polynomial object and its raw stringification (without prefix and suffix) to return a final stringification (still without prefix and suffix). Default is a function returning its second argument.

Other Conversions

Tree conversions can be used to generate data structures such as operand trees from polynomials. There is a distinction between two types of construction -- a power sum scheme essentially follows the canonical way of describing polynomials as a sum of multiples of powers of the variable, while a Horner scheme avoids repeated exponentiation and uses just alternating additions of coefficients and multiplications by the variable, describing a polynomial in a way that can be more efficiently evaluated.

as_horner_tree

$p->as_horner_tree($config) can generate nested data structures from a polynomial $p, employing a Horner scheme. A Horner scheme evaluates a polynomial using alternating additions and multiplications. For convenience, consecutive multiplications by the variable are condensed to a single multiplication by a power of the variable. In order to avoid exponentiation altogether, the configuration option expand_power can be set to a true value.

The $config hashref is a mandatory parameter. It defines what functions are to be called at each step of the tree construction. All configuration components are described in the next section.

as_power_sum_tree

$p->as_power_sum_tree($config) can generate nested data structures from a polynomial $p, where the polynomial is built as a sum of multiples of powers of a variable.

The $config hashref is a mandatory parameter. It defines what functions are to be called at each step of the tree construction. All configuration components are described in the next section.

Tree Conversion Configuration Options

fold_sign

Boolean, default false. Defines whether negation and difference operations should be employed in order to avoid negative constants.

A true value is only allowed if the coefficient space is an ordered space and defines a < comparison operator for coefficients, or the configuration parameter sign_of_coeff (see below) is set.

expand_power

Boolean, default false. Defines whether the power operation should be avoided in favour of consecutive multiplications. Presumably more useful in horner trees than power sum trees.

variable

Node to insert for the variable. If it is a coderef, the given subroutine will be called every time a variable is inserted into the tree and its return value will be used, otherwise the (same) value will be used directly each time.

constant

Coderef, node factory for constants. Called with a coefficient as single parameter. The result is used as a node representing that coefficient as a constant.

negation

Coderef, node negation. Called with a node as single parameter. The result is used as negative of the original node. Only used if fold_sign is true.

sum

Coderef, node summation. Called with two node parameters, ordered in decreasing complexity. The result is propagated as sum of the original nodes.

difference

Coderef, node subtraction. Called with two node parameters, ordered in decreasing complexity. The result is propagated as difference of the original nodes. Only used if fold_sign is true.

product

Coderef, node multiplication. Called with two node parameters, ordered like this: If one node is the variable or a power of the variable, it will be the second parameter, while a constant or a complex tree will be the first parameter. The result is propagated as product of the original nodes.

power

Coderef, exponentiation. Called with a node representing the variable and an integer number greater than one. Used for both power sum trees (where degree is at least two) and Horner trees (where some terms other than the constant term are zero). Note that the second parameter is not a node but a plain number, in order to support data structures allowing only integer exponentiation. Not used if expand_power is set to a true value (in either kind of tree).

group

Coderef, grouping. Only used with Horner trees, optional. Called with a node representing a subexpression that would have to be in parentheses to maintain operator precedence.

sign_of_coeff

If defined, code reference specifying a function that takes a coefficient value and returns a negative, zero, or positive integer if the argument is negative, zero, or positive, respectively. Default is undef.

This parameter can be used to let tree construction distinguish "negative" from other values where the coefficient space is not an ordered space, i.e. lacking operators like < (less than).

EXAMPLES

use Math::Polynomial 1.000;

# simple constructors:
$p  = Math::Polynomial->new(0, -3, 0, 2);    # (2*x**3 - 3*x)
$zp = Math::Polynomial->new(0);              # the zero polynomial
$q  = Math::Polynomial->monomial(3, 2);      # (2*x**3)
$q  = Math::Polynomial->from_roots(5, 6, 7); # (x-5)*(x-6)*(x-7)

# Lagrange interpolation:
$q = Math::Polynomial->interpolate([0..3], [0, -1, 10, 45]);
                                             # (2*x**3 - 3*x)

# constructors used as object methods:
$q = $p->new(0, -3, 0, 2);                   # (2*x**3 - 3*x)
$q = $p->new;                                # the zero polynomial
$q = $p->monomial(3, 2);                     # (2*x**3)
$q = $p->monomial(3);                        # (x**3)
$q = $p->interpolate([0..3], [0, -1, 10, 45]); # (2*x**3 - 3*x)
$q = $p->from_roots(5, 6, 7);                # (x-5)*(x-6)*(x-7)
$q = $p->clone;                              # q == p

# properties
@coeff = $p->coefficients;                   #    (0, -3, 0, 2)
@coeff = $p->coeff;                          #    (0, -3, 0, 2)
$coeff = $p->coeff(0);                       #     0
$coeff = $p->coeff(1);                       #        -3
$coeff = $p->coeff(2);                       #            0
$coeff = $p->coeff(3);                       #               2
$coeff = $p->coeff(4);                       # 0
@coeff = $zp->coefficients;                  #    (0)
@coeff = $zp->coeff;                         #    ()
$const = $p->coeff_zero;                     # 0
$const = $p->coeff_one;                      # 1
$n = $p->degree;                             # 3
$n = $zp->degree;                            # -1
$n = $p->proper_degree;                      # 3
$n = $zp->proper_degree;                     # undef

# evaluation
$y = $p->evaluate(4);                        # p(4) == 116

# comparison
$bool = !$p;         $bool = $p->is_zero;    # zero polynomial?
if ($p) ...          if ($p->is_nonzero) ... # not zero polynomial?

$bool = $p == $q;    $bool = $p->is_equal($q);      # equality
$bool = $p != $q;    $bool = $p->is_unequal($q);    # inequality

$p = $q && $r;       $p = $q->is_zero? $q: $r;      # choice
$p = $q || $r;       $p = $q->is_zero? $r: $q;      # choice

# arithmetic
$q = -$p;            $q = $p->neg;           # q(x) == -p(x)
$q = $p1 + $p2;      $q = $p1->add($p2);     # q(x) == p1(x) + p2(x)
$q = $p1 - $p2;      $q = $p1->sub_($p2);    # q(x) == p1(x) - p2(x)
$q = $p1 * $p2;      $q = $p1->mul($p2);     # q(x) == p1(x) * p2(x)
$q = $p1 / $p2;      $q = $p1->div($p2);     # p1 == q * p2 + r,
                                             #   deg r < deg p2
$r = $p1 % $p2;      $r = $p1->mod($p2);     # p1 == q * p2 + r,
                                             #   deg r < deg p2
$q = $p + 3;         $q = $p->add_const(3);  # q(x) == p(x) + 3
$q = $p - 3;         $q = $p->sub_const(3);  # q(x) == p(x) - 3
$q = $p * 3;         $q = $p->mul_const(3);  # q(x) == p(x) * 3
$q = $p / 3;         $q = $p->div_const(3);  # q(x) == p(x) / 3

$q = $p ** 3;        $q = $p->pow(3);        # q(x) == p(x) ** 3
$q = $p << 3;        $q = $p->shift_up(3);   # q(x) == p(x) * x**3
$q = $p >> 3;        $q = $p->shift_down(3); # p == q * x**3 + r,
                                             #   deg r < 3

$r = $p->slice(0, 3);              # p ==  q * x**3 + r, deg r < 3
$r = $p->slice(2, 3);              # p == (q * x**3 + r) * x**2 + s,
                                   #   deg r < 3, deg s < 2

($q, $r) = $p1->divmod($p2);                 # p1 == q * p2 + r,
                                             #   deg r < deg p2

$q = $p->mul_root(7);                        # q = p * (x-7)

$q = $p->div_root(7);                        # p = q * (x-7) + c,
                                             #   c is some constant

($q, $r) = $p->divmod_root(7);               # p = q * (x-7) + r,
                                             #   deg r < 1

$r = $p1->mmod($p2);                         # c * p1 == q * p2 + r,
                                             #   deg r < deg p2,
                                             #   c is a constant

$q = $p1->nest($p2);                         # q(x) == p1(p2(x))

$bool = $p->is_monic;                        # whether p is monic

$q = $p->monize;                             # p(x) == q(x) * c,
                                             #   q is monic or zero

$r = $p1->pow_mod(3, $p2);                   # p1**3 == q * p2 + r,
                                             #   deg r < deg p2

$r = $p->exp_mod(3);                         # x**3 == q * p + r,
                                             #   deg r < deg p

# greatest common divisor
$d = $p1->gcd($p2);                          # p1 == q1 * d,
                                             # p2 == q2 * d,
                                             # deg d is maximal

$d = $p1->gcd($p2, 'mmod');                  # like gcd, but with
                                             # modified modulo op

# extended Euclidean algorithm
($d, $d1, $d2, $m1, $m2) = $p1->xgcd($p2);   # p1 == q1 * d,
                                             # p2 == q2 * d,
                                             # deg d is maximal,
                                             # d == p1*d1 + p2*d2,
                                             # 0 == p1*m1 + p2*m2

$r = $p1->inv_mod($p2);                      # p1 * r == p2 * q + d,
                                             #   deg r < deg p2,
                                             #   d is monic gcd of
                                             #   p1 and p2

# calculus
$q = $p->differentiate;             # q(x) == d/dx p(x)
$q = $p->integrate;                 # d/dx q(x) == p(x), q(0) == 0
$q = $p->integrate(10);             # d/dx q(x) == p(x), q(0) == 10
$a = $p->definite_integral(1, 2);   # Integral from 1 to 2, p(x) dx

# configurable string representation
$config = {
  ascending     => 0,
  with_variable => 1,
  fold_sign     => 0,
  fold_zero     => 1,
  fold_one      => 1,
  fold_exp_zero => 1,
  fold_exp_one  => 1,
  convert_coeff => sub { "$_[0]" },
  sign_of_coeff => undef,
  plus          => q{ + },
  minus         => q{ - },
  leading_plus  => q{},
  leading_minus => q{- },
  times         => q{ },
  power         => q{^},
  variable      => q{x},
  prefix        => q{(},
  suffix        => q{)},
  wrap          => sub { $_[1] },
};
$str = "$p";                                 # '(2 x^3 + -3 x)'
$str = $p->as_string();                      # '(2 x^3 + -3 x)'
$str = $p->as_string($config);               # '(2 x^3 + -3 x)'

$str = $p->as_string({fold_sign => 1});      # '(2 x^3 - 3 x)'

$p->string_config({fold_sign => 1});
$str = "$p";                                 # '(2 x^3 - 3 x)'
$str = $p->as_string;                        # '(2 x^3 - 3 x)'

$p->string_config(undef);
$str = "$p";                                 # '(2 x^3 + -3 x)'

Math::Polynomial->string_config({fold_sign => 1});
$str = "$p";                                 # '(2 x^3 - 3 x)'

$config = $p->string_config;                 # undef
$config = Math::Polynomial->string_config;   # {fold_sign => 1}

$config = {
  with_variable => 0,
  ascending     => 1,
  plus          => q{, },
};
$str = $p->as_string($config);               # '(0, -3, 0, 2)'

# other conversions

$config = {
  fold_sign  => 1,
  variable   => 'x',
  coeff      => sub { $[0] },
  negation   => sub { "- $_[0]" },
  sum        => sub { "$_[0] + $_[1]" },
  difference => sub { "$_[0] - $_[1]" },
  product    => sub { "$_[0]*$_[1]" },
  power      => sub { "$_[0]^$_[1]" },
  group      => sub { "($_[0])" },
};
$str = $p->as_horner_tree($config);          # '(2*x^2 - 3)*x'

$config = {
  variable => sub { ['x'] },
  coeff    => sub { ['c', @_] },
  sum      => sub { ['+', @_] },
  product  => sub { ['*', @_] },
  power    => sub { ['^', @_] },
  group    => sub { $_[0] },
};
$listref = $p->as_horner_tree($config);
# ['*', ['+', ['*', ['c', 2], ['^', ['x'], 2], ['c', -3]]], ['x']]

$listref = $p->as_power_sum_tree($config);
# ['+', ['*', ['c', 2], ['^', ['x'], 3]], ['*', ['c', -3], ['x']]]

# other customizations

$q = do {
  local Math::Polynomial::max_degree;        # override limitation
  $p->monomial(100_000)                      # x^100000
};

# examples of other coefficient spaces

use Math::Complex;
$c0 = Math::Complex->make(0, 3);
$c1 = Math::Complex->make(2, 1);
$p = Math::Polynomial->new($c0, $c1);        # p(x) == (2+i)*x + 3i
$p->string_config({
  convert_coeff => sub {
    my $coeff = "$_[0]";
    if ($coeff =~ /[+-]/) {
      $coeff = "($coeff)";
    }
    return $coeff;
  },
});
print "$p\n";                                # prints ((2+i) x + 3i)

use Math::BigRat;
$c0 = Math::BigRat->new('-1/2');
$c1 = Math::BigRat->new('0');
$c2 = Math::BigRat->new('3/2');
$p = Math::Polynomial->new($c0, $c1, $c2);  # p(x) == 3/2*x**2 - 1/2

use Math::ModInt qw(mod);
$c0 = mod(4, 5);
$c1 = mod(2, 5);
$p = Math::Polynomial->new($c0, $c1);      # p(x) == 2*x + 4 (mod 5)
$p->string_config({
  convert_coeff => sub { $_[0]->signed_residue },
  sign_of_coeff => sub { $_[0]->signed_residue },
});
print "$p\n";                              # prints (2 x - 1)

EXPORT

Math::Polynomial does not export anything into the namespace of the caller.

DIAGNOSTICS

Currently, Math::Polynomial does not thoroughly check coefficient values for sanity. Incompatible coefficients might trigger warnings or error messages from the coefficient class implementation, blaming Math::Polynomial to operate on incompatible operands. Unwisely chosen coefficient objects, lacking overrides for arithmetic operations, might even silently be used with their memory address acting as an integer value.

Some types of wrong usage, however, are diagnosed and will trigger one of the error messages listed below. All of them terminate program execution unless they are trapped in an eval block.

array context required

A method designed to return more than one value, like divmod or xgcd, was not called in array context. The results of these methods have to be assigned to a list of values rather than a single value.

array context required if called without argument

The coeff method was called without arguments, so as to return a list of coefficients, but not in array context. The list of coefficients should be assigned to an array. To retrieve a single coefficient, coeff should be called with a degree argument.

bad modulo operator

A modulo operator was passed to gcd and turned out to violate rules required by such an operator, like constraints on the degree of returned polynomials.

division by zero

The div_const method was called with a zero argument. Coefficient spaces are supposed to not allow division by zero, therefore Math::Polynomial tries to safeguard against it.

division by zero polynomial

Some kind of polynomial division, like div, mod, divmod, inv_mod or an expression with / or % was attempted with a zero polynomial acting as denominator or modulus. Division by a zero polynomial is not defined.

exponent too large

One of the methods pow, shift_up or monomial was called with arguments that would lead to a result with an excessively high degree. You can tweak the class variable $max_degree to change the actual limit or disable the check altogether. Calculations involving large polynomials can consume a lot of memory and CPU time. Exponent sanity checks help to avoid that from happening by accident.

missing parameter: %s

A method such as as_horner_tree or as_power_sum_tree, expecting a parameter hashref, was called without the mandatory parameter this message refers to.

no such method: %s

A modulo operator name was passed to gcd which is not actually the name of a method.

non-negative integer argument expected

One of the methods expecting non-negative integer arguments, like pow, pow_mod, shift_up, shift_down, slice or monomial, got something else instead.

non-zero remainder

The div_root method was called with a first argument that was not actually a root of the polynomial and a true value as second argument, forcing a check for divisibility.

Note that the two-argument usage of div_root and therefore this diagnostic message is deprecated.

usage: %s

A method designed to be called in a certain manner with certain types of arguments got not what it expected.

For example, interpolate takes two references of arrays of equal length.

Usage messages give an example of the expected calling syntax.

wrong operand type

An arithmetic expression used an operation not defined for polynomial objects, such as a power with a polynomial exponent.

x values not disjoint

The interpolate method was called with at least two equal x-values. Support points for this kind of interpolation must have distinct x-values.

EXTENSION GUIDELINES

Math::Polynomial can be extended in different ways. Subclasses may restrict coefficient spaces to facilitate certain application domains such as numerical analysis or channel coding or symbolic algebra.

Special polynomials (such as Legendre, Chebyshev, Gegenbauer, Jacobi, Hermite, Laguerre polynomials etc.) may be provided by modules adding not much more than a bunch of funnily named constructors to the base class.

Other modules may implement algorithms employing polynomials (such as approximation techniques) or analyzing them (such as root-finding techniques).

Yet another set of modules may provide alternative implementations optimized for special cases such as sparse polynomials, or taking benefit from specialized external math libraries.

Multivariate polynomials, finally, are now implemented in an independent package, Math-Polynomial-Multivariate.

This list is not necessarily complete.

DEPENDENCIES

This version of Math::Polynomial requires these other modules and libraries to run:

  • perl version 5.6.0 or higher

  • overload (usually bundled with perl)

  • Carp (usually bundled with perl)

Additional requirements to run the test suite are:

  • Test (usually bundled with perl)

  • Math::Complex (usually bundled with perl)

  • FindBin (usually bundled with perl)

Recommended modules for increased functionality are:

  • Math::Complex (usually bundled with perl)

  • Math::BigRat (usually bundled with perl)

BUGS AND LIMITATIONS

At the time of release, there were no known unresolved issues with this module. Bug reports and suggestions are welcome -- please submit them through the CPAN RT, http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-Polynomial.

SEE ALSO

Part of this distribution:

  • Example scripts distributed with Math::Polynomial.

    Scripts in the examples directory cover module version differences, interpolation, rational coefficients, pretty-printing, and more.

    Scripts in the test suite are less wordily documented, but should have at least one usage example for each of even the most exotic features.

  • Math::Polynomial::Generic - an experimental interface extension with some syntactical sugar coating Math::Polynomial.

Modules planned for release, in various states of completion:

  • Math::Polynomial::Sparse - an alternative implementation optimized for polynomials with lots of zero coefficients.

  • Math::Polynomial::Orthogonal - an extension providing constructors for many well-known kinds of orthogonal polynomials.

  • Math::Polynomial::Roots::DurandKerner - an extension implementing the Weierstrass-(Durand-Kerner) numerical root-finding algorithm.

  • Math::Polynomial::Parse - an extension providing methods to create polynomial objects from strings.

Other Modules:

  • Math::Polynomial::Multivariate - a module dealing with polynomials in more than one variable.

  • PDL - the Perl Data Language.

  • Math::GMPz - an interface to the GMP arbitrary precision integer math library.

  • Math::Pari - interface to the Pari math library.

General Information:

AUTHOR

Martin Becker, <becker-cpan-mp@cozap.com>

ACKNOWLEDGEMENTS

Math::Polynomial was inspired by a module of the same name written and maintained by Mats Kindahl, <mats@kindahl.net>, 1997-2007, who kindly passed it on to the author for maintenance and improvement.

Additional suggestions and bug reports came from Thorsten Dahlheimer and Kevin Ryde.

LICENSE AND COPYRIGHT

Copyright (c) 2007-2015 by Martin Becker. All rights reserved.

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.6.0 or, at your option, any later version of Perl 5 you may have available.

DISCLAIMER OF WARRANTY

This library is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.