Twin-float arithmetic

We present a heuristically certified form of floating-point arithmetic and its implementation in CoCoALib. This arithmetic is intended to act as a fast alternative to exact rational arithmetic, and is developed from the idea of paired floats expounded by Traverso and Zanoni (2002). As prerequisites we need a source of (pseudo-)random numbers, and an underlying floating-point arithmetic system where the user can set the precision. Twin-float arithmetic can be used only where the input data are exact, or can be obtained at high enough precision. Our arithmetic includes a total cancellation heuristic for sums and differences, and so can be used in classical algebraic algorithms such as Buchberger's algorithm. We also present a (new) algorithm for recovering an exact rational value from a twin-float, so in some cases an exact answer can be obtained from an approximate computation. The ideas presented here are implemented as a ring in CoCoALib, called RingTwinFloat, allowing them to be used easily in a wide variety of algebraic computations (including Grobner bases). (C) 2011 Elsevier Ltd. All rights reserved.