Horner's Rule for Polynomial Computation

Suppose I had a polynomial a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀, and a point x^* at which I wanted to evaluate that polynomial.

Now our immediate inclination is to just substitute the point straight into the polynomial to get a_n(x^*)ⁿ + a_n-1(x^*)^n-1 + … + a₁(x^*) + a₀  and then work it through in the obvious way: we raise x^* to the nth power and multiply by a_n, then we raise x^* to the (n-1)th power and multiply by a_n-1, and so on, adding them all together at the end.

That seems like a lot of work though. We could be more efficient by working it the other way around: that is, starting with x^* and caching the intermediate powers of x^* as we work our way up. That would definitely cut down on some of the multiplications. But is there actually an even better way to do this polynomial evaluation?

As it turns out, there is – we can use Horner's Rule!

Not only is Horner's Rule more efficient than either of the above approaches, it is actually an optimal algorithm for polynomial computation: that is, we can prove mathematically that any other rule for polynomial computation can do no better than Horner's Rule.

So let's investigate how this rule works, and write up some Java code to test it out!

[We're back with the SICP exercise blog posts! This one is inspired by Exercise 2.34.]

Polynomial Computation – The Obvious Way

For the purposes of comparison, let's quickly review the ways that we would have otherwise calculated a polynomial. We'll start with the most obvious way:

Here we use result as a variable to hold the intermediate answers each time. By the end, the number in result will be the value of the polynomial at that point.

So for example, let's say we had the polynomial 5x⁴ + 2x³ – 3x² + x – 7, and we wanted the value of the polynomial at the point x=3. We'd work it through like this:

I've written it in a more "math-like" form here, but notice that we're essentially working through the above set of steps. We compute each of the terms (and each of the powers of x=3) separately, and add them up as we go across.

We could easily write some Java code to do this, right?


We have a class Polynomial1 with a method computePolynomial() that takes in a polynomial (represented here as an array of doubles, where the ith element of the array is the coefficient a_i of the polynomial), and a value x at which we are to evaluate the polynomial.

In the computePolynomial() method, we start from the nth term of the polynomial, and determine the value of that term. Then as we iterate in the for loop we work our way down, accumulating the terms in result.

So that we can compare each of the polynomial evaluation methods that we'll look at, we've also defined some static variables totalAdditions and totalMultiplications to keep track of those operations when the program runs. These get updated in the loop, and we'll display the values of those variables in the output at the end.

Running our little program on that polynomial example we had above, we get the following:

     java Polynomial1
     //> Polynomial: 5x^4 + 2x^3 - 3x^2 + x - 7
     //> x=3: 428.0
     //> Total additions: 5
     //> Total multiplications: 10

We got the right answer at least. But we're doing quite a few multiplications for such a small polynomial!

In general, computing an nth-degree polynomial this way means that we end up doing n additions and (0 + 1 + 2 + … + n) multiplications (since to get the a_ixⁱ term we multiply x by itself (i-1) times, and then multiply on the a_i coefficient to give us i multiplications for that step.)

This can be seen in the number of additions and multiplications we had for both the worked solution, and our program output (we've got an extra addition showing up in the program since we added the very first term to result, which is initially 0.0. We could always rewrite the program to make that first addition an assignment instead if we wanted.)

So we can summarise the efficiency of this polynomial computation scheme as follows:

We can easily see here that the number of multiplications is going to grow quadratically as the degree of the polynomial increases. We can do better than this though, of course.

Polynomial Computation – Caching Powers of x

As we mentioned earlier, we can already improve the efficiency of the computation by noticing that we're calculating many of the same powers of x for each term.

Consider that example with the polynomial 5x⁴ + 2x³ – 3x² + x – 7. Here we end up calculating x² three separate times, since we would have calculated x² as we were calculating both x³ and x⁴!

So one way to get an improvement is to cache those intermediate powers of x. Instead of starting with the a_nxⁿ term and working our way down, we'll start from the other end of the polynomial and work our way up – this means that we'll have the previous powers of x on hand that we can use to calculate the higher-order terms.

Our new set of steps looks like this:

So you can see that we keep x² around so we can use it to get x³, which we keep around to help us get x⁴, and so on. If we went through our example by hand using this method, we would get the following working:

And of course, this easily translates into another small program that we can use to compute polynomials:


This Polynomial2 class is very similar to the class we had before, and our computePolynomial() method takes the same input and returns the same output. But instead of starting at the a_nxⁿ term and working our way down the polynomial, this time around we start at the a₀ term (which we can make an assignment), and work our way up.

We also use the variable powerOfX to keep the previous x term around, so that we can use it to compute the next term of the polynomial. This should work to reduce the number of multiplications that we end up doing.

When we run the code, the output is as follows:

     java Polynomial2
     //> Polynomial: 5x^4 + 2x^3 - 3x^2 + x - 7
     //> x=3: 428.0
     //> Total additions: 4
     //> Total multiplications: 8

So we've managed to reduce the number of multiplications with this new method! And since we assigned the a₀ coefficient instead of adding it to 0, we've only had 4 additions this time too.

Computing an nth-degree polynomial this way will always take n additions and 

2 + 2 + … + 2 = 2n multiplications:

This is better – at least the number of multiplications we need to do now grows linearly with the degree of the polynomial.

Horner's Rule

We can reduce the number of multiplications even further. Consider that we can always rewrite a polynomial in the following equivalent way:

This is the main idea of Horner's Rule, which is named after the mathematician William George Horner.

Basically, we start with the a_n coefficient, multiply it by x and add on the a_n-1 coefficient. Then we multiply that whole result by x and add on the a_n-2 coefficient. Then we multiply everything by x again, and add on the a_n-3 coefficient, and so on for the rest of the polynomial terms.

You can see that by working through it that way, we should get the right powers of x coming out:  a_n ends up multiplied with x n times, a_n-1 ends up multiplied by x n-1 times, and similarly right down to the a₁ term, which is multiplied by x once.

The computation algorithm captures this process exactly:

And that's the entire algorithm! (It even looks prettier than the other algorithms we had above.)

As an example, if we were to work through our polynomial example by hand, we'd do the following:

And this algorithm is easy enough to translate into working Java code, too.


As you can see, in our computePolynomial() method we assign the a_n coefficient to result to start with, and then for each iteration of the loop, we multiply the current value of result by x and add on the next coefficient.

Running the code gives us the following output for our example:

     java HornersRule
     //> Polynomial: 5x^4 + 2x^3 - 3x^2 + x - 7
     //> x=3: 428.0
     //> Total additions: 4
     //> Total multiplications: 4

So we've now got 4 additions and 4 multiplications, which is nice!

As the final point of this blog post, we can notice that computing an nth-degree polynomial with Horner's Rule will always take only n additions and multiplications:

And in fact, this is the best we can do. The mathematician Alexander Ostrowski proved in 1954 that Horner's Rule uses the optimal number of additions, and another mathematician Victor Pan proved in 1966 that Horner's Rule uses the optimal number of multiplications. So Horner's Rule is an optimal algorithm for polynomial computation!