Evaluating polynomials - floating point or optimization issue?

Question

From Numerical Recipes:

We assume that you know enough never to evaluate a polynomial this way: p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x; ...

Obviously I don't know enough...

Is this only an optimization issue or is it also a floating point arithmetic issue and why?

Answer 1

You can compute p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x; as:

p=c[0]+(c[1]+(c[2]+(c[3]+c[4]*x)*x)*x)*x;

There are much fewer multiplications in the second form. This second form is called “Horner's”.

Is this only an optimization issue or is it also a floating point arithmetic issue and why?

It is mostly an optimization issue. However, some modern processors have a floating-point operation to do a multiplication and an addition in a single instruction without intermediate rounding for the multiplication, and while the benefit that most programmers see is still optimization, it also means that the result is more accurate.

Horner's form is very well-adapted for computation with this fused-multiply-add instruction.

---

Finally, I should point out for the sake of completeness that modern processors can be even more efficient if the polynomial is presented to them in a form with more parallelism. See for instance Estrin's scheme or this blog post for a down-to-earth explanation. Your book is not alluding to the requirement of knowing about Estrin's scheme. It is only alluding to the requirement of knowing about Horner's scheme.