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.