Tutorials › Calculus II › Efficient Polynomial Evaluation with Horner’s Rule

Home  /  Tutorials  /  Taylor Methods in Computation

Taylor Methods in Computation · Tutorial 876 of 998

Efficient Polynomial Evaluation with Horner's Rule

Rewrite Taylor polynomials as nested expressions and use Horner’s rule to evaluate them with fewer multiplications for dense polynomials of degree at least two.

Advanced 10 min read

What You'll Learn

  • Express a Taylor polynomial using powers of the displacement from its expansion center.
  • Convert ordinary polynomial form into nested Horner form.
  • Justify Horner’s recurrence and evaluate it from the highest-degree coefficient downward.
  • Compare Horner and direct-evaluation operation counts under a stated arithmetic model.
  • Check numerical evaluations by substituting into the original polynomial.
  • Recognize why degree-one polynomials have equal generic operation counts under the comparison used here.

Why the Form of a Polynomial Matters

A Taylor polynomial is often first written as a sum of powers of the displacement from its center. That form makes the coefficients and powers easy to identify, but it is not always the most efficient way to calculate a value. Rewriting the polynomial as a nested expression can reduce the number of multiplications required.

This matters whenever a polynomial is used as a computational approximation. The polynomial itself does not change: only the order in which its terms are evaluated changes. The number of arithmetic operations depends on the evaluation method, so comparisons should state which methods and operations are being counted.

Key idea: Horner’s rule rewrites a polynomial so that each successive multiplication by the input displacement is followed by an addition. For a dense polynomial of degree at least two, this uses fewer multiplications than direct evaluation by sequentially forming powers and then multiplying each power by its coefficient.

From Taylor Form to Polynomial Coefficients

For a function \(f\), the Taylor polynomial of degree \(n\) centered at \(a\) is

$$ T_n(x)=\sum_{k=0}^{n}\frac{f^{(k)}(a)}{k!}(x-a)^k. $$

For evaluation, it is convenient to set \(u=x-a\), the displacement from the center, and write the coefficients as \(c_k=f^{(k)}(a)/k!\). Then the same polynomial is

$$ P(u)=c_0+c_1u+c_2u^2+\cdots+c_nu^n. $$

The coefficients are treated as already known. The task here is to evaluate this finite polynomial, not to estimate the error between it and the function it approximates. That approximation error is a separate question.

Definition: If \(P(u)=\sum_{k=0}^{n}c_ku^k\), its Horner form is the nested expression \(c_0+u(c_1+u(c_2+\cdots+u(c_{n-1}+uc_n)\cdots))\). The nesting proceeds from the coefficient of the highest power down to the constant coefficient.

Horner’s Recurrence

Rather than forming each power of \(u\), Horner’s rule starts at the highest-degree coefficient and repeatedly multiplies by \(u\) and adds the next coefficient. Define the intermediate values by

$$ b_n=c_n,\qquad b_k=c_k+u b_{k+1}\quad (k=n-1,n-2,\ldots,0). $$

The final value \(b_0\) is \(P(u)\). In practice, the recurrence is applied in descending index order, using the same \(u\) at each stage.

1
Start at the leading coefficient.
Set the current value equal to \(c_n\).
2
Move down one coefficient at a time.
Multiply the current value by \(u\), then add the next coefficient.
3
Finish at the constant coefficient.
After adding \(c_0\), the current value equals the polynomial evaluation.

Why the Nested Form Is Equal to the Original

The recurrence works because each intermediate value represents the part of the polynomial that remains after factoring out the powers already accounted for. More precisely, for every \(k\) from \(0\) to \(n\),

$$ b_k=\sum_{j=k}^{n}c_j u^{j-k}. $$

At \(k=n\), the sum contains only \(c_n\), so the statement holds because \(b_n=c_n\). Now suppose it holds for \(b_{k+1}\). The recurrence gives

