Horner’s method is an algorithm for evaluating a polynomial by rewriting it as a nested sequence of multiplications and additions. For a degree- polynomial in the power basis, it requires multiplications and additions, without explicitly calculating successive powers of the argument. The same calculation supplies the coefficients needed for division by a linear polynomial and can be extended to evaluate derivatives. It is a standard technique in numerical analysis, symbolic computation, and numerical root-finding.
Nested form and recurrence
Consider the polynomial
Repeatedly factoring out gives its Horner form:
To evaluate it at , define the recurrence
The result is
Each step incorporates one more coefficient, proceeding from the highest degree to the constant term. An implementation needs only one running accumulator if the intermediate values are not required:
function horner(a[0..n], c):
value = a[n]
for k = n-1 down to 0:
value = value*c + a[k]
return value
The coefficient array here is indexed in ascending order of degree, although the algorithm reads it in descending order. Other interfaces store coefficients in the reverse order, so coefficient conventions matter when using software implementations.
Example
For
the nested form is
At , the successive accumulator values are
Thus .
Missing powers must be represented by zero coefficients. For example,
Why the method works
After the coefficients from down through have been processed, the accumulator contains
Multiplication by , followed by addition of , produces the corresponding expression for the next step. This establishes the result by mathematical induction.
The identity is algebraic rather than specifically numerical. It applies to real and complex coefficients and, more generally, to polynomials over a commutative ring. No division is required, so it also works in modular arithmetic and over a finite field.
Computational cost
For a degree- polynomial with , the basic scheme performs exactly:
- multiplications;
- additions.
Its arithmetic cost is in big-O notation, and its auxiliary storage is when only the value is wanted.
Computing each power independently by repeated multiplication can take arithmetic operations. Generating powers successively reduces that approach to , but a straightforward implementation still generally performs more multiplications than Horner’s method.
These counts use a unit-cost arithmetic model. For large integers, rational arithmetic, or symbolic expressions, the cost of individual operations depends on operand size; linear arithmetic-operation count does not necessarily imply linear running time.
Horner’s method is particularly suitable for dense polynomials in the power basis. It is not universally the fastest evaluation strategy. Sparse polynomials may benefit from algorithms that exploit gaps between exponents, while special structure can permit factorizations that use fewer operations.
Connection with synthetic division
The intermediate values are the coefficients of the quotient when is divided by :
where
Thus the Horner recurrence simultaneously performs synthetic division and evaluates the remainder .
For the preceding example, division by gives
If , then is an exact factor. Removing such a factor is called deflation. Deflation is useful in polynomial root-finding, but using an approximate root can perturb the quotient coefficients and reduce the accuracy of subsequently computed roots.
Evaluating derivatives
A modified recurrence evaluates both and its derivative in one pass. Initialize
For , update
The update of must use the old value of . At completion,
This follows by differentiating each nested step: if a partial polynomial is updated from to , its derivative becomes . It is a simple instance of automatic differentiation.
Efficient simultaneous evaluation is useful in Newton’s method, whose iteration for a polynomial is
provided the denominator is nonzero.
Higher derivatives can also be obtained through related recurrences or repeated synthetic division. If
then
Repeated division by therefore converts power-basis coefficients into coefficients centered at , giving the polynomial’s finite Taylor expansion about that point.
Floating-point accuracy
In floating-point arithmetic, multiplication and addition generally introduce rounding errors. Horner’s method has favorable stability properties, but these do not guarantee a small relative error for every polynomial and argument.
Under the standard rounding model, assuming no overflow or underflow, the computed value satisfies a bound of the form
where
and is the unit roundoff. This bound treats each multiplication and addition as separately rounded.
The method also admits a coefficientwise backward-error interpretation: the computed result is the exact value at of a polynomial whose coefficients differ slightly from the supplied coefficients.
Nevertheless, cancellation can make the final result small compared with the magnitudes of the terms being combined. A relevant coefficientwise condition number, for , is
When this quantity is large, small coefficient perturbations or rounding errors can cause a large relative error in the answer. This often occurs near a root. For example, evaluating the expanded power-basis form of near can involve severe cancellation, even though its factored form is simple to evaluate.
Hardware supporting fused multiply-add can compute each expression with one final rounding rather than two, improving error bounds and often performance. Compensated variants of Horner’s method estimate and correct rounding errors for greater accuracy.
Applications and alternative schemes
Horner evaluation is widely used in function approximation, where a mathematical function is represented locally by a polynomial. It also appears in interpolation, polynomial root-finding, and conversion of positional numerals into numerical values. For example, a base- digit sequence is evaluated as
The nested scheme has a sequential dependency: each accumulator value depends on the preceding one. This can limit parallel execution within a single evaluation. Schemes such as Estrin’s method group terms and use powers such as , exposing more parallelism at the expense of different arithmetic and storage costs.
Horner’s method is also basis-dependent. Polynomials represented using orthogonal polynomials, such as Chebyshev polynomials, are often better evaluated directly through a basis-specific recurrence rather than first converting them to the power basis.
Historical background
The method is named after the English mathematician William George Horner, who published a numerical equation-solving procedure in 1819. His work concerned root approximation, not merely the compact polynomial-evaluation loop now commonly taught under his name.
Related procedures substantially predate that publication. Chinese mathematical traditions used successive coefficient transformations for extracting roots and solving polynomial equations; Qin Jiushao’s thirteenth-century work is a prominent example. Consequently, “Horner’s method” may refer narrowly to nested polynomial evaluation or, in historical accounts, more broadly to a root-finding procedure based on repeated polynomial transformations.