Math::Polynomial  Perl class for polynomials in one variable
This documentation refers to version 1.013 of Math::Polynomial.
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
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 nonzero division remainders or failing equality checks.
$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
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.
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 n1 if n coefficients are given, less if one or more of the highestorder 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.
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 nonnegative 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
.
Math::Polynomial>interpolate(\@x_values, \@y_values)
creates a Newton/Lagrange interpolation polynomial passing through support points with the given x and ycoordinates. The xvalues must be mutually distinct. The number of yvalues must be equal to the number of xvalues. 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 n1 at most.
Note that with increasing numbers of support points, interpolation tends to get inaccurate if carried out with limited numerical precision. Furthermore, highdegree interpolation polynomials can oscillate wildly in the neighbourhood of the support points, let alone elswhere, unless the support point xvalues 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 MathPolynomial examples directory.
Math::Polynomial>from_roots(@x_values)
creates the monic polynomial with the given set of roots, i.e. for xvalues x1, x2, ..., xn the product (xx1)*(xx2)*...*(xxn). This is a Polynomial of degree n if n roots are given. The xvalues 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.
Some properties governing default behaviour can be accessed through the class method string_config. See "String Representation".
Each classlevel 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 perobject stringification settings (explained below) are inherited likewise.
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
.
$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
.
$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 ycoordinates. The xvalues must be mutually distinct. The number of yvalues must be equal to the number of xvalues. All values must belong to the coefficient space of $p
.
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 xvalues x1, x2, ..., xn the product (xx1)*(xx2)*...*(xxn), sharing inheritable properties with $p
. For n roots this takes O(n*n) multiplications and subtractions in the coefficient space.
$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").
$p>coefficients
returns the coefficients of $p
in ascending order of exponents, including zeroes, up to the highestorder nonzero coefficient. The result will be a list of n+1 coefficients for polynomials of degree n, or a single zero coefficient for zero polynomials.
$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.)
$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.
$p>coeff_zero
returns the zero element of the coefficient space of $p
, i.e. the neutral element with respect to addition.
$p>coeff_one
returns the multiplicative unit element of the coefficient space of $p
, i.e. the neutral element with respect to multiplication.
$p>degree
returns 1 if $p
is a zero polynomial, otherwise the degree of $p
.
$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.
$p>is_monic
returns a boolean value which is true if $p
is monic, which means it is not the zero polynomial and its highestdegree coefficient is equal to one. Cf. "monize".
$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.
All comparison operators return boolean results.
Note that there are no orderchecking comparisons (<, <=, >, <=>, ...) as neither polynomial nor coefficient spaces in general need to be ordered spaces.
!
$p>is_zero
or short !$p
or not $p
checks whether $p
is a zero polynomial.
$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 
.
==
$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.
!=
$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.

$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.
+
$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.

