Big Integers and Complexity Issues in Exact Real Arithmetic

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(n2), and present a method to reduce this complexity to that of multiplying two n bit integers.


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


Reinhold Heckmann / heckmann@absint.com