Generating trigonometric tables

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}
{mi², represent, 1st}

In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering. The calculation of mathematical tables was an important area of study, which led to the development of the first mechanical computing devices.

Modern computers and pocket calculators now generate trigonometric function values on demand, using special libraries of mathematical code. Often, these libraries use pre-calculated tables internally, and compute the required value by using an appropriate interpolation method. Interpolation of simple look-up tables of trigonometric functions is still used in computer graphics, where only modest accuracy may be required and speed is often paramount.

Another important application of trigonometric tables and generation schemes is for fast Fourier transform (FFT) algorithms, where the same trigonometric function values (called twiddle factors) must be evaluated many times in a given transform, especially in the common case where many transforms of the same size are computed. In this case, calling generic library routines every time is unacceptably slow. One option is to call the library routines once, to build up a table of those trigonometric values that will be needed, but this requires significant memory to store the table. The other possibility, since a regular sequence of values is required, is to use a recurrence formula to compute the trigonometric values on the fly. Significant research has been devoted to finding accurate, stable recurrence schemes in order to preserve the accuracy of the FFT (which is very sensitive to trigonometric errors).

Contents

On-demand computation

Modern computers and calculators use a variety of techniques to provide trigonometric function values on demand for arbitrary angles (Kantabutra, 1996). One common method, especially on higher-end processors with floating-point units, is to combine a polynomial or rational approximation (such as Chebyshev approximation, best uniform approximation, and Padé approximation, and typically for higher or variable precisions, Taylor and Laurent series) with range reduction and a table lookup — they first look up the closest angle in a small table, and then use the polynomial to compute the correction. Maintaining precision while performing such interpolation is nontrivial, however; and methods like Gal's accurate tables, Cody and Waite reduction, and Payne and Hanek reduction algorithms can be used for this purpose. On simpler devices that lack a hardware multiplier, there is an algorithm called CORDIC (as well as related techniques) that is more efficient, since it uses only shifts and additions. All of these methods are commonly implemented in hardware for performance reasons.

Full article ▸

related documents
Monotone convergence theorem
Cotangent space
Linear subspace
Column space
Operator overloading
Quasigroup
Special linear group
Associative algebra
Borel algebra
Automata theory
Graftal
Golden ratio base
Stirling's approximation
Sylow theorems
Least common multiple
Jacobi symbol
1 (number)
Measure (mathematics)
Free variables and bound variables
Diophantine equation
Theory of computation
Perfect number
Cumulative distribution function
Chain complex
Product topology
Spectrum of a ring
NaN
Elliptic integral
Interpolation search
Compact space