In the mathematical subfield of numerical analysis, the Horner scheme or Horner algorithm, named after William George Horner, is an algorithm for the efficient evaluation of polynomials in monomial form.

Description of the algorithm

---

Given the polynomial

$p(x)\; =\; a\_0\; +\; a\_1\; x\; +\; a\_2\; x^2\; +\; a\_3\; x^3\; +\; \backslash cdots\; +\; a\_n\; x^n,$

where $a\_0,\; \backslash ldots,\; a\_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x\backslash ,\backslash !$, say $x\_0\backslash ,\backslash !$.

To accomplish this, we define a new sequence of constants as follows:

{| $b\_n\backslash ,\backslash !$ $:=\backslash ,\backslash !$ $a\_n\backslash ,\backslash !$ $b\_\{n-1\}\backslash ,\backslash !$ $:=\backslash ,\backslash !$ $a\_\{n-1\}\; +\; b\_n\; x\_0\backslash ,\backslash !$ $\backslash vdots$ $b\_0\backslash ,\backslash !$ $:=\backslash ,\backslash !$ $a\_0\; +\; b\_1\; x\_0\backslash ,\backslash !$

Then $b\_0\backslash ,\backslash !$ is the value of $p(x\_0)\backslash ,\backslash !$.

To see why this works, note that the polynomial can be written in the form

$p(x)\; =\; a\_0\; +\; x(a\_1\; +\; x(a\_2\; +\; \backslash cdots\; x(a\_\{n-1\}\; +\; a\_n\; x)\; \backslash cdots\; ))$

Thus, by iteratively substituting the $b\_i$ into the expression,

{| $p(x)\backslash ,\backslash !$ $=\backslash ,\backslash !$ $a\_0\; +\; x(a\_1\; +\; x(a\_2\; +\; \backslash cdots\; x(a\_\{n-1\}\; +\; b\_n\; x)\; \backslash dots\; ))$ $=\backslash ,\backslash !$ $a\_0\; +\; x(a\_1\; +\; x(a\_2\; +\; \backslash cdots\; x(b\_\{n-1\})\; \backslash dots\; ))$ $\backslash vdots$ $=\backslash ,\backslash !$ $a\_0\; +\; x(b\_1)\backslash ,\backslash !$ $=\backslash ,\backslash !$ $b\_0\backslash ,\backslash !$

Examples

---

Let $f\_1(x)=4x^4-6x^3+3x-5\backslash ,$ and $f\_2(x)=2x-1\backslash ,$. Divide $f\_1(x)\backslash ,$ by $f\_2\backslash ,(x)$ using Horner's scheme. We can use a synthetic diagram to make the process faster.

2 | 4 -6 0 3 | -5

---

---

---

---

---

---

---|

---

-- 1 | 2 -2 -1 | 1 | | |

---

---

---

---

---

--|

---

--- 2 -2 -1 1 | -4

The answer is

$\backslash frac\{f\_1(x)\}\{f\_2(x)\}=2x^3-2x^2-x+1-\backslash frac\{4\}\{(2x-1)\}.$

Application

---

The Horner scheme is often used to convert between different positional numeral systems — in which case x is the base of the number system, and the a_i coefficients are the digits of the base-x representation of a given number — and can also be used if x is a matrix, in which case the gain in computational efficiency is even greater.

The Horner scheme can also be viewed as a fast algorithm for dividing a polynomial by a linear polynomial (see Ruffini's rule).

Efficiency

---

Evaluation using the monomial form of a degree-n polynomial requires at most n additions and (n²+n)/2 multiplications, if powers are calculated by repeated multiplication. Horner's scheme requires only n additions and n multiplications. (Minimizing the number of multiplications is desirable because they are time consuming and numerically unstable compared to addition.) Alternatively, Horner's scheme can be computed with n fused multiply-adds.

It has been shown that the Horner scheme is optimal, in that any algorithm to evaluate an arbitrary polynomial must use at least as many steps. That the number of additions required is minimal was shown by Alexander Ostrowski in 1954, that the number of multiplications is minimal by Victor Pan 1966. When x is a matrix, the Horner scheme is not optimal.

This assumes that the polynomial is evaluated in monomial form and no preconditioning of the representation is allowed, which makes sense if the polynomial is evaluated only once. However, if preconditioning is allowed and the polynomial is to be evaluated many times, then faster algorithms are possible. They involve a transformation of the representation of the polynomial. In general, a degree-n polynomial can be evaluated using only $\backslash left\backslash lfloor\; \backslash frac\{n\}\{2\}\; \backslash right\; \backslash rfloor\; +2$ multiplications and n additions D.E. Knuth: The Art of Computer Programming, Vol.2

History

---

Even though the algorithm is named after William George Horner, who described it in 1819, the method was already known to Isaac Newton in 1669, and even earlier to the Chinese mathematician Ch'in Chiu-Shao in the 13th century.

See also

---

• Clenshaw algorithm to evaluate polynomials in Chebyshev form
• De Casteljau's algorithm to evaluate polynomials in Bézier form

References

---

• William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. In Philosophical Transactions of the Royal Society of London, pp. 308-335, July 1819.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 486–488 in section 4.6.4.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Problem 2-3 (pg.39) and page 823 of section 30.1: Representation of polynomials.

Numerical analysis

Horner-Schema | Algoritmo de Horner | Méthode de Hörner | Hornerschema | Schemat Hornera | Esquema de Horner | Horners algoritm