Lecture
Gal's accurate tables are a method developed by Shmuel Gal (a mathematician and professor of statistics at the University of Haifa in Israel) for obtaining accurate values of special functions using an interpolation table and interpolation. It is a fast and efficient method for generating the values of functions such as the exponential or trigonometric functions, correctly rounded to the last bit for almost all argument values, without using extended-precision arithmetic.
|
Shmuel Gal
|
|
|---|---|
 |
The basic idea of Gal's accurate tables is a different tabulation for the special function being computed. Normally the range is divided into several subranges, each of which has precomputed values and correction formulas. To compute the function, one finds the nearest point and computes the correction as a function of the distance.
Gal's idea is not to precompute values spaced at equal intervals, but rather to perturb the points x such that both x and f ( x ) are represented almost exactly in the chosen numerical format. By searching among roughly 1000 values on either side of the desired value of x, one can find such a value that f ( x ) can be represented with a rounding error of less than ±1/2000 of a bit. If the correction is also computed to a precision of ±1/2000 of a bit (which requires no additional floating-point computation precision, since if the correction is smaller than 1/2000, the magnitude of the stored value of f ( x), and the computed correction differ from exactly half a bit by more than ±1/1000 of a bit (the hard rounding case), then it is known whether the exact value of the function should be rounded up or down.
This method provides an efficient way of computing the value of a function to within ±1/1000 of the least significant bit, that is, to within 10 extra bits. If this approximation is more than ±1/1000 of a bit away from exactly midway between two representable values (which happens in 99.8% of cases), then the correctly rounded result is clear.
Combined with a fallback high-precision algorithm, this can compute the correctly rounded result in a very reasonable average time. In 2/1000 (0.2%) of cases, such a high-precision estimate is required to resolve the rounding ambiguity, but this is rare enough to have little effect on the average computation time.
The problem of generating function values correct to the last bit is known as the table maker's dilemma.
William M. Kahan introduced the term “Table Maker's Dilemma” to refer to the unknown cost of correctly rounding transcendental functions:
No one knows how much it would cost to correctly round y w for every pair of floating-point arguments for which no overflow/underflow occurs. Instead, respectable mathematical libraries compute the elementary transcendental functions to a little more than half a ulp in most cases, and almost always to well within one ulp. Why can't y w be rounded to within half a ulp, the way SQRT is? Because no one knows how much it would cost to compute... There is no general way to predict how many extra digits will have to be carried in order to compute a transcendental expression and correctly round it to some predetermined number of digits. Even the fact (if true) that finitely many extra digits will eventually suffice may be a deep theorem.
The IEEE 754 standard for floating-point operations guarantees that addition, subtraction, multiplication, division, fused multiply-add, square root, and floating-point remainder will produce a correctly rounded result of the operation with infinite precision. In the 1985 standard there was no such guarantee for the more complex functions, and they were generally accurate to at best only the last bit. However, the 2008 standard guarantees that compliant implementations will produce correctly rounded results consistent with the active rounding mode; implementing these functions, however, is not mandatory.
Using the Gelfond–Schneider theorem and the Lindemann–Weierstrass theorem, one can prove that many standard elementary functions return transcendental results, except for a few well-known arguments; therefore, from a theoretical standpoint such functions can always be correctly rounded. However, to implement such a function, determining the limit, for a given precision, of how accurately the results must be computed before a correctly rounded result can be guaranteed may require a great deal of computation time or may be unattainable. In practice, when this limit is unknown (or only a very large limit is known), the implementation must make some decision (see below); but under a probabilistic model, correct rounding can be satisfied with very high probability by using an intermediate precision of up to twice the number of digits of the target format plus some small constant (after accounting for special cases).
See alsoEdit
Comments