Date: Tue, 20 Apr 1999 09:28:02 +0200 From: rainer storn <rainer.storn@hl.siemens.de> Newsgroups: comp.dsp Subject: Trick: Polynomial Evaluation (update) THIS WORK IS PLACED IN THE PUBLIC DOMAIN
Name: Polynomial Evaluation
Category: Algorithmic Trick
Application: e.g. Polynomial approximation of a transcendental function
Advantages: Simple and fast
Introduction: When evaluating a polynomial it is advantageous to use Horner’s rule as this nicely fits the MAC architectures of DSPs.
The Trick:
Suppose you want to compute a polynomial:
p(x)=p0 +p1*x + p2*x^2 + ... + pk*x^k (1)
Horner’s rule to compute this polynomial is given by:
p(x)=p0 + (p1 + (p2 + ...(pk)*x)*x)...)*x (2)
or in a little C-snippet
//----computes result=p(x) with p[j] = pj------ result = 0; for (i=k; i>0; i--) { result = (result + p[i])*x; } result = result + p[0];
another, even better possibility is:
//----computes result=p(x) with p[j] = pj------ result = p[k]; for (i=k-1; i>=0; i--) { result = result*x + p[i]; }