Algorithms in Computational Geometry and Computer Aided Design are
often developed for the Real RAM model of computation, which assumes
exactness of all the input arguments and operations. In practice,
however, the exactness imposes tremendous limitations on the
algorithms -- even the basic operations become uncomputable, or
prohibitively slow. When the computations of interest are limited to
determining the sign of polynomial expressions over floating point
numbers, faster approaches are available. One can evaluate the
polynomial in floating point first, together with some estimate of the
rounding error, and fall back to exact arithmetic only if this error
is too big to determine the sign reliably. A particularly efficient
variation on this approach has been used by Shewchuk in his robust
implementations of Orient and InSphere geometric predicates.
We extend Shewchuk's method to arbitrary polynomial expressions. The
expressions are given as programs in a suitable source language
featuring basic arithmetic operations of addition, subtraction,
multiplication and squaring, which are to be perceived by the
programmer as exact. The source language also allows for anonymous
functions, and thus enables the common functional programming
technique of staging. The method is presented formally through
several judgments that govern the compilation of the source expression
into target code, which is then easily transformed into SML or, in case of
single-stage expressions, into C.
