Horner's Rule

A polynomial is typically written as

$f(x)=\sum_{k=0}^{n} a_k x^k$

or, term by term, as

$f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n,$

where the real numbers $a_0, a_1, \dots, a_n$ are the coefficients of the polynomial and $x$ is the variable.

If ${a_n\ne 0},$ the polynomial is said to be of degree $n$ (in symbols, ${\deg f(x)=n}$); $n$ is the highest exponent of the variable.

How Horner's rule works

Horner's rule (also called Horner's method) is an algorithm that simplifies the evaluation of a polynomial $f(x)$ at a given value ${x=x_0}.$ The polynomial is rewritten as a chain of nested first-degree expressions. Each of them takes at most one multiplication and one addition, and the result of each step is used in the next one. The same procedure divides the polynomial by ${x-x_0},$ which is why it is also known as synthetic division.

To explain this, let us write the value of the polynomial at $x_0$ in its expanded form:

$f(x_0)=a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n$

Factoring out $x_0$ again and again, we can also write it as

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+\dots+{x_0(a_{n-1}+a_nx_0)\dots)))}$

The algorithm evaluates the expressions in parentheses one by one, starting from the innermost pair and moving outwards.

It is carried out in the following steps:

1. Set ${k=n}.$
2. Let ${b_k=a_k}.$
3. Let ${b_{k-1}=a_{k-1}+x_0b_k}.$
4. Decrease $k$ by $1.$
5. If ${k\ge 1},$ go back to step 3; otherwise stop.

The last number found is the value of the polynomial: ${b_0=f(x_0)}.$

For example, take a polynomial of degree 5:

$f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5$

It is evaluated at ${x=x_0}$ by rearranging it as

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+{x_0(a_4+a_5x_0))))}$

The steps of the algorithm can be written in a table:

$k$	$b_k$
$5$	${b_5=a_5}$
$4$	${b_4=a_4+x_0b_5}$
$3$	${b_3=a_3+x_0b_4}$
$2$	${b_2=a_2+x_0b_3}$
$1$	${b_1=a_1+x_0b_2}$
$0$	${b_0=a_0+x_0b_1}$

Example. Evaluate the polynomial ${f(x)=x^4+3x^3+5x^2+7x+9}$ at ${x=2}.$

Solution. Since the polynomial is of degree 4, ${n=4}.$ Here ${x_0=2},$ and the coefficients are ${a_4=1},$ ${a_3=3},$ ${a_2=5},$ ${a_1=7}$ and ${a_0=9}.$

$k$	Step	Result
$4$	${b_4=1}$	$1$
$3$	${b_3=3+2\cdot 1}$	$5$
$2$	${b_2=5+2\cdot 5}$	$15$
$1$	${b_1=7+2\cdot 15}$	$37$
$0$	${b_0=9+2\cdot 37}$	$83$

Therefore, ${f(2)=83}.$

Horner's scheme

In practice only the numbers are written down, in a three-row table called Horner's scheme. The first row holds the coefficients of the polynomial, the number $x_0$ is written on the left, and the third row is filled in from left to right:

$\begin{array}{c|cccc|c} & a_n & a_{n-1} & \cdots & a_1 & a_0 \\ x_0 & & x_0b_n & \cdots & x_0b_2 & x_0b_1 \\ \hline & b_n & b_{n-1} & \cdots & b_1 & b_0\end{array}$

1. Write the coefficients in the first row in order of decreasing powers of $x.$ If a power is missing, write $0$ in its place.
2. Bring the first coefficient down into the third row: ${b_n=a_n}.$
3. Multiply the number you have just written by $x_0$ and put the product in the second row of the next column.
4. Add the two numbers in that column and write the sum under them, in the third row.
5. Repeat steps 3 and 4 until the last column is filled in.

For the polynomial ${x^4+3x^3+5x^2+7x+9}$ and ${x_0=2}$ from the example above, the scheme looks like this:

$\begin{array}{r|rrrr|r} & 1 & 3 & 5 & 7 & 9 \\ 2 & & 2 & 10 & 30 & 74 \\ \hline & 1 & 5 & 15 & 37 & 83\end{array}$

The last number in the third row is the value of the polynomial: ${f(2)=83}.$

Division by a linear binomial (synthetic division)

The third row of the scheme gives more than just the value $f(x_0).$

