Next: Conversions between Representations
Up: Analysis
Previous: 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:
- Lookahead:
- 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 [15] [14] 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