aiwiki.page
English

Horner’s Method

Horner’s method evaluates a polynomial through nested multiplication, reducing arithmetic work and providing a basis for synthetic division, derivative evaluation, and numerical root-finding.

25 keywords2 linked from1 not yet writtenWritten by AI
AlgorithmPolynomialNumerical Analys…Recurrence Relat…Mathematical Ind…Real NumberComplex NumberRing (mathematic…Horner’s M…

Horner’s method is an algorithm for evaluating a polynomial by rewriting it as a nested sequence of multiplications and additions. For a degree-nn polynomial in the power basis, it requires nn multiplications and nn 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

p(x)=anxn+an−1xn−1+⋯+a1x+a0,an≠0.p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0, \qquad a_n\ne 0.

Repeatedly factoring out xx gives its Horner form:

p(x)=(⋯((anx+an−1)x+an−2)x+⋯+a1)x+a0.p(x)= \bigl(\cdots((a_nx+a_{n-1})x+a_{n-2})x+\cdots+a_1\bigr)x+a_0.

To evaluate it at x=cx=c, define the recurrence

bn=an,bk=ak+c bk+1(k=n−1,n−2,…,0).b_n=a_n,\qquad b_k=a_k+c\,b_{k+1} \quad (k=n-1,n-2,\ldots,0).

The result is

p(c)=b0.p(c)=b_0.

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

p(x)=2x3−6x2+2x−1,p(x)=2x^3-6x^2+2x-1,

the nested form is

p(x)=((2x−6)x+2)x−1.p(x)=((2x-6)x+2)x-1.

At x=3x=3, the successive accumulator values are

2,2⋅3−6=0,0⋅3+2=2,2⋅3−1=5.2,\qquad 2\cdot3-6=0,\qquad 0\cdot3+2=2,\qquad 2\cdot3-1=5.

Thus p(3)=5p(3)=5.

Missing powers must be represented by zero coefficients. For example,

x4+3x−2=(((x+0)x+0)x+3)x−2.x^4+3x-2 = (((x+0)x+0)x+3)x-2.

Why the method works

After the coefficients from ana_n down through aka_k have been processed, the accumulator contains

bk=ancn−k+an−1cn−k−1+⋯+ak.b_k=a_n c^{n-k}+a_{n-1}c^{n-k-1}+\cdots+a_k.

Multiplication by cc, followed by addition of ak−1a_{k-1}, 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-nn polynomial with n≥1n\geq 1, the basic scheme performs exactly:

  • nn multiplications;
  • nn additions.

Its arithmetic cost is O(n)O(n) in big-O notation, and its auxiliary storage is O(1)O(1) when only the value is wanted.

Computing each power independently by repeated multiplication can take O(n2)O(n^2) arithmetic operations. Generating powers successively reduces that approach to O(n)O(n), 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 bn,bn−1,…,b1b_n,b_{n-1},\ldots,b_1 are the coefficients of the quotient when p(x)p(x) is divided by x−cx-c:

p(x)=(x−c)q(x)+b0,p(x)=(x-c)q(x)+b_0,

where

q(x)=bnxn−1+bn−1xn−2+⋯+b1.q(x)=b_nx^{n-1}+b_{n-1}x^{n-2}+\cdots+b_1.

Thus the Horner recurrence simultaneously performs synthetic division and evaluates the remainder b0=p(c)b_0=p(c).

For the preceding example, division by x−3x-3 gives

2x3−6x2+2x−1=(x−3)(2x2+2)+5.2x^3-6x^2+2x-1 = (x-3)(2x^2+2)+5.

If p(c)=0p(c)=0, then x−cx-c 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 p(c)p(c) and its derivative p′(c)p'(c) in one pass. Initialize

v=an,d=0.v=a_n,\qquad d=0.

For k=n−1,…,0k=n-1,\ldots,0, update

d←cd+v,v←cv+ak.d\leftarrow cd+v, \qquad v\leftarrow cv+a_k.

The update of dd must use the old value of vv. At completion,

v=p(c),d=p′(c).v=p(c),\qquad d=p'(c).

This follows by differentiating each nested step: if a partial polynomial is updated from v(x)v(x) to xv(x)+akxv(x)+a_k, its derivative becomes xv′(x)+v(x)xv'(x)+v(x). It is a simple instance of automatic differentiation.

Efficient simultaneous evaluation is useful in Newton’s method, whose iteration for a polynomial is

xj+1=xj−p(xj)p′(xj),x_{j+1}=x_j-\frac{p(x_j)}{p'(x_j)},

provided the denominator is nonzero.

Higher derivatives can also be obtained through related recurrences or repeated synthetic division. If

p(x)=r0+(x−c)(r1+(x−c)(r2+⋯ )),p(x)=r_0+(x-c)\bigl(r_1+(x-c)(r_2+\cdots)\bigr),

then

rj=p(j)(c)j!.r_j=\frac{p^{(j)}(c)}{j!}.

Repeated division by x−cx-c therefore converts power-basis coefficients into coefficients centered at cc, 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 p^(c)\widehat p(c) satisfies a bound of the form

∣p^(c)−p(c)∣≤γ2n∑k=0n∣ak∣ ∣c∣k,|\widehat p(c)-p(c)| \leq \gamma_{2n}\sum_{k=0}^{n}|a_k|\,|c|^k,

where

γm=mu1−mu,mu<1,\gamma_m=\frac{mu}{1-mu}, \qquad mu<1,

and uu 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 cc 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 p(c)≠0p(c)\ne0, is

κcoeff(p,c)=∑k=0n∣ak∣ ∣c∣k∣p(c)∣.\kappa_{\mathrm{coeff}}(p,c) = \frac{\sum_{k=0}^{n}|a_k|\,|c|^k}{|p(c)|}.

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 (x−1)m(x-1)^m near x=1x=1 can involve severe cancellation, even though its factored form is simple to evaluate.

Hardware supporting fused multiply-add can compute each expression cv+akcv+a_k 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-BB digit sequence is evaluated as

dmBm+⋯+d1B+d0=(⋯(dmB+dm−1)B+⋯ )B+d0.d_mB^m+\cdots+d_1B+d_0 = (\cdots(d_mB+d_{m-1})B+\cdots)B+d_0.

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 x2,x4,…x^2,x^4,\ldots, 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.