In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. It is named after William George Horner, although it is much older, attributed by Horner to Joseph-Louis Lagrange, and was discovered hundreds of years earlier by Chinese and Persian mathematicians. After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials. The algorithm is based on Horner's rule, in which a polynomial is written in nested form:
a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n x n =
a 0 + x ( a 1 + x ( a 2 + x ( a 3 + ⋯ + x ( a n − 1 + x a n ) ⋯ ) ) ) . {\displaystyle {\begin{aligned}&a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\={}&a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}
This allows the evaluation of a polynomial of degree n with only n {\displaystyle n} multiplications and n {\displaystyle n} additions. This is optimal, as it is impossible to evaluate polynomials of degree n with fewer arithmetic operations when both x and the coefficients a0, ..., an are given as input. Horner's method and Horner–Ruffini method also refers to a method for approximating the roots of polynomials, described by Horner in 1819. It is a variant of the Newton–Raphson method made more efficient for hand calculation by application of Horner's rule. It was widely used until computers came into general use around 1970.
Polynomial evaluation and long division Given the polynomial p ( x ) = ∑ i = 0 n a i x i = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n x n , {\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},} where a 0 , … , a n {\displaystyle a_{0},\ldots ,a_{n}} are constant coefficients, the problem is to evaluate the polynomial at a specific value x 0 {\displaystyle x_{0}} of x . {\displaystyle x.}
For this, a new sequence of constants is defined recursively as follows:
Then b 0 {\displaystyle b_{0}} is the value of p ( x 0 ) {\displaystyle p(x_{0})} . To see why this works, the polynomial can be written in the form
p ( x ) = a 0 + x ( a 1 + x ( a 2 + x ( a 3 + ⋯ + x ( a n − 1 + x a n ) ⋯ ) ) ) . {\displaystyle p(x)=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}\ .}
Thus, by iteratively substituting the b i {\displaystyle b_{i}} into the expression,
p ( x 0 ) = a 0 + x 0 ( a 1 + x 0 ( a 2 + ⋯ + x 0 ( a n − 1 + b n x 0 ) ⋯ ) ) = a 0 + x 0 ( a 1 + x 0 ( a 2 + ⋯ + x 0 b n − 1 ) ) ⋮ = a 0 + x 0 b 1 = b 0 . {\displaystyle {\begin{aligned}p(x_{0})&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\cdots {\big )}{\Big )}\\&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}b_{n-1}{\big )}{\Big )}\\&~~\vdots \\&=a_{0}+x_{0}b_{1}\\&=b_{0}.\end{aligned}}}
Similarly, it can be shown that:
Suggesting a convenient procedure for determining the result of the polynomial division
p ( x ) / ( x − x 0 ) {\displaystyle p(x)/(x-x_{0})}
with b 0 {\displaystyle b_{0}} (which is equal to p ( x 0 ) {\displaystyle p(x_{0})} ) being the division's remainder. If x 0 {\displaystyle x_{0}} is a root of p ( x ) {\displaystyle p(x)} , then b 0 = 0 {\displaystyle b_{0}=0} (meaning the remainder is 0 {\displaystyle 0} ) and x − x 0 {\displaystyle x-x_{0}} a factor of p ( x ) {\displaystyle p(x)} .
Examples Evaluate f ( x ) = 2 x 3 − 6 x 2 + 2 x − 1 {\displaystyle f(x)=2x^{3}-6x^{2}+2x-1} for x = 3 {\displaystyle x=3} . We use synthetic division as follows:
3 2 − 6 2 − 1 6 0 6 2 0 2 5 {\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\\\\\end{array}}&{\begin{array}{|rrrr}\ 2&-6&2&-1\\&6&0&6\\\hline 2&0&2&5\end{array}}\end{array}}}
The entries in the third row are the sum of those in the first two. Each entry in the second row is the product of the x-value (3 in this example) with the third-row entry immediately to the left. The entries in the first row are the coefficients of the polynomial to be evaluated. Then the remainder of f ( x ) {\displaystyle f(x)} on division by x − 3 {\displaystyle x-3} is 5. But by the polynomial remainder theorem, we know that the remainder is f ( 3 ) {\displaystyle f(3)} . Thus, f ( 3 ) = 5 {\displaystyle f(3)=5} . In this example, if a 3 = 2 , a 2 = − 6 , a 1 = 2 , a 0 = − 1 {\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1} we can see that b 3 = 2 , b 2 = 0 , b 1 = 2 , b 0 = 5 {\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5} , the entries in the third row. So, synthetic division (which was actually invented and published by Ruffini 10 years before Horner's publication) is easier to use; it can be shown to be equivalent to Horner's method. As a consequence of the polynomial remainder theorem, the entries in the third row are the coefficients of the second-degree polynomial, the quotient of f ( x ) {\displaystyle f(x)} on division by x − 3 {\displaystyle x-3} . The remainder is 5. This makes Horner's method useful for polynomial long division. Divide x 3 − 6 x 2 + 11 x − 6 {\displaystyle x^{3}-6x^{2}+11x-6} by x − 2 {\displaystyle x-2} :
2 1 − 6 11 − 6 2 − 8 6 1 − 4 3 0 {\displaystyle {\begin{array}{cc}{\begin{array}{r}\\2\\\\\\\end{array}}&{\begin{array}{|rrrr}\ 1&-6&11&-6\\&2&-8&6\\\hline 1&-4&3&0\end{array}}\end{array}}}
The quotient is x 2 − 4 x + 3 {\displaystyle x^{2}-4x+3} . Let f 1 ( x ) = 4 x 4 − 6 x 3 + 3 x − 5 {\displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5} and f 2 ( x ) = 2 x − 1 {\displaystyle f_{2}(x)=2x-1} . Divide f 1 ( x ) {\displaystyle f_{1}(x)} by f 2 ( x ) {\displaystyle f_{2}\,(x)} using Horner's method.
0.5 4 − 6 0 3 − 5 2 − 2 − 1 1 2 − 2 − 1 1 − 4 {\displaystyle {\begin{array}{cc}{\begin{array}{r}\\0.5\\\\\\\end{array}}&{\begin{array}{|rrrrr}\ 4&-6&0&3&-5\\&2&-2&-1&1\\\hline 2&-2&-1&1&-4\end{array}}\end{array}}}
The third row is the sum of the first two rows, divided by 2. Each entry in the second row is the product of 1 with the third-row entry to the left. The answer is
f 1 ( x ) f 2 ( x ) = 2 x 3 − 2 x 2 − x + 1 − 4 2 x − 1 . {\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.}
Efficiency Evaluation using the monomial form of a degree n {\displaystyle n} polynomial requires at most n {\displaystyle n} additions and ( n 2 + n ) / 2 {\displaystyle (n^{2}+n)/2} multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. The cost can be reduced to n {\displaystyle n} additions and 2 n − 1 {\displaystyle 2n-1} multiplications by evaluating the powers of x {\displaystyle x} by iteration. If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately 2 n {\displaystyle 2n} times the number of bits of x {\displaystyle x} : the evaluated polynomial has approximate magnitude x n {\displaystyle x^{n}} , and one must also store x n {\displaystyle x^{n}} itself. By contrast, Horner's method requires only n {\displaystyle n} additions and n {\displaystyle n} multiplications, and its storage requirements are only n {\displaystyle n} times the number of bits of x {\displaystyle x} . Alternatively, Horner's method can be computed with n {\displaystyle n} fused multiply–adds. Horner's method can also be extended to evaluate the first k {\displaystyle k} derivatives of the polynomial with k n {\displaystyle kn} additions and multiplications. Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. Alexander Ostrowski proved in 1954 that the number of additions required is minimal. Victor Pan proved in 1966 that the number of multiplications is minimal. However, Horner's method is not optimal for evaluation of matrix polynomials (where x {\displaystyle x} is a matrix, but the coefficients are scalar), when we count scalar multiplications and matrix multiplications separately as the former are cheaper than the latter. 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 {\displaystyle n} polynomial can be evaluated using only ⌊n/2⌋+2 multiplications and n {\displaystyle n} additions.
Parallel evaluation
A disadvantage of Horner's rule is that all of the operations are sequentially dependent, so it is not possible to take advantage of instruction level parallelism on modern computers. In most applications where the efficiency of polynomial evaluation matters, many low-order polynomials are evaluated simultaneously (for each pixel or polygon in computer graphics, or for each grid square in a numerical simulation), so it is not necessary to find parallelism within a single polynomial evaluation. If, however, one is evaluating a single polynomial of very high order, it may be useful to break it up as follows:
p ( x ) = ∑ i = 0 n a i x i = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ + a n x n = ( a 0 + a 2 x 2 + a 4 x 4 + ⋯ ) + ( a 1 x + a 3 x 3 + a 5 x 5 + ⋯ ) = ( a 0 + a 2 x 2 + a 4 x 4 + ⋯ ) + x ( a 1 + a 3 x 2 + a 5 x 4 + ⋯ ) = ∑ i = 0 ⌊ n / 2 ⌋ a 2 i x 2 i + x ∑ i = 0 ⌊ n / 2 ⌋ a 2 i + 1 x 2 i = p 0 ( x 2 ) + x p 1 ( x 2 ) . {\displaystyle {\begin{aligned}p(x)&=\sum _{i=0}^{n}a_{i}x^{i}\\[1ex]&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+\left(a_{1}x+a_{3}x^{3}+a_{5}x^{5}+\cdots \right)\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+x\left(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\cdots \right)\\[1ex]&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i+1}x^{2i}\\[1ex]&=p_{0}(x^{2})+xp_{1}(x^{2}).\end{aligned}}}
More generally, the summation can be broken into k parts:
p ( x ) = ∑ i = 0 n a i x i = ∑ j = 0 k − 1 x j ∑ i = 0 ⌊ n / k ⌋ a k i + j x k i = ∑ j = 0 k − 1 x j p j ( x k ) {\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=\sum _{j=0}^{k-1}x^{j}\sum _{i=0}^{\lfloor n/k\rfloor }a_{ki+j}x^{ki}=\sum _{j=0}^{k-1}x^{j}p_{j}(x^{k})}
where the inner summations may be evaluated using separate parallel instances of Horner's method. This requires slightly more operations than the basic Horner's method, but allows k-way SIMD execution of most of them. Modern compilers generally evaluate polynomials this way when advantageous, although for floating-point calculations this requires enabling (unsafe) reassociative math. Another use of breaking a polynomial down this way is to calculate steps of the inner summa