4.6.4 EVALUATION OF POLYNOMIALS 471 Adaptation of coefficients.
4.6.4 EVALUATION OF POLYNOMIALS 471 Adaptation of coefficients. Let us now return to our original problem of eval- uating a given polynomial U(Z) as rapidly as possible, for random values of 2. The importance of this problem is due partly to the fact that standard functions such as sinx, cos Z, eZ, etc., are usually computed by subroutines that rel.y on the evaluation of certain polynomials; such polynomials are evaluated so often, it is desirable to find the fastest possible way to do the computation. Arbitrary polynomials of degree five and higher can be evaluated with fewer operations than Horner s rule ,requires, if we first adapt or precondition the coefficients ~0, ~1, . . . , u,. This adaptation process might involve a lot of work, as explained below; but the preliminary calculation is not wasted, since it must be done only once while the polynomial will be evaluated many times. For examples of adapted polynomials for standard functions, see V. I^a. Pan, USSR Computational Math. and Math. Physics 2 (1963), 137-146. The simplest case for which adaptation of coefficients is helpful occurs for a fourth degree polynomial: u(x) = %$x4 + z&x3 + u2×2 + UlX + uo, u4 # 0. (8) This equation can be rewritten in a form originally suggested by T. S. Motzkin, Y = (x + ao)x + al, u(x) = ((Y + x + Q2)Y + &3)&4, (9) for suitably adapted coefficients a~, (~1, ax, as, ~4. The computation in (9) involves three multiplications, five additions, and (on a one-accumulator machine like MIX) one instruction to store the partial result y into temporary storage. By comparison with Horner s rule, we have traded a multiplication for an addition and a possible storage command. Even this comparatively small savings is worthwhile if the polynomial is to be evaluated often. (Of course, if the time for multiplication is comparable to the time for addition, (9) gives no improvement; we will see that a general fourth-degree polynomial always requires at least eight arithmetic operations for its evaluation.) By equating coefficients in (8) and (9), we obtain formulas for computing the aj s in terms of the Q S: Qo= 4@3/9J4 -l), P = u2/u4 -~O(~O + I), Ql = w/u4 -aoPt et2 =p-2cq, a3 = uo/u4 -Ql(Q + Q2), a4 = u4. (10) A similar scheme, which evaluates a fourth-degree polynomial in the same num- ber of steps as (9), appears in exercise 18; this alternative method will give greater numerical accuracy than (9) in certain cases, although it yields poorer accuracy in others. Polynomials that arise in practice often have a rather small leading coeffi- cient, so that the division by 214 in (10) leads to instability. In such a case it is usually preferable to replace x by Iu4 11j4 x as the first step, reducing (8) to a polynomial whose leading coefficient is f 1. A similar transformation applies to
Note: If you are looking for high quality webhost to host and run your jsp application check Vision christian web host services