next up previous contents
Next: Work Performed Up: A Calculator for Exact Previous: Contents

Introduction

  In this work we have developed a calculator for exact real arithmetic. In addition we have experimented with and analysed the representations and algorithms required to do so. The calculator includes the basic arithmetic operations, a number of transcendental functions, integration and function minimum and maximum. These are accessed through a simple text prompt user interface.

Many applications of computers require the use of real arithmetic. Unfortunately, there are a number of significant problems associated with performing real arithmetic using floating point approximation, the method most commonly used by programmers, and which forms part of most computer languages and the instruction set of many modern CPUs. These problems stem from the fact that only a finite set of reals are represented exactly using this approach, and rounding occurs after each floating point operation. They can result in complete loss of accuracy in even relatively simple computations.

There are a number of alternative approaches to real arithmetic on a computer, including floating point arithmetic with error analysis, interval arithmetic, a stochastic rounding technique, and the symbolic manipulation of expressions as performed by computer algebra systems. Each of these approaches has advantages and disadvantages.

Exact real arithmetic is a method of performing arithmetic operations to arbitrary precision and obtaining results which are guaranteed correct. It relies on the use of finite sized representations of infinite objects to represent numbers. A finite portion of this infinite object may be evaluated explicitly to return a result with the required precision to the user, but the object itself still expresses the number exactly.

There are a number of possible representations one might use for exact real arithmetic. The representations used in this project are based on familiar digit representations (eg. binary, decimal), and include the use of signed binary digits, and the use of dyadic rationals as `pseudo-digits'.

The techniques used to develop algorithms for the arithmetic and other operations on these representations include range analysis, exploiting the relationship between list operations and mathematical ones that exist when we use these representations, and the use of identities to re-express numerals.

There are numerous potential applications of an exact real arithmetic package, although the performance and memory constraints are likely to make this approach impractical for `everyday' real arithmetic. These potential applications might include:

Unfortunately at the present time the theory behind exact real arithmetic, especially regarding tractability, is not sufficiently advanced to seriously discuss the potential applications of a such a package in more than abstract terms. See Ko [18] for further discussion of these issues.

Developing a calculator for exact real arithmetic is interesting because it involves both finding representations and developing algorithms real number computation, and also implementing these representations and operations. The end product demonstrates that this approach can actually be used in a real application, albeit a simple one.

The definition of a ``calculator for exact real arithmetic'' is an extremely open-ended one. At the very least one would expect the basic arithmetic operations and a simple user interface. However such a calculator might also include an extensive library of transcendental functions or functional operations, or have an elaborate user interface and expression/programming language. We have taken a middle road, implementing a reasonable selection of transcendental functions and some functional operations, and including simple variables and variable precision output in the expression language of the user interface. In addition to this implementation, we have then spent time analysing the algorithms we have developed and experimenting with the implementation.



 
next up previous contents
Next: Work Performed Up: A Calculator for Exact Previous: Contents
Martin Escardo
5/11/2000