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
If we evaluate this naïvely, we end up doing multiply and additions. Even using the fast exponentiation algorithm, we still use multiplies. But we can, very easily, get down to .
Horner, while proposing a method to find a polynomial’s roots , wrote the polynomial
This form requires additions and multiplies.
What if some of the 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 , the Horner representation becomes
We could “compress” the zeroes away and write . That still asks for 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, can be rewritten as , or a variant of, which seemingly dispenses us of the “difficult” multiplication by . Unless your target CPU is much faster with multiplying with very small integers than with a general multiplication, that’s a pretty pointless optimization.
 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.