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

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

It can be rewritten as:

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

1) reduces the number of necessary multiply operations, and

2) is straightforward to implement 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 nine multiplies and five additions, whereas the Horner version

requires only five multiplies and five adds when the computations begin with the innermost multiply and add operations (c₅x + c₄).

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

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

Horner's rule is another of those handy computer techniques we use whose origins are very old. Chinese mathematicians described it in the 1200s. European mathematicians (including William Horner) rediscovered and publicized it in the early 1800s. It seems Sir Isaac Newton also invented and used it in the 1600s.

Used with the permission of the publisher, Prentice Hall, this on-going series of articles on Embedded.com is based on copyrighted material from "Understanding Digital Signal Processing, Second Edition" by Richard G. Lyons. The book can be purchased on line.

Richard Lyons is a consulting systems engineer and lecturer with Besser Associates. As a lecturer with Besser and an instructor for the University of California Santa Cruz Extension, Lyons has delivered digitasl signal processing seminars and training course at technical conferences as well at companies such as Motorola, Freescale, Lockheed Martin, Texas Instruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm, Honeywell, National Semiconductor, General Dynamics and Infinion.