Horner scheme - Wikipedia, the free encyclopedia
The Horner scheme can also be viewed as a fast algorithm for dividing a ... By contrast, Horner's scheme requires only n additions and n multiplications, ...
en.wikipedia.org

Cramster - Definition of Horner scheme
Horner's scheme requires only n additions and n multiplications. ... Wikipedia information about Horner scheme This article is licensed under the GNU ...
www.cramster.com

Horner's Scheme
Example of Horner's Scheme. To find a root of p(x) = 4x4-2x2+3x+1, we apply ... So we need to compute p(-2) and p¢(-2). Horner's scheme ...
www.math.byu.edu

Horner's Method from Interactive Mathematics Miscellany and Puzzles
The Horner scheme computes the value P(t) of the polynomial P at x = t as the ... Both appear in the third row of the Horner scheme. ...
www.cut-the-knot.org

Talk:Horner scheme - Wikipedia, the free encyclopedia
1 A notation for the Horner scheme. 2 Numerical efficiency. 3 Old stuff. 4 error in formula ... Horner's scheme is more efficient than naive evaluation since ...
en.wikipedia.org

Horner's Method
Parallel-Serial Multiplication Using Booth's Algorithm And Horner's Scheme. ... An application of Horner's division scheme in the solution of algebriac ...
mathews.ecs.fullerton.edu

Talk: Horner scheme - Open Encyclopedia
A notation for the Horner scheme ... This is precisely the Horner scheme. ... Edit 'Talk: Horner scheme' article. ...
talk.open-encyclopedia.com

COMAP: Mathematics Instructional Resources for Innovative Educators
COMAP Home Page ... The unit introduces Horner's scheme for evaluating polynomials, and generalizes ... Students apply Horner's scheme and the related ...
www.comap.com

Energy Efficient Hardware Synthesis of Polynomial Expressions
The Horner scheme, which is a very ... The delay for Horner scheme is much worse than both CSE and our technique, because the nested ...
www.ece.ucsb.edu

A small reminder about univariate interpolation.
The divided difference for the Newton form. The Horner scheme. A small reminder about univariate interpolation. ... The Horner scheme uses the following ...
www.applied-mathematics.net

Warning: mkdir() [function.mkdir]: Permission denied in /home/webs/affiliatelib2/CacheManager.php on line 12

Warning: mkdir() [function.mkdir]: No such file or directory in /home/webs/affiliatelib2/CacheManager.php on line 12

Warning: fopen(/home/templatecore2cache//*cluesnet.com/d3/d3f8c6425e80bd34f9133724f31387394df37b4a.tc2cache) [function.fopen]: failed to open stream: No such file or directory in /home/webs/affiliatelib2/CacheManager.php on line 130

Warning: fwrite(): supplied argument is not a valid stream resource in /home/webs/affiliatelib2/CacheManager.php on line 131

Warning: fclose(): supplied argument is not a valid stream resource in /home/webs/affiliatelib2/CacheManager.php on line 132

In numerical analysis, the Horner scheme or Horner algorithm, named after William George Horner, is an algorithm for the efficient evaluation of polynomials in Monomial basis. Horner's method describes a manual process by which one may approximate the roots of a polynomial equation. The Horner scheme can also be viewed as a fast algorithm for dividing a polynomial by a linear polynomial with Ruffini's rule.

Description of the algorithm Given the polynomial p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n, where a_0, \ldots, a_n are real numbers,we wish to evaluate the polynomial at a specific value of x\,\!, say x_0\,\!.

To accomplish this, we define a new sequence of constants as follows: {| ||-|b_n\,\!|:=\,\!|a_n\,\!|-|b_{n-1}\,\!|:=\,\!|a_{n-1} + b_n x_0\,\!|-||align="center"|\vdots||-|b_0\,\!|:=\,\!|a_0 + b_1 x_0\,\!|}Then b_0\,\! is the value of p(x_0)\,\!.

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 + \cdots x(a_{n-1} + a_n x)\dots))

Thus, by iteratively substituting the b_i into the expression, {| ||-|p(x_0)\,\!|=\,\!|a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(a_{n-1} + b_n x_0)\dots))|-||=\,\!|a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(b_{n-1})\dots))|-||align="center"|\vdots||-||=\,\!|a_0 + x_0(b_1)\,\!|-||=\,\!|b_0\,\!|}

Examples Evaluate f_1(x)=2x^3-6x^2+2x-1\, for x=3\;. By repeatedly factoring out x, f_1 may be rewritten as x(x(2x-6)+2)-1\; for x=3\;. We use a synthetic diagram to organize these calculations and make the process faster.

3 | 2 -6 2 -1 | 6 0 6 |---------------------- 2 0 2 5

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. The answer is 5.

As a consequence of the polynomial remainder theorem, the entries in the third row are the coefficients of the second-degree polynomial that is the quotient of f1/(x-3). The remainder is 5. This makes Horner's method useful for polynomial long division.

Divide x^3-6x^2+11x-6\, by x-2:

2 | 1 -6 11 -6 | 2 -8 6 |---------------------- 1 -4 3 0

The quotient is x^2-4x+3.

Let f_1(x)=4x^4-6x^3+3x-5\, and f_2(x)=2x-1\,. Divide f_1(x)\, by f_2\,(x) using Horner's scheme.

2 | 4 -6 0 3 | -5 ---------------------------|------ 1 | 2 -2 -1 | 1 | | |----------------------|------- 2 -2 -1 1 | -4

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

\frac{f_1(x)}{f_2(x)}=2x^3-2x^2-x+1-\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 ai coefficients are the digits of the base-x representation of a given number — and can also be used if x is a matrix (math), in which case the gain in computational efficiency is even greater.

Efficiency Evaluation using the monomial form of a degree-n polynomial requires at most n additions and (n2 + n)/2 multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. (This can be reduced to n additions and 2n + 1 multiplications by evaluating the powers of x iteratively.) If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately 2n times the number of bits of x (the evaluated polynomial has approximate magnitude xn, and one must also store xn itself). By contrast, Horner's scheme requires only n additions and n multiplications, and its storage requirements are only n times the number of bits of x. Alternatively, Horner's scheme can be computed with n fused multiply-adds.

It has been shown that the Horner scheme is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. 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, in 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 {\scriptstyle{\left\lfloor \frac{n}{2} \right\rfloor + 2--> multiplications and n additions (see 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 mathematics 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
• De Boor's algorithm to evaluate spline curve in B-spline 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.
• {{cite book

|last= Spiegel|first= Murray R.|title= Schaum's Outline of Theory and Problems of College Algebra|year= 1956|publisher= McGraw-Hill Book Company-->

• 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 0-262-03293-7. Problem 2-3 (pg.39) and page 823 of section 30.1: Representation of polynomials.

External links

• Module for Horner's Method by John H. Mathews