Horner’s Method

It’s not like evaluating polynomial is something that comes up that frequently in the average programmer’s day. In fact, almost never, but it brings up a number of interesting questions, such as, how do we evaluate it very efficiently and how much of a simplification in the computation is actually a simplification?

The generic polynomial has the form

a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n.

If we evaluate this naïvely, we end up doing O(n^2) multiply and O(n) additions. Even using the fast exponentiation algorithm, we still use O(n \lg n) multiplies. But we can, very easily, get down to O(n).

Horner, while proposing a method to find a polynomial’s roots [1], wrote the polynomial

a_0 a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n

as

a_0+x(a_1+x(a_2+x(\cdots(a_{n-1}+a_nx)\cdots))).

This form requires n-1 additions and n multiplies.

*
* *

What if some of the a_i are zeroes? How does the Horner representation deal with this? It doesn’t, because it doesn’t really have to. For a polynomial such as a_0+a_3x^3+a_4x^4, the Horner representation becomes

a_0+x(0+x(0+x(a_3+x(a_4)))).

We could “compress” the zeroes away and write a_0+x^3(a_3+x(a_4)). That still asks for O(n) multiplies and everybody’s happy.

*
* *

Should we do something more with the coefficients? Intuitively, and especially in a pen-and-paper mindset, we may think that further breaking down the coefficients to get “small multiplies” is a good idea. For example, 5x^2+15x^3 can be rewritten as 5x^2(1+3x), or a variant of, which seemingly dispenses us of the “difficult” multiplication by 15. Unless your target CPU is much faster with multiplying with very small integers than with a general multiplication, that’s a pretty pointless optimization.


[1] W. G. Horner — A New Method of Solving Numerical Equations of All Orders, by Continuous Approximation — Philosophical Transactions of the Royal Society of London, vol. 109 (1819) p. 308–335.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: