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.
In a recent blog entry, Jeff Atwood makes the case that “hardware is Cheap, Programmers are Expensive”, basically arguing that in a lot of cases, it’s cost-efficient to add cheap, faster, hardware to a performance problem rather than investing time to actually enhance the code at the algorithmic and implementation level.
I do, however, disagree with him on many points.