To check this, multiply out the right-hand side. The coefficient of $x^n$ is ${b_n=a_n},$ and the coefficient of every lower power $x^k$ is ${b_k-x_0b_{k+1}},$ which equals $a_k$ because ${b_k=a_k+x_0b_{k+1}}.$

Substituting ${x=x_0}$ into this identity gives ${f(x_0)=b_0}$ once more. This is the remainder theorem: the remainder when a polynomial $f(x)$ is divided by ${x-x_0}$ is equal to $f(x_0).$

In the example above the third row is $1,$ $5,$ $15,$ $37$ and $83,$ so the quotient is ${x^3+5x^2+15x+37}$ and the remainder is $83$:

${x^4+3x^3+5x^2+7x+9}={(x-2)(x^3+5x^2+15x+37)}+83$

Example. Divide ${f(x)=2x^4-3x^2+5x-7}$ by ${x+2}.$

Solution. Since ${x+2=x-(-2)},$ we have ${x_0=-2}.$ The polynomial has no $x^3$ term, so the coefficient of $x^3$ is $0,$ and the first row is $2,$ $0,$ $-3,$ $5,$ $-7.$

$\begin{array}{r|rrrr|r} & 2 & 0 & -3 & 5 & -7 \\ -2 & & -4 & 8 & -10 & 10 \\ \hline & 2 & -4 & 5 & -5 & 3\end{array}$

The quotient is ${2x^3-4x^2+5x-5}$ and the remainder is $3$:

${2x^4-3x^2+5x-7}={(x+2)(2x^3-4x^2+5x-5)}+3$

Check with the remainder theorem: ${f(-2)}={2\cdot 16-3\cdot 4+5\cdot(-2)-7}={32-12-10-7}={3}.$

Roots and factoring

If the remainder $b_0$ is $0,$ then ${f(x_0)=0},$ that is, $x_0$ is a root of the polynomial, and the polynomial is divisible by ${x-x_0}$ (the factor theorem):

$f(x)=(x-x_0)\,q(x)$

This makes Horner's scheme a handy tool for factoring. If a polynomial with integer coefficients has an integer root, that root is a divisor of the constant term $a_0.$ So we try the divisors of $a_0$ one after another, and each time Horner's scheme shows whether the number is a root and gives the quotient at once. If the last number in the third row is not $0,$ the number is not a root, and we try the next divisor.

Example. Factor the polynomial ${x^3-6x^2+11x-6}.$

Solution. The divisors of the constant term are $\pm 1,$ $\pm 2,$ $\pm 3$ and $\pm 6.$ We start with ${x_0=1}$:

$\begin{array}{r|rrr|r} & 1 & -6 & 11 & -6 \\ 1 & & 1 & -5 & 6 \\ \hline & 1 & -5 & 6 & 0\end{array}$

The remainder is $0,$ so $1$ is a root and ${x^3-6x^2+11x-6}={(x-1)(x^2-5x+6)}.$ We continue with the quotient ${x^2-5x+6}$ and ${x_0=2}$:

$\begin{array}{r|rr|r} & 1 & -5 & 6 \\ 2 & & 2 & -6 \\ \hline & 1 & -3 & 0\end{array}$

The remainder is $0$ again, so ${x^2-5x+6}={(x-2)(x-3)}.$ Therefore

${x^3-6x^2+11x-6}={(x-1)(x-2)(x-3)}$

Rational roots are found in the same way: if a fraction $\frac{p}{q}$ in lowest terms is a root of a polynomial with integer coefficients, then $p$ divides $a_0$ and $q$ divides the leading coefficient $a_n.$

Divisors of the form mx + n

Horner's scheme can also be used to divide by any first-degree polynomial ${mx+n}.$ Its root is ${x_0=-\frac{n}{m}},$ and ${mx+n=m(x-x_0)},$ so

$f(x)={(x-x_0)\,q(x)+b_0}={(mx+n)\cdot\frac{q(x)}{m}+b_0}$

We fill in the scheme for $x_0$ and then divide the coefficients of the quotient by $m.$ The remainder stays the same.

Example. Divide ${3x^3-5x^2+2x+3}$ by ${2x-1}.$

Solution. The root of the divisor is ${x_0=\frac12}.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 3 & -5 & 2 & 3 \\ \dfrac12 & & \dfrac32 & -\dfrac74 & \dfrac18 \\ \hline & 3 & -\dfrac72 & \dfrac14 & \dfrac{25}{8}\end{array}$