$$ \begin{aligned} b_k &=c_k+u b_{k+1}\\ &=c_k+u\sum_{j=k+1}^{n}c_j u^{j-(k+1)}\\ &=c_k+\sum_{j=k+1}^{n}c_j u^{j-k}\\ &=\sum_{j=k}^{n}c_j u^{j-k}. \end{aligned} $$

This proves the stated formula at index \(k\), completing the backward argument. At \(k=0\), it says \(b_0=\sum_{j=0}^{n}c_j u^j=P(u)\). Thus Horner’s rule evaluates exactly the same polynomial as the original sum.

Worked Example: A Cubic Taylor Polynomial Centered at One

Worked Example: A Cubic Taylor Polynomial Centered at One

Evaluate \(T_3(x)=2-3(x-1)+4(x-1)^2+(x-1)^3\) at \(x=3\), first directly and then by Horner’s rule.

The displacement is \(u=x-1=3-1=2\). Direct evaluation gives

$$ \begin{aligned} T_3(3) &=2-3(2)+4(2^2)+2^3\\ &=2-6+4(4)+8\\ &=2-6+16+8\\ &=20. \end{aligned} $$

For Horner’s form, the coefficients in ascending powers of \(u\) are \(c_0=2\), \(c_1=-3\), \(c_2=4\), and \(c_3=1\). Nesting from the highest-degree coefficient down gives

$$ T_3(3)=2+2\bigl(-3+2(4+2(1))\bigr). $$

Evaluate from the inside outward:

$$ \begin{aligned} 1\cdot 2+4&=6,\\ 6\cdot 2-3&=9,\\ 9\cdot 2+2&=20. \end{aligned} $$

The results agree. Substituting \(u=2\) into the original polynomial also gives \(2-6+16+8=20\), checking the nested evaluation.

Operation Counts and Their Assumptions

To compare methods fairly, use this specific arithmetic model: count each scalar addition and multiplication as one operation; regard the coefficients as available; do not use fused multiply-add instructions; and do not exploit special coefficient values to skip operations. Both methods use the displacement \(u=x-a\), so its calculation is common to both and is excluded from the comparison.

For a dense degree-\(n\) polynomial, Horner’s recurrence has \(n\) stages after setting \(b_n=c_n\). Each stage uses one multiplication by \(u\) and one addition of a coefficient. Therefore it uses \(n\) multiplications and \(n\) additions.

For direct evaluation in the comparison used here, form \(u^2,\ldots,u^n\) sequentially. That takes \(n-1\) multiplications. Then multiply each of the \(n\) nonconstant terms by its coefficient, and add those terms to \(c_0\). This takes \(n\) more multiplications and \(n\) additions, for a total of \(2n-1\) multiplications and \(n\) additions.

Method for a dense degree-\(n\) polynomialMultiplicationsAdditions
Direct: sequential powers, then coefficient products\(2n-1\)\(n\)
Horner’s rule\(n\)\(n\)

Consequently, for dense polynomials of degree at least two, Horner’s rule saves \(n-1\) multiplications under this model, with the same number of additions. At degree one, both methods use one multiplication and one addition: the counts are equal. Thus Horner’s rule does not increase the generic operation count in this comparison, but it does not reduce it for degree one. These counts describe the stated evaluation schemes; a different method of computing powers or special coefficients can change the comparison.

Worked Example: Evaluating an Exponential Taylor Polynomial

Worked Example: Evaluating an Exponential Taylor Polynomial

The degree-four Taylor polynomial for \(e^x\) centered at zero is \(T_4(x)=1+x+x^2/2+x^3/6+x^4/24\). Evaluate it at \(x=1/2\) by Horner’s rule and check the result by direct evaluation.

In descending coefficient order, the coefficients are \(1/24,\ 1/6,\ 1/2,\ 1,\ 1\). Horner’s form is

$$ T_4(x)=1+x\left(1+x\left(\frac12+x\left(\frac16+\frac{x}{24}\right)\right)\right). $$

Set \(x=1/2\), then evaluate each stage:

