Rounding - The Table-maker's Dilemma

The Table-maker's Dilemma

William Kahan coined the term "The Table-Maker's Dilemma" for the unknown cost of rounding transcendental functions:

"Nobody knows how much it would cost to compute y^w correctly rounded for every two floating-point arguments at which it does not over/underflow. Instead, reputable math libraries compute elementary transcendental functions mostly within slightly more than half an ulp and almost always well within one ulp. Why can't Y^W be rounded within half an ulp like SQRT? Because nobody knows how much computation it would cost... No general way exists to predict how many extra digits will have to be carried to compute a transcendental expression and round it correctly to some preassigned number of digits. Even the fact (if true) that a finite number of extra digits will ultimately suffice may be a deep theorem."

The IEEE floating point standard guarantees that add, subtract, multiply, divide, square root, and floating point remainder will give the correctly rounded result of the infinite precision operation. No such guarantee was given in the 1985 standard for more complex functions and they are typically only accurate to within the last bit at best. However the 2008 standard guarantees that conforming implementations will give correctly rounded results which respect the active rounding mode, implementation of the functions is however optional.

Using the Gelfond–Schneider theorem and Lindemann–Weierstrass theorem many of the standard elementary functions can be proved to return transcendental results when given rational non-zero arguments; therefore it is always possible to correctly round such functions. However determining a limit for a given precision on how accurate results needs to be computed before a correctly rounded result can be guaranteed may demand a lot of computation time.

There are some packages around now that offer correct rounding. The GNU MPFR package gives correctly rounded arbitrary precision results. Some other libraries implement elementary functions with correct rounding in double precision:

• IBM's libultim, in rounding to nearest only.
• Sun Microsystems's libmcr, in the 4 rounding modes.
• CRlibm, written in the Arénaire team (LIP, ENS Lyon). It supports the 4 rounding modes and is proved.

There exist computable numbers which a rounded value can never be determined no matter how many digits are calculated. Specific instances cannot be given but this follows from the undecidability of the halting problem. For instance if Goldbach's conjecture is true but unprovable then the result of rounding the following value up to the next integer cannot be determined: 10−n where n is the first even number greater than 4 which is not the sum of two primes, or 0 if there is no such number. The result is 1 if such a number exists and 0 if no such number exists. The value before rounding can however be approximated to any given precision even if the conjecture is unprovable.