What is Exact Arithmetic?

David Lester

(University of Manchester)

In this talk I shall explain what I think exact arithmetic is; methods by which it might be efficiently implemented on a machine; and problems for which it might profitably be used. An exact arithmetic is one in which any answers generated may be relied upon to be correct. One way to view this is that any intermediate calculations will be performed to whatever accuracy is needed to ensure the accuracy of the answer. There is a connection here to the use of laziness in languages such as Haskell. Another way to view an exact arithmetic is that it is a realization of the Computable Reals. The methods that can be used to implement Exact Arithmetic on a machine can be broardly classified as those that behave incrementally and those that require the complete re-computation of the problem if the accuracy required of the answers increases. As someone who has experimented with a number of methods from both classes I shall describe my experiences (or more accurately prejudices!). Finally, I shall describe one of the problems set for the CCA2000 arithmetic competition (gaussian elimination), along with other problems from Computable Analysis (Non-Newtonian Orbital Mechanics, and Korteweg de-Vriess) and show why the use of Exact Arithmetic can become vital.
Friday 2nd June 2000, 14:00
Robert Recorde Room
Department of Computer Science