# DSP Trick: Polynomial Evaluation via Horner's Rule

```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

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