Generating trigonometric tables
Encyclopedia
In mathematics
, tables of trigonometric function
s 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 table
s 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).
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 shift
s and additions. All of these methods are commonly implemented in hardware
for performance reasons.
For very high precision
calculations, when series-expansion convergence becomes too slow, trigonometric functions can be approximated by the arithmetic-geometric mean, which itself approximates the trigonometric function by the (complex
) elliptic integral
(Brent, 1976).
Trigonometric functions of angles that are rational
multiples of 2π are algebraic number
s, related to roots of unity, and can be computed with a polynomial
root-finding algorithm
in the complex plane
. For example, the cosine and sine of 2π ⋅ 5/37 are the real and imaginary parts, respectively, of a 37th root of unity, corresponding to a root of a degree
-37 polynomial x37 − 1. Root-finding algorithms such as Newton's method
are much simpler than the arithmetic-geometric mean algorithms above while converging at a similar asymptotic rate; the latter algorithms are required for transcendental
trigonometric constants, however.
, who derived them in the Almagest
, a treatise on astronomy. In modern form, the identities he derived are stated as follows (with signs determined by the quadrant in which x lies):
These were used to construct Ptolemy's table of chords
, which was applied to astronomical problems.
Various other permutations on these identities are possible: for example, some early trigonometric tables used not sine and cosine, but sine and versine
).
(2π
n/N) and cn for cos(2πn/N) is:
for n = 0,...,N − 1, where d = 2π/N.
This is simply the Euler method for integrating the differential equation
:
with initial conditions s(0) = 0 and c(0) = 1, whose analytical solution is s = sin(t) and c = cos(t).
Unfortunately, this is not a useful algorithm for generating sine tables because it has a significant error, proportional to 1/N.
For example, for N = 256 the maximum error in the sine values is ~0.061 (s202 = −1.0368 instead of −0.9757). For N = 1024, the maximum error in the sine values is ~0.015 (s803 = −0.99321 instead of −0.97832), about 4 times smaller. If the sine and cosine values obtained were to be plotted, this algorithm would draw a logarithmic spiral rather than a circle.
and the relation:
This leads to the following recurrence to compute trigonometric values sn and cn as above:
for n = 0, ..., N − 1, where wr = cos(2π/N) and wi = sin(2π/N). These two starting trigonometric values are usually computed using existing library functions (but could also be found e.g. by employing Newton's method
in the complex plane to solve for the primitive root
of zN − 1).
This method would produce an exact table in exact arithmetic, but has errors in finite-precision floating-point arithmetic. In fact, the errors grow as O(ε N) (in both the worst and average cases), where ε is the floating-point precision.
A significant improvement is to use the following modification to the above, a trick (due to Singleton, 1967) often used to generate trigonometric values for FFT implementations:
where α = 2 sin2(π/N) and β = sin(2π/N). The errors of this method are much smaller, O(ε √N) on average and O(ε N) in the worst case, but this is still large enough to substantially degrade the accuracy of FFTs of large sizes.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, tables of trigonometric function
Trigonometric function
In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...
s are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation
Navigation
Navigation is the process of monitoring and controlling the movement of a craft or vehicle from one place to another. It is also the term of art used for the specialized knowledge used by navigators to perform navigation tasks...
, science
Science
Science is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...
and engineering
Engineering
Engineering is the discipline, art, skill and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge, in order to design and build structures, machines, devices, systems, materials and processes that safely realize improvements to the lives of...
. The calculation of mathematical table
Mathematical table
Before calculators were cheap and plentiful, people would use mathematical tables —lists of numbers showing the results of calculation with varying arguments— to simplify and drastically speed up computation...
s was an important area of study, which led to the development of the first mechanical computing devices
History of computing
The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables...
.
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
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, 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
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
(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).
On-demand computation
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
units, is to combine a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
or rational
Rational function
In mathematics, a rational function is any function which can be written as the ratio of two polynomial functions. Neither the coefficients of the polynomials nor the values taken by the function are necessarily rational.-Definitions:...
approximation
Approximation theory
In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby...
(such as Chebyshev approximation, best uniform approximation, and Padé approximation
Padé approximant
Padé approximant is the "best" approximation of a function by a rational function of given order - under this technique, the approximant's power series agrees with the power series of the function it is approximating....
, and typically for higher or variable precisions, Taylor
Taylor series
In mathematics, a Taylor series is a representation of a function as an infinite sum of terms that are calculated from the values of the function's derivatives at a single point....
and Laurent series
Laurent series
In mathematics, the Laurent series of a complex function f is a representation of that function as a power series which includes terms of negative degree. It may be used to express complex functions in cases where...
) 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
Gal's accurate tables
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...
, 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
CORDIC
CORDIC is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions...
(as well as related techniques) that is more efficient, since it uses only shift
Shift operator
In mathematics, and in particular functional analysis, the shift operator or translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator....
s and additions. All of these methods are commonly implemented in hardware
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
for performance reasons.
For very high precision
Arbitrary-precision arithmetic
In computer science, arbitrary-precision arithmetic indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most ALU hardware, which typically...
calculations, when series-expansion convergence becomes too slow, trigonometric functions can be approximated by the arithmetic-geometric mean, which itself approximates the trigonometric function by the (complex
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
) elliptic integral
Elliptic integral
In integral calculus, elliptic integrals originally arose in connection with the problem of giving the arc length of an ellipse. They were first studied by Giulio Fagnano and Leonhard Euler...
(Brent, 1976).
Trigonometric functions of angles that are rational
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
multiples of 2π are algebraic number
Algebraic number
In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients. Numbers such as π that are not algebraic are said to be transcendental; almost all real numbers are transcendental...
s, related to roots of unity, and can be computed with a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
root-finding algorithm
Root-finding algorithm
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
in the complex plane
Complex plane
In mathematics, the complex plane or z-plane is a geometric representation of the complex numbers established by the real axis and the orthogonal imaginary axis...
. For example, the cosine and sine of 2π ⋅ 5/37 are the real and imaginary parts, respectively, of a 37th root of unity, corresponding to a root of a degree
Degree of a polynomial
The degree of a polynomial represents the highest degree of a polynominal's terms , should the polynomial be expressed in canonical form . The degree of an individual term is the sum of the exponents acting on the term's variables...
-37 polynomial x37 − 1. Root-finding algorithms such as Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
are much simpler than the arithmetic-geometric mean algorithms above while converging at a similar asymptotic rate; the latter algorithms are required for transcendental
Transcendental number
In mathematics, a transcendental number is a number that is not algebraic—that is, it is not a root of a non-constant polynomial equation with rational coefficients. The most prominent examples of transcendental numbers are π and e...
trigonometric constants, however.
Half-angle and angle-addition formulas
Historically, the earliest method by which trigonometric tables were computed, and probably the most common until the advent of computers, was to repeatedly apply the half-angle and angle-addition trigonometric identities starting from a known value (such as sin(π/2) = 1, cos(π/2) = 0). This method was used by the ancient astronomer PtolemyPtolemy
Claudius Ptolemy , was a Roman citizen of Egypt who wrote in Greek. He was a mathematician, astronomer, geographer, astrologer, and poet of a single epigram in the Greek Anthology. He lived in Egypt under Roman rule, and is believed to have been born in the town of Ptolemais Hermiou in the...
, who derived them in the Almagest
Almagest
The Almagest is a 2nd-century mathematical and astronomical treatise on the apparent motions of the stars and planetary paths. Written in Greek by Claudius Ptolemy, a Roman era scholar of Egypt,...
, a treatise on astronomy. In modern form, the identities he derived are stated as follows (with signs determined by the quadrant in which x lies):
These were used to construct Ptolemy's table of chords
Ptolemy's table of chords
The table of chords, created by the astronomer and geometer Ptolemy in Egypt during the 2nd century AD, is a trigonometric table in Book I, chapter 11 of Ptolemy's Almagest, a treatise on mathematical astronomy. It is essentially equivalent to a table of values of the sine function...
, which was applied to astronomical problems.
Various other permutations on these identities are possible: for example, some early trigonometric tables used not sine and cosine, but sine and versine
Versine
The versine or versed sine, versin, is a trigonometric function equal to and 2sin2. It appeared in some of the earliest trigonometric tables and was once widespread, but it is now little-used...
).
A quick, but inaccurate, approximation
A quick, but inaccurate, algorithm for calculating a table of N approximations sn for sinSine
In mathematics, the sine function is a function of an angle. In a right triangle, sine gives the ratio of the length of the side opposite to an angle to the length of the hypotenuse.Sine is usually listed first amongst the trigonometric functions....
(2π
Pi
' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
n/N) and cn for cos(2πn/N) is:
- s0 = 0
- c0 = 1
- sn+1 = sn + d × cn
- cn+1 = cn − d × sn
for n = 0,...,N − 1, where d = 2π/N.
This is simply the Euler method for integrating the differential equation
Differential equation
A differential equation is a mathematical equation for an unknown function of one or several variables that relates the values of the function itself and its derivatives of various orders...
:
with initial conditions s(0) = 0 and c(0) = 1, whose analytical solution is s = sin(t) and c = cos(t).
Unfortunately, this is not a useful algorithm for generating sine tables because it has a significant error, proportional to 1/N.
For example, for N = 256 the maximum error in the sine values is ~0.061 (s202 = −1.0368 instead of −0.9757). For N = 1024, the maximum error in the sine values is ~0.015 (s803 = −0.99321 instead of −0.97832), about 4 times smaller. If the sine and cosine values obtained were to be plotted, this algorithm would draw a logarithmic spiral rather than a circle.
A better, but still imperfect, recurrence formula
A simple recurrence formula to generate trigonometric tables is based on Euler's formulaEuler's formula
Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the deep relationship between the trigonometric functions and the complex exponential function...
and the relation:
This leads to the following recurrence to compute trigonometric values sn and cn as above:
- c0 = 1
- s0 = 0
- cn+1 = wr cn − wi sn
- sn+1 = wi cn + wr sn
for n = 0, ..., N − 1, where wr = cos(2π/N) and wi = sin(2π/N). These two starting trigonometric values are usually computed using existing library functions (but could also be found e.g. by employing Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
in the complex plane to solve for the primitive root
Root of unity
In mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, field theory, and the discrete...
of zN − 1).
This method would produce an exact table in exact arithmetic, but has errors in finite-precision floating-point arithmetic. In fact, the errors grow as O(ε N) (in both the worst and average cases), where ε is the floating-point precision.
A significant improvement is to use the following modification to the above, a trick (due to Singleton, 1967) often used to generate trigonometric values for FFT implementations:
- c0 = 1
- s0 = 0
- cn+1 = cn − (αcn + β sn)
- sn+1 = sn + (β cn − α sn)
where α = 2 sin2(π/N) and β = sin(2π/N). The errors of this method are much smaller, O(ε √N) on average and O(ε N) in the worst case, but this is still large enough to substantially degrade the accuracy of FFTs of large sizes.
See also
- Numerical analysisNumerical analysisNumerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
- CORDICCORDICCORDIC is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions...
- Exact trigonometric constantsExact trigonometric constantsExact constant expressions for trigonometric values are sometimes useful, mainly for simplifying solutions into radical forms which allow further simplification....
- Aryabhata's sine tableĀryabhaṭa's sine tableĀryabhaṭa's sine table is a set of twenty-four of numbers given in the astronomical treatise Āryabhaṭiya composed by the fifth century Indian mathematician and astronomer Āryabhaṭa , for the computation of the half-chords of certain set of arcs of a circle...
- Madhava's sine tableMadhava's sine tableMadhava's sine table is the table of trigonometric sines of various angles constructed by the 14th century Kerala mathematician-astronomer Madhava of Sangamagrama. The table lists the trigonometric sines of the twenty-four angles 3.75°, 7.50°, 11.25°, ... , and 90.00°...