$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 nm negations if n is greater than m.
The trailing underscore in the method name may look a bit odd but will prevent primitive syntaxaware tools from stumbling over "misplaced" sub keywords.
*
$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.
($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+1n divisions, (m+1n)*n multiplications and (m+1n)*n subtractions in the coefficient space.
/
$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.
%
$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.
$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+1n)*(m+3*n)/2 multiplications and (m+1n)*n subtractions in the coefficient space.
**
$p>pow($n)
or short $p ** $n
calculates a power of a polynomial. The exponent $n
must be a nonnegative 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 nth power of a polynomial of degree m takes O(m*m*n*n) multiplications and additions in the coefficient space.
$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 nonnegative integer.
$p>exp_mod($n)
is equivalent to (x ** $n) % $p
. The exponent $n
must be a nonnegative integer.
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 nonpolynomial 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.
<<
$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 nonnegative integer. To prevent accidential excessive memory consumption, the degree of the result must be at most $Math::Polynomial::max_degree
.
>>
$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 nonnegative integer.
Shifting up or down is more efficient than multiplication or division as it does not take any operations in the coefficient space.
$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 nonnegative integers.
$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.
$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.
($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.
$p>monize
converts an arbitrary nonzero polynomial to a monic polynomial via division by its highestorder coefficient. The result will be monic, i.e. with a highestorder coefficient of one, if the invocant was not the zero polynomial, otherwise the zero polynomial. Monization of a nonzero polynomial of degree n takes n divisions in the coefficient space.
=
+=
=
*=
/=
%=
**=
<<=
>>=
&&=
=
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 shortcircuit 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.
$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.
$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.
($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.
$q = $p1>inv_mod($p2)
calculates the multiplicative pseudoinverse 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 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.
$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.
$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.
$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 xaxis 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);
""
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 perobject default configuration is used, and in the absence of that, a perclass default configuration (see "string_config").
Each individual configuration setting has a default value as defined in the next section.
$p>string_config($hashref)
sets the perobject default stringification configuration to $hashref
. $hashref
may be undef to remove a previously set configuration.
$p>string_config
returns the perobject default stringification configuration as a reference to a hash, if present, otherwise undef.
Math::Polynomial>string_config($hashref)
sets the perclass 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 perobject 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.
True value: order coefficients from lowest to highest degree; False value (default): from highest to lowest.
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.
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.
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.
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.
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.
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.
Code reference specifying a function that takes a coefficient value and returns a string representing that value. Default is ordinary stringification.
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).
Addition symbol to put between terms. Default is a plus character surrounded by blanks.
Subtraction symbol replacing a plus symbol and a negative sign, if applicable (see fold_sign). Default is a minus character surrounded by blanks.
Sign symbol to put before the first term unless fold_sign is true and the coefficient is negative. Default is an empty string.
Sign symbol replacing a negative sign at the first term, if fold_sign is true. Default is a minus followed by a blank.
Multiplication symbol to put between the coefficient and the variable in each term. Default is a blank.
Exponentiation symbol to put between the variable and the exponent in each term. Default is a caret (^
).
Symbol representing the variable. Default is a lower case x.
Prefix to prepend to the entire polynomial. Default is a left parenthesis.
Suffix to append to the entire polynomial. Default is a right parenthesis.
Wrapping or postprocessing 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.
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.
$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.
$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.
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.
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.
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.
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.
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.
Coderef, node summation. Called with two node parameters, ordered in decreasing complexity. The result is propagated as sum of the original nodes.
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.
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.
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).
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.
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).
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); # (x5)*(x6)*(x7) # 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); # (x5)*(x6)*(x7) $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 * (x7) $q = $p>div_root(7); # p = q * (x7) + c, # c is some constant ($q, $r) = $p>divmod_root(7); # p = q * (x7) + 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::BigNum; $c0 = Math::BigNum>new('1/2'); $c1 = Math::BigNum>new('0'); $c2 = Math::BigNum>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)
Math::Polynomial does not export anything into the namespace of the caller.
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.
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.
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.
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.
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.
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.
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.
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.
A modulo operator name was passed to gcd which is not actually the name of a method.
One of the methods expecting nonnegative integer arguments, like pow, pow_mod, shift_up, shift_down, slice or monomial, got something else instead.
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 twoargument usage of div_root and therefore this diagnostic message is deprecated.
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.
An arithmetic expression used an operation not defined for polynomial objects, such as a power with a polynomial exponent.
The interpolate method was called with at least two equal xvalues. Support points for this kind of interpolation must have distinct xvalues.
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 rootfinding 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, MathPolynomialMultivariate.
This list is not necessarily complete.
This version of Math::Polynomial requires these other modules and libraries to run:
Additional requirements to run the test suite are:
Recommended modules for increased functionality are:
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=MathPolynomial.
Our test suite checks for compatibility with several alien modules that might be useful as coefficient spaces. Issues with these modules are reported only in skip messages, but not as hard failures, as in the past usually the alien module was to blame.
Part of this distribution:
Scripts in the examples directory cover module version differences, interpolation, rational coefficients, prettyprinting, 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.
Modules planned for release, in various states of completion:
Other Modules:
General Information:
Martin Becker, <beckercpanmp@cozap.com>
Math::Polynomial was inspired by a module of the same name written and maintained by Mats Kindahl, <mats@kindahl.net>, 19972007, who kindly passed it on to the author for maintenance and improvement.
Additional suggestions and bug reports came from Thorsten Dahlheimer and Kevin Ryde.
Copyright (c) 20072017 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.
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.