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.

Read the rest of this entry »


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

Read the rest of this entry »