The LEDA class real number
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra · 1996
We describe the implementation of the LEDA data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and squareroot. The main features of the data type real are: the user-interface is similar to that of the built-in data type double. All comparison operators #left brace#>,#>=#,<,#<=#,=#right brace# are exact. In order to determine the sign of a real number x the data type first computes a rational number q such that vertical stroke x vertical stroke #<=# q implies x 0 and then computes an approximation of x of sufficient precision to decide the sign of x. The user may assist the data type by providing a separation bound q. The data type also allows to evaluate real expressions with arbitrary precision. One may either set the mantissa length of the underlying floating point system and then evaluate the expression with that mantissa length or one may specify an error bound q. The data type then computes an approximation with absolute error at most q. The implementation of the data type real is based on the LEDA data types integer and bigfloat which are the types of arbitrary precision integers and floating point numbers, respectively. The implementation takes various shortcuts for increased efficiency, e.g., a double approximation of any number together with an error bounds is maintained and tests are first performed on these approximations. A high precision computation is only started when the best on the double approximation is inconclusive. (orig.)