Horner scheme

related topics
{math, number, function}
{church, century, christian}
{country, population, people}
{mi², represent, 1st}

In numerical analysis, the Horner scheme (also known as 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.

Contents

Description of the algorithm

Given the polynomial

where a_0, \ldots, a_n are real numbers, we wish to evaluate the polynomial at a specific value of x, say x0.

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

Then b0 is the value of p(x0).

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

Thus, by iteratively substituting the bi into the expression,

Examples

Evaluate f_1(x)=2x^3-6x^2+2x-1\, for x=3\;. By repeatedly factoring out x, f1 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₀│   x³    x²    x¹    x⁰
 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)}.

[edit] 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.

[edit] Example

For example, to find the product of two numbers, (0.15625) and m:


\begin{align}
( 0.15625) m & = (0.00101_b) m = ( 2^{-3} + 2^{-5}) m = (2^{-3})m + (2^{-5})m \\[4pt]
& = 2^{-3} (m + (2^{-2})m) = 2^{-3} (m + 2^{-2} (m)).
\end{align}

[edit] 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).

[edit] Derivation

In general, for a binary number with bit values: (d3d2d1d0) the product is:

(d323 + d222 + d121 + d020)m = d323m + d222m + d121m + d020m

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:

Full article ▸

related documents
Euler–Mascheroni constant
Axiom schema of specification
NP-complete
Convergence of random variables
Linear map
Preadditive category
Universal property
Field extension
Splay tree
Self-organizing map
Bubble sort
Projective plane
Spectral theorem
Euler–Maclaurin formula
Hausdorff space
Binary tree
Brute-force search
Additive category
Rice's theorem
Logical connective
Binary heap
Planar graph
Polymorphism in object-oriented programming
Isomorphism
Constructivism (mathematics)
Chinese remainder theorem
Transcendental number
Cauchy–Schwarz inequality
Trace (linear algebra)
Locally compact space