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 kthorder polynomial:
Equation 13126
It can be rewritten as:
Equation 13127
where the H subscript means Horner. Using this method to compute polynomials:
For example, consider the fifthorder polynomial:
Equation 13128
Evaluated in the standard way, Eq. (13128) would require nine multiplies and five additions, whereas the Horner version
Equation 13129
requires only five multiplies and five adds when the computations begin with the innermost multiply and add operations (c5x + c4).
Here are a few examples of polynomials in the Horner format:
Equation 13130
Equation 13131
Equation 13132
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 followon 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.
URL http://proquest.safaribooksonline.com/0131089897/ch13lev1sec26
Amazon  


