# Horner scheme

http://en.wikipedia.org/wiki/Horner_scheme

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.

## Description of the algorithm

Given the polynomial

where  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

for .

We use synthetic division as follows:

 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. Then the remainder of f(x) on division by x − 3 is 5.

But by the remainder theorem, we know that the remainder is f(3). Thus f(3) = 5

In this example, if a3 = 2,a2 = − 6,a1 = 2,a0 = − 1 we can see that b3 = 2,b2 = 0,b1 = 2,b0 = 5, the entries in the third row. So, synthetic division is based on Horner Scheme.

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) on division by x − 3. The remainder is 5. This makes Horner’s method useful for polynomial long division.

Divide  by :

 2 │   1    -6    11    -6
│         2    -8     6
└────────────────────────
1    -4     3     0

The quotient is .

Let  and . Divide  by  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