Andrej Bauer

Programming techniques for exact real arithmetic

Andrej Bauer
University of Ljubljana, Slovenia

There are several strategies for implementing exact computation with real numbers. Two common ones are based on interval arithmetic with forward or backward propagation of errors. A less common way of computing with exact reals is to use Dedekind's construction of reals as cuts. In such a setup a real number is defined by two predicates that describe its lower and upper bounds. We can extract efficient evaluation strategies from such declarative descriptions by using an interval Newton's method.

From the point of view of programming language design it is desirable to express the mathematical content of a computation in a direct and abstract way, while still retaining flexibility and control over evaluation strategy. We shall discuss how such a goal might be achieved using techniques that modern programming languages have to offer.