Efficient polynomial evaluation

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!

Anuncis
Aquesta entrada ha esta publicada en Algorithms, Math, Programming. Afegeix a les adreces d'interès l'enllaç permanent.

3 respostes a Efficient polynomial evaluation

  1. Selma ha dit:

    Nice post and nice weblog!

    In fact, it was a physicist coworker of mine who reminded me of Horner’s.

    Keep up the good work 😉

  2. Waldeck ha dit:

    10 times faster? Not exactly.

    While your old algorithm is of complexity O(n^2), where n is the degree, the Horner’s method is just O(n). Hence for the same degree, your old code would run about n times *slower* then the new one. If the degree is 10, then it is correct to say the new code will run in about 1/10th of the time.

    Depending on your polynomials and how they are evaluated, there could
    be even better approaches.

    Now you might have been talking about overall system performance in which case it would be difficult to figure out the correct gains without knowing the system particulars.

    In any case, enjoy the performance! 😉

    • Anònim ha dit:

      The evaluation of pow(x,i) in C/C++ costs something close to 100-200 multiplications, as opposed to the assumption of (i-1) multiplications in Waldeck’s analysis above.

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s