4th year project

Departments of Computer Science and Artificial Intelligence

University of Edinburgh

**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.

- Acknowledgements
- Contents
- Introduction
- Real Number Computation
- Representations
- Basic Operations
- High-Level Operations
- Design and Implementation
- Analysis
- Conclusion
- Dyadic Digit Operations
- Algorithms
- Expression Language
- References
- About this document ...