How would you code a method to evaluate a n-th degree polynomial? I once needed to code this type of routine for a project I was working on. At that time I used to program fast FPU processors, so I never paid attention to performance. I went carelessly coding the straight forward approach:
void polynomial::eval(const vector<double>& coef, double x, double *res)
{
double res=0;
for (int i=0; i<coef.size(); i++)
res += coef[i] * pow(x, i);
return res;
}
The library ran smooth on our P-IV intel processor. It was used for a couple of years without problems. As time went by and product cost was pushed down, we sooner decided to move to a XScale intel processor. It was then when we noticed quite an impact on the performance (from 0.2 to 12 sec overhead). It turns out that my harmless function was called 9 million times! A mathematician friend of mine pointed me out to a more efficient algorithm: Horner’s scheme. I admire it for the elegance and simplicity of its solution: just a rewrite of the commonly used polynomial expression:
The new routine runs now 10 times faster!
