DSP Tricks: Efficient Polynomial Evaluation - Embedded.com

DSP Tricks: Efficient Polynomial Evaluation


On the off chance that you didn't know, to speed up polynomialevaluations (computations) in software it's smart to use what's knownas Horner's rule. An example of polynomial evaluationis, say, using the following expression to compute the arctangent of x:

To see how the computational workload of polynomial evaluations canbe reduced, consider the following kth-order polynomial:

It can be rewritten as:

where the H subscript means Horner. Using this method to computepolynomials:

1) reduces the number ofnecessary multiply operations, and

2) is straightforward toimplement using programmable DSP chips with their multiply and accumulate (MAC) architectures.

For example, consider the fifth-order polynomial:

Evaluated in the standard way, Eq.(13″128) would require ninemultiplies and five additions, whereas the Horner version

requires only five multiplies and five adds when the computationsbegin with the innermost multiply and add operations (c5 x + c4 ).

Here are a few examples of polynomials in the Horner format:

By the way, the multiplications and additions cannot be performed inparallel. Because Horner's rule is inherently serial, we need theresult of the last multiplication before we can start the nextaddition, and that addition result is needed before the follow-onmultiplication.

Horner's rule is another of those handy computer techniques we usewhose origins are very old. Chinesemathematicians described it in the 1200s. European mathematicians(including William Horner) rediscovered and publicized it in the early1800s. It seems Sir Isaac Newton also inventedand used it in the 1600s.

Usedwith the permission of the publisher, Prentice Hall, this on-goingseries of articles on Embedded.com is based on copyrighted materialfrom “UnderstandingDigital Signal Processing, Second Edition” by Richard G. Lyons. Thebook can be purchased on line.

Richard Lyons is a consultingsystems engineer and lecturer with Besser Associates. As alecturer with Besser and an instructor for the University of CaliforniaSanta Cruz Extension, Lyons has delivered digitasl signal processingseminars and training course at technical conferences as well atcompanies such as Motorola, Freescale, Lockheed Martin, TexasInstruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm,Honeywell, National Semiconductor, General Dynamics and Infinion.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.