4.7 MANIPULATION OF POWER SERIES 513 The running
4.7 MANIPULATION OF POWER SERIES 513 The running time T(n) of this procedure satisfies T(2n) = 2T(n) + C(n), (26) where C(n) is the time to compute R(z), I@( z ), and g(z). The function C(n) is dominated by the time to compute V(U(z)) modulo z2n, and C(n) presumably grows faster than order nl+ ; therefore the solution r(n) to (26) will be of order C(n). For example, if C(n) = cn3 we have T(n) z $cn3; or if C(n) is O(nlogn)3/2 using fast composition, we have T(n) = O(nlogn)3/2. The procedure breaks down when W(0) = 1 and S(0) # 0, so we need to investigate when this can happen. It is easy to prove by induction on n that the solution of (22) by the Brent-Traub method entails consideration of exactly n subproblems, in which the coefficient of V(z) on the right-hand side takes the respective values W(z)(z/U(z))j for 0 5 j < n in some order. If W(0) = U1 and if U1 is not a root of unity, we therefore have W(0) = 1 only when j = 1; the procedure will fail in this case only if (22) has no solution for n = 2. The Schrijder function for U can therefore be found by solving (22) for n = 2, 4, 8, 16, . . , with W(z) = U 1 and S(z) = 0, whenever VI is nonzero and not a root of unity. If Ul = 1, there is no Schrader function unless U(z) = z. But Brent and Traub have found a fast way to compute P(z) even when Ul = 1, by making use of a function V(z) such that V(U(z)) = U (z)V(z). (27) If two functions U(z) and o(z) both satisfy (27), for the same V, it is easy to check that their composition U(o(z)) does too; therefore all iterates of U(z) are solutions of (27). Suppose that U(z) = z + Uk zk + Uk+lzk+l + ... where k 2 2 and uk # 0. Then it can be shown that there is a unique power series of the form V(z) = zk + Vk+lzk+ + Vk+2zk+2 +. . . satisfying (27). Conversely if such a function V(z) is given, and if k 2 2 and uk are given, then there is a unique power series of the form U(z) = z + uk zk + uk+lz + +. . . satisfying (27); the desired iterate P(Z) is the unique power series P(z) satisfying V(P(z)) = P (z)V(z) (28) such that P(z) = z + nukzk + ... . Both V(z) and P(z) can be found by appropriate algorithms (see exercise 14). If UI is a kth root of unity, but not equal to 1, the same method can be applied to the function Uk(z) = z + ... , and Uk(z) can be found from U(z) by doing l(k) composition operations (cf. Section 4.6.3). We can also handle the case VI = 0: If U(z) = Ukzk + Uk+lzk+ + ... where k > 2 and uk # 0, the idea is to find a solution to the equation V(U(z)) = ukV(qk; then Un(z) = ~-1(u)ck -W(k-1) V(Z)~ ). Finally, if U(z) = UO + UIZ + … where UO # 0, let cr be a fixed point such that U(a) = e, and let o(z) = U(a + z) -a = zU (a) + zV ((Y)/2! + . . . ; then P(Z) = Un(z -0) + a. Further det#ails can be found in Brent, and Traub s paper [SIAM J. Computing 9 (1980), 54-661.
From our experience, we are can tell you that you can find a reliable and cheap webhost service at Java Web Hosting services.