$$ \begin{aligned} b_4&=\frac{1}{24},\\ b_3&=\frac16+\frac12\left(\frac{1}{24}\right) =\frac{8}{48}+\frac{1}{48}=\frac{3}{16},\\ b_2&=\frac12+\frac12\left(\frac{3}{16}\right) =\frac{16}{32}+\frac{3}{32}=\frac{19}{32},\\ b_1&=1+\frac12\left(\frac{19}{32}\right) =\frac{64}{64}+\frac{19}{64}=\frac{83}{64},\\ b_0&=1+\frac12\left(\frac{83}{64}\right) =\frac{128}{128}+\frac{83}{128}=\frac{211}{128}. \end{aligned} $$

For a direct check, the powers are \(x^2=1/4\), \(x^3=1/8\), and \(x^4=1/16\). Therefore

$$ \begin{aligned} T_4\left(\frac12\right) &=1+\frac12+\frac{1}{8}+\frac{1}{48}+\frac{1}{384}\\ &=\frac{384}{384}+\frac{192}{384}+\frac{48}{384} +\frac{8}{384}+\frac{1}{384}\\ &=\frac{633}{384}=\frac{211}{128}. \end{aligned} $$

Both evaluations give \(211/128=1.6484375\). Under the stated generic count, Horner’s method uses four multiplications and four additions. Sequential direct evaluation uses three multiplications to form powers, four coefficient multiplications, and four additions: seven multiplications and four additions.

Worked Example: Degree One Has No Operation-Count Saving

Worked Example: Degree One Has No Operation-Count Saving

Evaluate \(P(x)=3+2(x-1)\) at \(x=4\), and compare the operation counts.

The displacement is \(u=4-1=3\). Direct evaluation gives

$$ P(4)=3+2(3)=3+6=9. $$

Horner’s form, with \(c_0=3\) and \(c_1=2\), is \(c_0+u c_1\). It gives

$$ P(4)=3+3(2)=3+6=9. $$

Both evaluations use one multiplication and one addition after \(u\) is known. Substitution into the original expression confirms \(3+2(4-1)=9\). This example shows why the claim that Horner’s rule always reduces the multiplication count would be too broad: for degree one, the generic counts are equal.

A Common Pitfall: Using the Wrong Input

For a Taylor polynomial centered at \(a\), the powers are powers of \(u=x-a\), not powers of \(x\). Forgetting the center changes the input to the polynomial and can produce a plausible-looking but incorrect calculation.

For the cubic in the first example, \(a=1\) and \(x=3\), so the required input is \(u=3-1=2\). If one mistakenly uses \(x=3\) directly, the calculation becomes

$$ 2-3(3)+4(3^2)+3^3=2-9+36+27=56, $$

which is not the value of the Taylor polynomial at \(x=3\). The correction is to use the displacement \(u=2\), giving \(2-3(2)+4(2^2)+2^3=20\). The same displacement must be used at every Horner stage.

When Horner’s Rule Is Useful

Horner’s rule gives a systematic way to evaluate a polynomial while avoiding the separate formation of each power. It is especially useful when evaluating dense polynomials repeatedly, as can happen when Taylor polynomials serve as local computational models. The nested structure also gives a straightforward sequence of intermediate values to record and check.

The operation-count comparison does not by itself guarantee that every implementation produces identical rounded results on a computer. It establishes an exact algebraic identity and compares arithmetic counts under a stated model. The central practice is to preserve the same polynomial, use the correct displacement from its center, and evaluate coefficients in the correct order.

Check Your Understanding

Answer these questions using the definitions and comparison model in this tutorial.

  1. Write \(P(u)=5-2u+3u^2\) in Horner form.
  2. For a degree-\(n\) polynomial, how many multiplications and additions does Horner’s recurrence use under the stated model?
  3. Why are the generic multiplication counts equal for direct and Horner evaluation when \(n=1\)?
  4. If a Taylor polynomial is centered at \(a=2\) and evaluated at \(x=5\), what input should be used in its powers?
  5. For a dense degree-four polynomial, compare the multiplication counts of the two evaluation schemes used here.

Previous

Next

Back to Tutorials