The Table Maker's Dilemma: our search for worst cases.

Vincent Lefèvre and Jean-Michel Muller, Projet ARENAIRE, Laboratoire LIP,
Ecole Normale Supérieure de Lyon, 46 Allée d'Italie, 69364 Lyon Cedex 07, France.

Last modification: Oct. 28, 2003.

What is the Table Maker's Dilemma?

Let f be a transcendental function (sine, cosine, exponential, logarithm...). f cannot be exactly computed  in a finite number of steps. The only thing we can do is to compute approximations to f.

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.

Worst case generation

Using an algorithm due to V. Lefèvre and a network of around 100 workstations, we have found worst cases for some functions. We are still computing new worst cases, and we update our data base of worst cases each time we get a new value. Click here to get the already computed worst cases. For instance, for the logarithm function between e^4 = 54.598... and e^8 = 2980.957..., in IEEE-754 double precision arithmetic, the worst case is:

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

References and links

William Kahan's Documents relating to IEEE standard 754 for binary floating-point arithmetic

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)
 

Acknowledgements

We could not have performed our numerical experiments without the workstations of Laboratoire LIP and Ecole Normale Supérieure de Lyon. Ecole Normale Supérieure de Lyon also gave us a "BQR" grant to help us doing this study. We have also received much help from INRIA through the Fiable project. Getting exactly rounded transcendentals is one of the major goals of the ARENAIRE project. ARENAIRE is a joint project of CNRS, Ecole Normale Supérieure de Lyon and INRIA.