4.6.4 EVALUATION OF POLYNOMIALS 467 a demonstration that (Remote web server)
4.6.4 EVALUATION OF POLYNOMIALS 467 a demonstration that certain kinds of numerical stability cannot be guaranteed for some families of high-speed algorithms.] A beginning programmer will often evaluate the polynomial (1) in a manner corresponding directly to its conventional textbook form: First u,xn, is calcu- lated, then u,-lxn- , . . . , ulx, and finally all of the terms of (1) are added together. But even if the efficient methods of Section 4.6.3 are used to evaluate powers of x in this approach, the resulting calculation is needlessly slow unless nearly all of the coefficients uk are zero. If the coefficients are all nonzero, an obvious alternative would be to evaluate (1) from right to left,, computing the values of xk and Ukxk+. . .+UO for k = 1, . . . , n. Such a process involves 2n-1 multiplications and n additions, and it might also require further instructions to store and retrieve intermediate results from memory. Homer s rule. One of the first things a novice programmer is usually taught is an elegant way to rearrange this computation, by evaluating u(x) as follows: u(x) = ((. . . (21,x + u,-1)x + . . .)x + uo. (2) Start with un, multiply by x, add ~~-1, multiply by x, . . . , multiply by x, add ~0. This form of the computation is usually called Horner s rule ; we have already seen it used in connection with radix conversion in Section 4.4. The entire process requires n multiplications and n additions, minus one addition for each coefficient that is zero. Furthermore, there is no need to store partial results, since each quantity arising during the calculation is used immediately after it has been computed. W. G. Horner gave this rule early in the nineteenth century [Philosophical Transactions, Royal Society of London 109 (1819), 308-3351 in connection with a procedure for calculating polynomial roots. The fame of the latter method [see J. L. Coolidge, Mathematics of Great Amateurs (Oxford, 1949), Chapter 151 accounts for the fact that Horner s name has been attached to (2); but actually Isaac Newton had made use of the same idea 150 years earlier. In a well-known work entitled De Analysi per Bquationes Innfinitas, originally written in 1669, Newton wrote y–4xy:+5xy:-12xy:+17 for the polynomial y4 -4y3 + 5y2 -12y + 17; this clearly uses the idea of (a), since he often denoted grouping by using horizontal lines and colons instead of parentheses. [See D. T. Whiteside, ed., The Mathematical Paperrs of Isaac Newton 2 (Cambridge Univ. Press, 1968), 222.1 Several generalizations of Horner s rule have been suggested. Let us first consider evaluating U(Z) when z is a complex number, while the coefficients uk are real. In particular, when .z = eie = cos 0 + i sin 8, the polynomial u(z) is essentially two Fourier series, (U,+U1COSe+… + un cos no) + i(ul sin 19 + . . . + un sin no).