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