510 ARITHMETIC 4.7 Equation (16) explains the mechanism (Web hosting billing)
510 ARITHMETIC 4.7 Equation (16) explains the mechanism of this algorithm, which is due to Henry C. Thacher, Jr. [CACM 9 (1966), 10-111. The running time is essentially the same as Algorithm L, but considerably more storage space is required. An example of this algorithm is worked out in exercise 9. Still another approach to power series reversion has been proposed by R. P. Brent and H. T. Kung [JACM 25 (1978), 581-5951, based on the fact that stand- ard iterative procedures used to find roots of equations over the real numbers can also be applied to equations over power series. In particular, we can con- sider Newton s method for computing approximations to a real number t such that f(t) = 0, given a function f that is well-behaved near t: If z is a good approximation to t, then 4(z) = z - f(~)/f (~) will be even better, for if we write z = t + E we have f(x) = f(t) + ef (t) + O(e2), f (s) = f (t) + O(t); consequently 4(5) = t + t -(0 + ef (t) + O(?))/(f (t) + O(E)) = t + O(e2). Applying this idea to power series, let f(z) = V(s) -V(Z), where U and V are the power series in Eq. (14). We wish to find the power series t in z such that f(t) = 0. Let z = W1 z +. . . + W,-l zn- = t + O(F) be an approximation to t of order n; then @(z) = z - f(~)/f (z) will be an approximation of order 2n, since the assumptions of Newton s method hold for this f and t. In other words, we can use the following procedure: Algorithm N (General power series reversion by Newton s method). This semi- on-line algorithm inputs the values of U, and V, in (14) for 2k 5 n < 2k+1 and then outputs the values of W, in (15) for 2k 5 n < 2kf1, thereby producing its answers in batches of 2k at a time, for k = 0, 1, 2, . . . , K. Nl. [Initialize.] Set N c 1. (We will have N = ak.) Input the first coefficients VI and VI (where VI = l), and set WI e VI. N2. [Output.] Output W, for N 5 n < 2N. N3. [Input.] Set N e 2N. If N > 2K, the algorithm terminates; otherwise input the values U, and V, for N 5 n < 2N. N4. [Newtonian step.] Use an algorithm for power series composition (see exer- cise 11) to evaluate the coefficients Qj and Rj (0 < j < N) in the power series u,z+ + U2jl,-$2N-1 -v(wlz + -+wN-lzN- ) = RozN + RlzN+l + . . . + RN-1z2N- + O(Z~~), v (w,z + + wj,T-lz N-1) = Qo + QIZ + . . . + QN-~z~- + O(zN), where V(x) = 2 + V2s2 + . .. and V (x) = 1 + 2Vzz + . . . Then set WN, . . . . W2N–1 to the coefficients in the power series Ro+Rlz+. * .+RN-~z N-l = WN + + W&X-12 N-1 + O(ZN) Qo+Qlz+. . .+QN-Iz -~ and return to step N2. m