Dave Plume
Supervisors: Martín Escardó and Alex Simpson
Date: 1998
The most usual approach to real arithmetic on computers consists of using floating point approximations. Unfortunately, floating point arithmetic can sometimes produce wildly erroneous results. One alternative approach is to use exact real arithmetic. Exact real arithmetic allows exact real number computation to be performed without the roundoff errors characteristic of other methods. We observe that conventional representations such as binary are inadequate for this purpose, and consider two alternative representations of reals. Algorithms for the basic arithmetic operations, transcendental functions, integration, and function minimum and maximum are implemented. These include new algorithms for direct multiplication of signed binary streams, division, and the evaluation of limits of Cauchy sequences. A theoretical and experimental analysis of some of these algorithms is performed which shows that algorithms for the same operation using different representations behave differently. It also shows that even relatively simple expressions can require many digits of input to compute even a single digit of output and that one of the representations can exhibit a form of expression swell which destroys performance. The experimental work shows the performance of the implemented system to be poor on complex expressions, and we discuss why this might be so.
![$[-\infty, \infty]$](img187.gif){kind=small}