# Accession Number:

## ADA058743

# Title:

## On the Complexity of Composition and Generalized Composition of Power Series.

# Descriptive Note:

## Interim rept.,

# Corporate Author:

## CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1978-05-01

# Pagination or Media Count:

## 36.0

# Abstract:

Let Fx f1x f2xx ... be a formal power series over a field Delta. Let F superscript 0x x and for q 1,2,..., define F superscript qx F superscript q-1 Fx. The obvious algorithm for computing the first n terms of F superscript qx is by the composition position analogue of repeated squaring. This algorithm has complexity about log 2 q times that of a single composition. The factor log 2 q can be eliminated in the computation of the first n terms of Fx to the q power by a change of representation, using the logarithm and exponential functions. We show the factor log 2 q can also be eliminated for the composition problem. F superscript qx 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 superscript qx whenever it is defined.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics