**Last modification:** Oct. 28, 2003.

We assume that the input and output values are represented in the same floating-point format, with n-bit mantissas (the target format for our tests was IEEE-754 double precision). Assume a given rounding mode, chosen among the 4 rounding modes defined by the IEEE standard (towards +infinity, towards -infinity, towards 0, or to the nearest). Our goal is to implement the most common elementary functions with correct rounding, that is, to always return what you would get if you rounded (according to the chosen rounding mode) the exact, infinitely precise, result.

Assume we compute y = f(x). Since the exact result y cannot be known, we can only compute an approximate value y*, with relative error 2^(-m) (with m significantly larger than n). We round this intermediate value... and hope that this is equivalent to rounding y. By doing this, we may be in trouble if y is very close to an exactly representable number (for rounding toward 0, +infinity or -infinity), or if y is very close to the mid-point of two consecutive exactly representable numbers (for rounding to the nearest).

The *Table Maker's Dilemma *consists in finding, for a given
function
and a given domain, the smallest value of m such that rounding this
approximate
value y* always gives the same result as rounding the exact value y.
This
is done by looking for "worst cases", that is, in the considered
domain,
the values x such that f(x) is closest to an exactly representable
number
or the mid-point of two exactly representable numbers.

log 110101100.01010000101101000000100111001000101011101110

= 110.00001111010100101111001101111010111011001111110011 1
1^{60}
0101...

where 1^{60} means "60 consecutive ones". This means that if the approximate calculation is such that we can guarantee at least 115 significant digits, then we will be able to always return correctly rounded logarithms in the considered domain.

Click here to go to our data base of worst cases

Vincent Lefèvre, Jean-Michel Muller and Arnaud Tisserand, The Table Maker's Dilemma, IEEE Transactions on Computers, Vol. 47 No 11, Nov. 1998.

V. Lefèvre, An algorithm that computes a lower bound on the distance between a segment and mathbbZ^2, Research report 97-18, Laboratoire de l'Informatique du Parallélisme, Lyon, France, 1997.

J.M. Muller, Elementary Functions, Algorithms and Implementation, Birkhauser Boston, 1997 .

David Hough's page (with link
to Goldberg's paper on floating-point arithmetic and Ng's notes on
trigonometric
argument reduction)