4.7 MANIPULATION OF POWER SERIES 507 theory to
4.7 MANIPULATION OF POWER SERIES 507 theory to run the algorithm indefinitely and compute the entire power series; or to run it until a certain condition is met. (The opposite of on-line is off-line. ) If the coefficients uk and vk are integers but the wk are not, the recurrence relation (3) involves computation with fractions. This can be avoided by the all-integer approach described in exercise 2. Let us now consider the operation of computing W(z) = V(z) , where cr is an arbitrary power. For example, we could calculate the square root of V(z) by taking cr = f , or we could find V(z)-lo or even V(z) . If V, is the first nonzero coefficient of V(z), we have V(z) = hlzy1+ (Kn+1 lK& + Wm+2IV& + . . .)I (4 V(z) = v; zam (1+ wn+dK& + (Kn+2/Vm)Z2 +. . .) . This will be a power series if and only if crm is a nonnegative integer. From (4) we can see that the problem of computing general powers can be reduced to the case that VO = 1; then the problem is to find coefficients of W(z) = (1 + viz + vzzz + vszs +. . .)*. (5) Clearly WO = 1 = 1. The obvious way to find the coefficients of (5) is to use the binomial theorem (Eq. 1.2.9-19), or ( f1 cr is a positive integer) to try repeated squaring as in Section 4.6.3; but a much simpler and more efficient device for calculating powers has been suggested by J. C. P. Miller. [See P. Henrici, JACA4 3 (1956), 10-15.1 If W(z) = v(z)*, we have by differentiation WI + 2wzz + 3w32 +. . . = W (z) = av(z)- V (z); (6) therefore W (z)V(z) = aW(z)V (z). If we now equate the coefficients of zn- in (7), we find that c kWkV,-k = Cy c (TL-k)WkVn-k, (8) O