Free web hosts - 4.6.4 EVALUATION OF POLYNOMIALS 469 and u(-z), this
4.6.4 EVALUATION OF POLYNOMIALS 469 and u(-z), this approach yields u(–5) with just one more addition operation; two values can be obtained almost as cheaply as one. Moreover, if we have a computer that allows parallel computations, the two lines of (4) may be evaluated independently, so we save about half the running time. When our computer allows parallel computation on k arithmetic units at once, a /&h-order Horner s rule (obtained in a similar manner from f(z) = xk - x; ) may be used. Another attractive method for parallel computation has been suggested by G. Estrin [Proc. Western Joint Computing Conf. 17 (1960), 33-401; for n = 7, Estrin s method is: Processor 1 Processor 2 Processor 3 Processor 4 Processor 5 al = U7x + U6 bl = U5Z + U4 cl = U3x + U2 dl = UlZ + Z&o X2 u2 = u1×2 + bl c2 = c1×2 + dl X4 a3 =a2×4+c2 Here us = u(x). However, an interesting analysis by W. S. Dorn [IRM J. Res. and Devel. 6 (1962), 239-2451 shows that these methods might not actually be an improvement over the second-order rule, if each arithmetic unit must access a memory that communicates with only one processor at a time. Tabulating polynomial values. If we wish to evaluate an nth degree polynomial at many points in an arithmetic progression (i.e., if we want to calculate u(xo), 4×0 + h), u(xo + 2h), . * J, the process can be reduced to addition only, after the first few steps. For if we start with any sequence of numbers (Q,, (xl,. . . , a,) and apply the transformation ~o+~o+w, a1 +w+Qz, **a, an-1 + c&-l + Cb, (5) we find that k applications of (5) yields where ,0j denotes the initial value of aj and pj = 0 for j > n. In particular, is a polynomial of degree n in k. By properly choosing the p s, as shown in exercise 7, we can arrange things so that ar) is the desired value u(xg + kh), for all k. In other words, each execution of the n additions in (5) will produce the next value of the given polynomial. Caution: Rounding errors can accumulate after many repetitions of (5), and an error in Qj produces a corresponding error in the coefficients of x0, . . . , xj in the polynomial being computed. Therefore the values of the a s should be refreshed after a large number of iterations.
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision virtual web hosting services