In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, polynomial evaluation refers to computation of the value of a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
when its
indeterminates are substituted for some values. In other words, evaluating the polynomial
at
consists of computing
See also
For evaluating the
univariate polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
the most naive method would use
multiplications to compute
, use
multiplications to compute
and so on for a total of
multiplications and
additions.
Using better methods, such as
Horner's rule, this can be reduced to
multiplications and
additions. If some preprocessing is allowed, even more savings are possible.
Background
This problem arises frequently in practice. In
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, polynomials are used to compute function approximations using
Taylor polynomials. In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
and
hash tables, polynomials are used to compute
k-independent hashing.
In the former case, polynomials are evaluated using
floating-point arithmetic
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
, which is not exact. Thus different schemes for the evaluation will, in general, give slightly different answers. In the latter case, the polynomials are usually evaluated in a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, in which case the answers are always exact.
General methods
Horner's rule
Horner's method evaluates a polynomial using repeated bracketing:
This method reduces the number of multiplications and additions to just
Horner's method is so common that a computer instruction "
multiply–accumulate operation
In computing, especially digital signal processing, the multiply–accumulate (MAC) or multiply-add (MAD) operation is a common step that computes the product of two numbers and adds that product to an accumulator. The hardware unit that perfor ...
" has been added to many computer processors, which allow doing the addition and multiplication operations in one combined step.
Multivariate
If the polynomial is multivariate, Horner's rule can be applied recursively over some ordering of the variables.
E.g.
:
can be written as
:
An efficient version of this approach was described by Carnicer and Gasca.
Evaluation with preprocessing
Arbitrary polynomials can be evaluated with fewer
operations than Horner's rule requires if we first "preprocess"
the coefficients
.
An example was first given by Motzkin who noted that
:
can be written as
:
where the values
are computed in advance based on
.
Motzkin's method uses just 3 multiplications compared to Horner's 4.
The values for each
can be easily computed by expanding
and equating the coefficients:
:
Example
To compute the
Taylor expansion ,
we can upscale by a factor 24, apply the above steps, and scale back down.
That gives us the three multiplication computation
:
Improving over the equivalent Horner form (that is
) by 1 multiplication.
Multipoint evaluation
Evaluate of a
-degree polynomial
in multiple points
can be done with
multiplications by using
Horner's method times. Using above preprocessing approach, this can be reduced that by a factor of two, that is, to
multiplications.
However, it is possible to do better.
It is possible to reduce the time requirement to just
.
The idea is to define two polynomials that are zero in respectively the first and second half of the points:
and
.
We then compute
and
using
Polynomial remainder theorem, which can be done in
time using
Fast Fourier Transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in ...
.
Since
and
by construction, we have
:
This gives us a
Divide-and-conquer algorithm with
, which implies
.
In the case where the points in which we wish to evaluate the polynomials have some structure, simpler methods exists.
For example, Knuth section 4.6.4
gives a method for tabulating polynomial values of the type
:
Dynamic evaluation
In the case where
are not known in advance,
Kedlaya and Umans gave a data structure for evaluating polynomials over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
of size
in time
per evaluation after some initial preprocessing.
This was shown by
Larsen to be essentially optimal.
The idea is to transform
of degree
into a
multivariate polynomial , such that
and the individual degrees of
is at most
.
Since this is over
, the largest value
can take (over
) is
.
Using the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
, it suffices to evaluate
modulo different primes
with a product at least
.
Each prime can be taken to be roughly
, and the number of primes needed,
, is roughly the same.
Doing this process recursively, we can get the primes as small as
.
That means we can compute and store
on all the possible values in
time and space.
If we take
, we get
, so the time/space requirement is just
Kedlaya and Umans further show how to combine this preprocessing with fast (FFT) multipoint evaluation.
This allows optimal algorithms for many important algebraic problems, such as polynomial
modular composition
Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a s ...
.
Specific polynomials
While general polynomials require
operations to evaluate, some polynomials can be computed much faster.
For example, the polynomial
can be computed using just one multiplication and one addition since
Evaluation of powers
A particularly interesting type of polynomial is powers like
.
Such polynomials can always be computed in
operations.
Suppose, for example, that we need to compute
; we could simply start with
and multiply by
to get
.
We can then multiply that by itself to get
and so on to get
and
in just four multiplications.
Other powers like
can similarly be computed efficiently by first computing
by 2 multiplications and then multiplying by
.
The most efficient way to compute a given power
is provided by addition-chain exponentiation. However, this requires designing a specific algorithm for each exponent, and the computation needed for designing these algorithms are difficult (
NP-complete), so exponentiation by squaring is generally preferred for effective computations.
Polynomial families
Often polynomials show up in a different form than the well known
.
For polynomials in
Chebyshev form we can use
Clenshaw algorithm In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials. Note that this paper is written in terms of the ''Shifted'' Chebyshev polynomials of the ...
.
For polynomials in
Bézier form we can use
De Casteljau's algorithm In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to s ...
,
and for
B-spline
In the mathematical subfield of numerical analysis, a B-spline or basis spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. Any spline function of given degree can be expresse ...
s there is
De Boor's algorithm In the mathematical subfield of numerical analysis de Boor's algorithmC. de Boor 971 "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121. is a polynomial-time and numerically s ...
.
Hard polynomials
The fact that some polynomials can be computed significantly faster than "general polynomials" suggests the question: Can we give an example of a simple polynomial that cannot be computed in time much smaller than its degree?
Volker Strassen has shown that the polynomial
:
cannot be evaluated by with less than
multiplications and
additions.
At least this bound holds if only operations of those types are allowed, giving rise to a so-called "polynomial chain of length