Optimizing Programs over the Constructive Reals

Abstract

A real number x is constructive if an algorithm can be given to compute arbitrarily accurate approximations to x. An efficient implementation of constructive real arithmetic could be used for prototyping numerical programs, experimenting with numerical algorithms, to distinguish round-off errors from algorithmic errors, and to perform computations in highly unstable sections of a program. It could be used to evaluate expressions in a symbolic algebra system without regard to their numerical stability. It would also be useful in an automatic assertion checking system in a programming environment, since assertions in numerical programs are naturally stated in terms of real, not floating point, arithmetic. Previous implementations have used several different representations for constructive real values, but all consist of the same basic approach. An execution history is recorded as the program runs, containing all information necessary to recompute any constructive real value. These histories are then used to produce approximations to real values as required. However, execution histories may become extremely large and costly to maintain. Lazy infinite continued fractions, lazy infinite digit sequences, and various functional approaches all use history-based methods, in different forms. An alternate approach simply provides the programmer with a variable-precision interval arithmetic package. It is argued that this not a true implementation of constructive real arithmetic, but more a tool that may used in constructing a constructive real arithmetic package. A new approach is presented that uses data-flow analysis to discover much of the information previously gathered in execution histories. The instructions that may require approximations for their arguments are located, and a new version of the program is created, in two parts: one part mirrors the original program, but performs interval arithmetic at fixed precision for real operations. The second part, consisting of a set of subroutines, recomputes approximations to real values as required. A strategy for using variable-precision intervals is given such that the cost of all re-executions necessary to compute an approximation is only a constant factor more than the cost of the final re-execution. Experimental results from a prototype implementation are presented.