Web site designers - 4.7 MANIPULATION OF POWER SERIES 511 The running
4.7 MANIPULATION OF POWER SERIES 511 The running time for this algorithm to obtain the coefficients up to iV = 2K is T(N), where T(2N) = T(N) + (time to do step N4) + O(N). (17) Straightforward algorithms for composition and division in step N4 will take order N3 steps, so Algorithm N will run slower than Algorithm T. However, Brent and Kung have found a way to do the required composition of power series with O(N log iV)3/2 arithmetic operations, and exercise 6 gives an even faster algorithm for division; hence (17) shows that power series reversion can be achieved by doing only O(Nlog N)3/2 operations as N + co. (On the other hand the constant of proportionality is such that N must be really large before Algorithms L and T lose out to this high-speed method.) Historical note: J. N. Bramhall and M. A. Chapple published the first O(n ) method for power series reversion in CACM 4 (1961), 317-318, 503. It was an off-line algorithm whose running time was approximately the same as that of Algorithms L and T. Iteration of series. If we want to study the behavior of an iterative process X, t f(~~-~), we are interested in studying the n-fold composition of a given function f with itself, namely 2, = f(f( . . . f(zo) . . . )). Let us define f (x) = x and f (z) = f(fnY1(,)), so that f +w = frn(Y(4) (18) for all integers m, 72 2 0. It also makes sense to define jn(,) wh& n is a negative integer, namely to let f and f- be inverse functions such that 2 = fn(fPn(,)); then (18) holds for all integers m and n. Reversion of series is essentially the operation of finding the inverse function f- (z); for example, Eqs. (10) and (11) essentially state that z = V(W(.z)) and that t = W(V(t)), so w = v-l. Suppose we are given two power series V(z) = z + V2z2 + . . . and W(Z) = z + w2.2 + … such that W = V-l. Let u be any nonzero constant, and consider the function U(z) = W(uV(z)). (19) It is easy to see that U(U@)) = W(u2V(z)), and in general that U (z) = W(u V(2)) (20) for all integers 72. Therefore we have a simple expression for the nth iterate Un, which can be calculated with roughly the same amount of work for all n. Furthermore, we can even use (20) to define U for non-integer values of n; the half iterate U1i2, for example, is a function such that U1/2(U1/2(~)) = U(Z). (There are two such functions U112, obtained by using fi and -fi as the value of u l .)