Gal's accurate tables
Encyclopedia
Gal's accurate tables is a method devised by Shmuel Gal
to provide accurate values of special functions
using a lookup table
and interpolation
. It is a fast and efficient method for generating values of functions like the exponential
or the trigonometric functions to within last-bit accuracy for almost all argument values without using extended precision arithmetic.
The main idea in Gal's accurate tables is not to use tables of equally spaced argument values in which the rounding error prevents obtaining last-bit accuracy. In order to achieve a small error the following idea is used: Perturb
the original, equally spaced, argument values in such a way that the function value will be very close to numbers that can be exactly represented by the computer (much closer than the usual double-precision representation). Thus each table entry has a perturbed argument value and an associated function value. The function value for a given argument is interpolated using these more accurate end values from the table. This method enables controlling the error introduced by the computer representation of real number
s and extends the accuracy.
The problem of generating function values which are accurate to the last bit is known as the table-maker's dilemma.
Shmuel Gal
Shmuel Gal is a professor of statistics at the University of Haifa in Israel.Gal received a Ph.D. in mathematics from the Hebrew University of Jerusalem....
to provide accurate values of special functions
Special functions
Special functions are particular mathematical functions which have more or less established names and notations due to their importance in mathematical analysis, functional analysis, physics, or other applications....
using a lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
and interpolation
Interpolation
In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
. It is a fast and efficient method for generating values of functions like the exponential
Exponential function
In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...
or the trigonometric functions to within last-bit accuracy for almost all argument values without using extended precision arithmetic.
The main idea in Gal's accurate tables is not to use tables of equally spaced argument values in which the rounding error prevents obtaining last-bit accuracy. In order to achieve a small error the following idea is used: Perturb
Perturbation theory
Perturbation theory comprises mathematical methods that are used to find an approximate solution to a problem which cannot be solved exactly, by starting from the exact solution of a related problem...
the original, equally spaced, argument values in such a way that the function value will be very close to numbers that can be exactly represented by the computer (much closer than the usual double-precision representation). Thus each table entry has a perturbed argument value and an associated function value. The function value for a given argument is interpolated using these more accurate end values from the table. This method enables controlling the error introduced by the computer representation of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s and extends the accuracy.
The problem of generating function values which are accurate to the last bit is known as the table-maker's dilemma.