Abstract: dvi (3K), pdf (82K), ps (28K),
Paper: pdf (942K).
Let F(0)(x) = x and, for q = 1, 2, ..., define F(q)(x) = F(q-1)(F(x)). The obvious algorithm for computing the first n terms of F(q)(x) is by the composition analogue of repeated squaring. This algorithm has complexity about log2q times that of a single composition. Brent  showed that the factor log2q can be eliminated in the computation of the first n terms of the power (F(x))q by a change of representation, using the logarithm and exponential functions. We show here that the factor log2q can also be eliminated for the composition problem, unless the complexity of composition is quasi-linear.
F(q)(x) can often, but not always, be defined for more general q. We give algorithms and complexity bounds for computing the first n terms of F(q)(x) whenever it is defined.
The paper concludes with some open problems.
Page 63, line 13, in Algorithm 5.1,
"((-R" should be "(-R".
Page 63, line 21, in Algorithm 5.2, the German letter should be a "B".
Go to next publication
Return to Richard Brent's index page