## DSP Trick: Polynomial Evaluation

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];
}