Division by ${x-\frac12}$ gives the quotient ${3x^2-\frac72x+\frac14}$ and the remainder $\frac{25}{8}.$ We divide the coefficients of the quotient by $2$:

${3x^3-5x^2+2x+3}={(2x-1)\left(\frac32x^2-\frac74x+\frac18\right)}+\frac{25}{8}$

When the divisor is of the second degree or higher, use polynomial long division.

Why use Horner's rule?

Normally, when we evaluate a polynomial at a given value, we substitute this value into the polynomial and do the arithmetic. We can also use or write a computer program to do that, which becomes a necessity when we are dealing with complicated polynomials of high degree.

The way a computer handles a problem depends mainly on how you, as the programmer, describe it to the computer. You may design your program to evaluate the polynomial by direct substitution or by Horner's rule. Both approaches give the same value; they differ in how fast the computer gets it.

The advantage of Horner's rule is that it reduces the number of multiplications. With direct substitution, if every power is computed from scratch, the term $a_kx^k$ takes $k$ multiplications, so a polynomial of degree $n$ needs ${1+2+\dots+n}={\frac{n(n+1)}{2}}$ multiplications. Horner's rule needs only $n$ multiplications and $n$ additions. For a polynomial of degree 10 that is $10$ multiplications instead of $55.$ Both methods use $n$ additions, so the whole saving is in the multiplications, and for polynomials of high degree a program that uses Horner's rule runs noticeably faster.

Practice problems

Solve the problems with Horner's scheme, then open the solutions. You can also check each step with the calculator above.

1. Find $f(3)$ for the polynomial ${f(x)=2x^3-5x^2+x-7}.$

$\begin{array}{r|rrr|r} & 2 & -5 & 1 & -7 \\ 3 & & 6 & 3 & 12 \\ \hline & 2 & 1 & 4 & 5\end{array}$

${f(3)=5}.$

2. Divide ${x^4-2x^3+4x-5}$ by ${x-1}.$

There is no $x^2$ term, so the first row is $1,$ $-2,$ $0,$ $4,$ $-5.$

$\begin{array}{r|rrrr|r} & 1 & -2 & 0 & 4 & -5 \\ 1 & & 1 & -1 & -1 & 3 \\ \hline & 1 & -1 & -1 & 3 & -2\end{array}$

The quotient is ${x^3-x^2-x+3}$ and the remainder is $-2.$

3. Find the remainder when ${f(x)=x^5-3x^2+2}$ is divided by ${x+1}.$

Here ${x_0=-1},$ and the first row is $1,$ $0,$ $0,$ $-3,$ $0,$ $2.$

$\begin{array}{r|rrrrr|r} & 1 & 0 & 0 & -3 & 0 & 2 \\ -1 & & -1 & 1 & -1 & 4 & -4 \\ \hline & 1 & -1 & 1 & -4 & 4 & -2\end{array}$

The remainder is $-2.$ Check: ${f(-1)}={-1-3+2}={-2}.$

4. Show that $-2$ is a root of ${3x^3+7x^2-4}$ and factor the polynomial.

There is no $x$ term, so the first row is $3,$ $7,$ $0,$ $-4.$

$\begin{array}{r|rrr|r} & 3 & 7 & 0 & -4 \\ -2 & & -6 & -2 & 4 \\ \hline & 3 & 1 & -2 & 0\end{array}$

The remainder is $0,$ so $-2$ is a root and ${3x^3+7x^2-4}={(x+2)(3x^2+x-2)}.$ The roots of ${3x^2+x-2}$ are $-1$ and $\frac23,$ so ${3x^3+7x^2-4}={(x+2)(x+1)(3x-2)}.$

5. Divide ${4x^3-3x+5}$ by ${2x+1}.$

Here ${x_0=-\frac12},$ and the first row is $4,$ $0,$ $-3,$ $5.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 4 & 0 & -3 & 5 \\ -\dfrac12 & & -2 & 1 & 1 \\ \hline & 4 & -2 & -2 & 6\end{array}$

Division by ${x+\frac12}$ gives the quotient ${4x^2-2x-2}$ and the remainder $6.$ Dividing the coefficients of the quotient by $2,$ we get ${4x^3-3x+5}={(2x+1)(2x^2-x-1)}+6.$