Horner scheme

Horner scheme

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 form. 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::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,:

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;. We use a synthetic diagram to organize these calculations and make the process faster. x_0 | x^3 x^2 x^1 x^0

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)}.

Floating point multiplication and division

Horner's method is a fast, code-efficient method for multiplication and division of binary numbers on a microcontroller with no math coprocessor. One of the binary numbers to be multiplied is represented as a trivial polynomial, where, (using the above notation): ai = 1, and x = 2. Then, x (or x to some power) is repeatedly factored out. In this binary numeral system (base 2), x = 2, so powers of 2 are repeatedly factored out.

Example

For example, to find the product of two numbers, (0.15625) and "m":: ( 0.15625) m = (0.00101_b) m = ( 2^{-3} + 2^{-5}) m = (2^{-3})m + (2^{-5})m = 2^{-3} (m + (2^{-2})m) = 2^{-3} (m + 2^{-2} (m))

Method

To find the product of two binary numbers, "d" and "m".
*1. A register holding the intermediate result is initialized to (d).
*2. Begin in (m) with the least significant (rightmost) non-zero bit,
**2b. Count (to the left) the number of bit positions to the next most significant non-zero bit. If there are no more-significant bits, then take the value of the current bit position.
**2c. Using that value, perform a right-shift operation by that number of bits on the register holding the intermediate result
*3. If all the non-zero bits were counted, then the intermediate result register now holds the final result. Otherwise, add (d) to the intermediate result, and continue in step #2 with the next most significant bit in (m).

Derivation

In general, for a binary number with bit values: ( d_3 d_2 d_1 d_0 ) the product is:: (d_3 2^3 + d_2 2^2 + d_1 2^1 + d_0 2^0)m = d_3 2^3 m + d_2 2^2 m + d_1 2^1 m + d_0 2^0 m At this stage in the algorithm, it is required that terms with zero-valued coefficients are dropped, so that only binary coefficients equal to one are counted, thus the problem of multiplication or division by zero is not an issue, despite this implication in the factored equation:

: = d_0(m + 2 frac{d_1}{d_0} (m + 2 frac{d_2}{d_1} (m + 2 frac{d_3}{d_2} (m))))

The denominators all equal one (or the term is absent), so this reduces to:: = d_0(m + 2 {d_1} (m + 2 {d_2} (m + 2 {d_3} (m)))) or equivalently (as consistent with the "method" described above):: = d_3(m + 2^{-1} {d_2} (m + 2^{-1}{d_1} (m + {d_0} (m))))

In binary (base 2) math, multiplication by a power of 2 is merely an register shift operation. Thus, multiplying by 2 is calculated in base-2 by a right arithmetic shift. The factor (2-1) is a right arithmetic shift, a (0) results in no operation (since 20 = 1, is the multiplicative identity element), and a (21) results in a left arithmetic shift.The multiplication product can now be quickly calculated using only arithmetic shift operations, addition and subtraction.

The method is particularly fast on processors supporting a single-instruction shift-and-addition-accumulate. Compared to a C floating-point library, Horner's method sacrifices some accuracy, however it is nominally 13 times faster (16 times faster when the "canonical signed digit" (CSD) form is used), and uses only 20% of the code space (Kripasagar 62).

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.

Efficiency

Evaluation using the monomial form of a degree-"n" polynomial requires at most "n" additions and ("n"2 + "n")/2 multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. (This can be reduced to "n" additions and 2"n" + 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 2"n" times the number of bits of "x" (the evaluated polynomial has approximate magnitude "x""n", and one must also store "x""n" 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{leftlfloor n/2 ight floor + 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, the Chinese mathematician Qin Jiushao in his "Mathematical Treatise in Nine Sections" in the 13th century, and even earlier to the Persian Muslim mathematician Sharaf al-Dīn al-Tūsī in the 12th century. [J. L. Berggren (1990). "Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat", "Journal of the American Oriental Society" 110 (2), p. 304-309.] The earliest use of Horner's scheme was in "The Nine Chapters on the Mathematical Art", a Chinese work of the Han Dynasty (202 BC – 220 AD) edited by Liu Hui (fl. 3rd century). [Temple, Robert. (1986). "The Genius of China: 3,000 Years of Science, Discovery, and Invention". With a forward by Joseph Needham. New York: Simon and Schuster, Inc. ISBN 0671620282. Page 142.]

ee also

*Ruffini's rule
*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 splines in B-spline form
*Estrin's scheme that is susceptible to parallelization on modern computer architectures.

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.
*Cite journal
last = Kripasagar
first = Venkat
title = Efficient Micro Mathematics - Multiplication and Division Techniques for MCUs
journal = Circuit Cellar magazine
issue = 212
pages = p. 60
year = 2008
date = March 2008

External links

*
* [http://math.fullerton.edu/mathews/n2003/HornerMod.html Module for Horner's Method by John H. Mathews]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Horner — is an English surname that derives from the occupation horner who is a person who cuts the horns off cattle, or deals in horns , or plays a horn.Horner refers to: *People named Horner **Bob Horner (1957 ndash;), American professional baseball… …   Wikipedia

  • Estrin's scheme — In numerical analysis Estrin s scheme (also known as Estrin s method) is an algorithm for numerical evaluation of polynomials. The Horner scheme for evaluation of polynomials is one of the most commonly used algorithms for this purpose and unlike …   Wikipedia

  • William George Horner — (1786 – September 22, 1837) was a British mathematician who was born in Bristol England and died in Bath England. He invented the zoetrope in 1834. ee also*Horner scheme External links * …   Wikipedia

  • New Zealand Emissions Trading Scheme — See also: Climate change in New Zealand The New Zealand Emissions Trading Scheme (NZ ETS) is a national all sectors all greenhouse gases all free allocation uncapped emissions trading scheme. The NZ ETS was first legislated in September 2008 by… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

  • Rational root theorem — In algebra, the rational root theorem (or rational root test to find the zeros) states a constraint on solutions (or roots) to the polynomial equation:a nx^n+a {n 1}x^{n 1}+cdots+a 0 = 0,!with integer coefficients.Let a 0 and a n be nonzero.Then… …   Wikipedia

  • Dynastie Song/Traduction à faire — Modèle:Otheruses Sommaire 1 0 2 Histoire de la dynastie Song 2.1 Les Song du Nord 2.2 Les Song du Sud …   Wikipédia en Français

  • De Casteljau's algorithm — In the mathematical field of numerical analysis, De Casteljau s algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau s algorithm can also be used to… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”