Gal's accurate tables is a method devised by
Shmuel Gal
Shmuel Gal ( he, שמואל גל, born 1940) is a mathematician and professor of statistics at the University of Haifa in Israel.
He devised the Gal's accurate tables method for the computer evaluation of elementary functions. With Zvi Yehudai he ...
to provide accurate values of
special functions
Special functions are particular mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications.
The term is defined by ...
using a
lookup table
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v wi ...
and
interpolation
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a n ...
. It is a fast and efficient method for generating values of functions like the
exponential or the
trigonometric functions
In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all ...
to within last-bit
accuracy for almost all argument values without using extended precision arithmetic.
The main idea in Gal's accurate tables is a different tabulation for the special function being computed. Commonly, the range is divided into several subranges, each with precomputed values and correction formulae. To compute the function, look up the closest point and compute a correction as a function of the distance.
Gal's idea is to not precompute equally spaced values, but rather to
perturb the points ''x'' so that both ''x'' and ''f''(''x'') are very nearly exactly representable in the chosen numeric format. By searching approximately 1000 values on either side of the desired value ''x'', a value can be found such that ''f''(''x'') can be represented with less than ±1/2000 bit of
rounding error. If the correction is also computed to ±1/2000 bit of accuracy (which does not require extra floating-point precision as long as the correction is less than 1/2000 the magnitude of the stored value ''f''(''x''), ''and'' the computed correction is more than ±1/1000 of a bit away from exactly half a bit (the difficult rounding case), then it is known whether the exact function value should be rounded up or down.
The technique provides an efficient way to compute the function value to within ±1/1000 least-significant bit, i.e. 10 extra bits of precision. If this approximation is more than ±1/1000 of a bit away from exactly midway between two representable values (which happens 99.8% of the time), then the correctly rounded result is clear.
Combined with an extended-precision fallback algorithm, this can compute the correctly rounded result in very reasonable ''average'' time. In 2/1000 (0.2%) of the time, such a higher-precision evaluation is required to resolve the rounding uncertainty, but this is infrequent enough that it has little effect on the average calculation time.
The problem of generating function values which are accurate to the last bit is known as the
table-maker's dilemma.
See also
*
Floating point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
*
Rounding
Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression with .
Rounding is often done to obta ...
References
*
*
*
*
* {{cite book , author-first1=Damien , author-last1=Stehlé , author-first2=Paul , author-last2=Zimmermann , author-link2=Paul Zimmermann (mathematician) , chapter-url=http://hal.inria.fr/inria-00070644/PDF/RR-5359.pdf , pages=257–264 , date=2005 , access-date=2018-01-15 , url-status=live , archive-url=https://web.archive.org/web/20180115191657/https://hal.inria.fr/inria-00070644/PDF/RR-5359.pdf , archive-date=2018-01-15 , doi=10.1109/ARITH.2005.24, chapter=Gal's Accurate Tables Method Revisited , title=17th IEEE Symposium on Computer Arithmetic (ARITH'05) , isbn=0-7695-2366-8
Numerical analysis
Computer arithmetic
Interpolation