Projects in Exact Computer Arithmetic

Professor Abbas Edalat

Last modified: Sat Jan 9 17:34:06 GMT 1999

Summary:

An efficient framework for exact computer arithmetic has recently been developed which completely overcomes the problem of round-off error in floating point computation. The framework is based on a novel representation of real numbers by linear fractional transformations. Continued fractions are used to express all elementary functions in this setting. Prototype implementations in Haskell, Miranda, C++ and Java are now available. The work has considerable scientific and commercial applications. A number of projects in this area are proposed. Students would need sufficient mathematical and programming skill.

The Problem:

The usual implementation of real numbers in today's computers as floating point numbers has the well-known deficiency that most numbers can only be represented up to some fixed accuracy. This means that even the basic arithmetic operations can not be performed exactly, leading to the ubiquitous round-off errors. In compound calculations, these errors propagate and accumulate, possibly leading to unpredictable and grossly inaccurate results. This is a serious problem in all disciplines where high accuracy calculations are required, e.g. science and engineering.

The Project:

We have developed a prototype system for exact real arithmetic using the framework of linear fractional transformations (lft's). Rational numbers are represented by column vectors with integer entries and real numbers are represented by potentially infinite sequences of lft's or 2 by 2 matrices with integer entries. Functions and operations are represented, using the theory of continued fractions, by 2-dimensional lft's with integer entries. This has been implemented in C++ and the functional language Caml and provides provably correct algorithms for all elementary functions made up from composition of basic arithmetic operations, algebraic and transcendental functions like exp and sin. The user specifies the desired precision and the system automatically delivers the result of the calculation with this accuracy. If necessary, intermediate calculations are performed with higher precision. In our current implementation, for example, the first two thousand decimal digits of pi is computed on a PC in a fraction of a second. We have also developed algorithms to find roots, fixpoints and integrals of elementary functions.

Current and Future Work:

In order to provide a serious alternative to floating point arithmetic, we aim to increase the efficiency of the package. We are now developing a compiler for real numbers which will significantly speed up the computation. We are also developing other applications such as efficient algorithms for root finding, integration of elementary functions and solution of differential equations. The package will then be implemented as a library in C++, Java and other languages. It will provide a data type "real" which can be used by any programmer replacing the floating point type "float" or "double". The ultimate goal of this project is to implement the system in hardware which will further increase the speed of computation. With this aim in mind, we are now examining the famous golden ratio as a base for exact arithmetic.

MSc Projects:

1. Exact real arithmetic for linear algebra.

2. Hardware implementation for basic arithmetic operations using the golden ratio.

Link to my homepage.

Mail to Abbas Edalat