The Appearance of Big Integers in Exact Real Arithmetic based on Linear Fractional Transformations

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. In this paper, we show that the bit sizes of the (integer) parameters of nearly all transformations used in computations are proportional to the number of basic computational steps executed so far. Here, a basic step means consuming one digit of the argument(s) or producing one digit of the result.


[Paper.ps.gz (17p, 60k)]


Reinhold Heckmann / heckmann@absint.com