Reinhold Heckmann

Abstract

One possible approach to exact real arithmetic
is to use linear fractional transformations
to represent real numbers and computations on real numbers.
We show how to determine the digits that
can be emitted from a transformation,
and present a criterion which ensures that it is possible to emit a digit.
Using these results, we prove that the obvious algorithm
to compute *n* digits from the application of a transformation to a real number
has complexity *O*(*n*^{2}),
and present a method to reduce this complexity
to that of multiplying two *n* bit integers.

[Paper.ps.gz (20p, 82k)]