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.