Evaluating polynomials

05/05/2020

Evaluating polynomials is not a thing I do very often. When I do, it’s for interpolation and splines; and traditionally those are done with relatively low degree polynomials—cubic at most. There are a few rather simple tricks you can use to evaluate them efficiently, and we’ll have a look at them.

Horner’s Method

25/10/2016

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)$.