    Next: Conversions between Representations Up: Analysis Previous: Analysis

# Theoretical Analysis

The theoretical analysis begins with the simple operations such as converting between representations and averaging streams, and moves onto more complex operations and sequences of them. Features of particular interest include:

The number of digits of the input streams required to generate a specified number of output digits.
Branching:
The number of stream operations required at each step of the algorithm. Some operations (eg. average) require an operation on the digits, the result of which is prefixed to the stream resulting from a single recursive call using the `cons' operation. Others (eg. multiplication) may make several stream operations for each digit generated.

Digit size:
In many of the operations using dyadic digits, there is the possibility of the size of the size of the representation of the digits swelling. It may interesting to compare similar work by Heckmann   which analyses the way the size required for the representation of reals using linear fractional transformations behaves during certain computations.

These points are of interest because they affect the performance of the algorithms and the amount of memory they require. An algorithm with high lookahead requires many input digits to generate output. If the input is a complex expression itself, computing even a a few extra digits of this input may affect performance.

The branching will also affect the performance. An algorithm which branches will slow down over time as the number of stream operations required accumulates. An algorithm with no branching will continue generating new digits at a fairly constant rate (with respect to rate at which input digits are generated).

Dyadic digit swell will affect performance because the time required for primitive digit operations will dramatically increase.    Next: Conversions between Representations Up: Analysis Previous: Analysis
Martin Escardo
5/11/2000