# 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

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

»

- Printer-friendly version
- Login to post comments