- Generating trigonometric tables
In

mathematics , tables oftrigonometric function s are useful in a number of areas. Before the existence ofpocket calculator s,**trigonometric tables**were essential fornavigation ,science andengineering . The calculation ofmathematical 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 are still used in

computer graphics , where accurate calculations are either not needed, or cannot be made fast enough.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).**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 apolynomial or rational approximation (such asChebyshev approximation , best uniform approximation, and Padé approximation, and typically for higher or variable precisions, Taylor andLaurent 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 calledCORDIC (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.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 toroots of unity , and can be computed with apolynomial root-finding algorithm in thecomplex plane . For example, the cosine and sine of 2π⋅5/37 are the real andimaginary part s, respectively, of a 37th root of unity, corresponding to a root of a degree-37 polynomial $x^\{37\}\; -\; 1$. Root-finding algorithms such asNewton'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.**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). The relevant identities, the first recorded derivation of which is by

Ptolemy , are (with signs determined by the quadrant of "x")::$cosleft(frac\{x\}\{2\}\; ight)\; =\; pm,\; sqrt\{frac\{1\; +\; cos(x)\}\{2$

:$sinleft(frac\{x\}\{2\}\; ight)\; =\; pm,\; sqrt\{frac\{1\; -\; cos(x)\}\{2$

:$sin(x\; pm\; y)\; =\; sin(x)\; cos(y)\; pm\; cos(x)\; sin(y),$

:$cos(x\; pm\; y)\; =\; cos(x)\; cos(y)\; mp\; sin(x)\; sin(y),$

Various other permutations on these identities are possible (for example, the earliest trigonometric tables used not sine and cosine, but sine and

versine ).**A quick, but inaccurate, approximation**A quick, but inaccurate, algorithm for calculating a table of "N" approximations "s"

_{"n"}for sin(2π"n"/"N") and "c"_{"n"}for cos(2π"n"/"N") is::"s"

_{0}= 0:"c"_{0}= 1:"s"_{"n"+1}= "s"_{"n"}+ "d" × "c"_{"n"}:"c"_{"n"+1}= "c"_{"n"}− "d" × "s"_{"n"}for "n" = 0,...,"N" − 1, where "d" = 2π/"N".This is simply the Euler method for integrating the

differential equation ::$ds/dt\; =\; c$:$dc/dt\; =\; -s$

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 ("s"

_{202}= −1.0368 instead of −0.9757). For "N" = 1024, the maximum error in the sine values is ~0.015 ("s"_{803}= −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 formula and the relation::$e^\{i(\; heta\; +\; Delta\; heta)\}\; =\; e^\{i\; heta\}\; imes\; e^\{iDelta\; heta\}$

This leads to the following recurrence to compute trigonometric values "s"

_{"n"}and "c"_{"n"}as above::"c"

_{0}= 1:"s"_{0}= 0:"c"_{"n"+1}= "w"_{"r"}"c"_{"n"}− "w"_{"i"}"s"_{"n"}:"s"_{"n"+1}= "w"_{"i"}"c"_{"n"}+ "w"_{"r"}"s"_{"n"}for "n" = 0, ..., "N" − 1, where "w"_{"r"}= cos(2π/"N") and "w"_{"i"}= sin(2π/"N"). These two starting trigonometric values are usually computed using existing library functions (but could also be found e.g. by employingNewton's method in the complex plane to solve for the primitive root of "z"^{"N"}− 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) often used to generate trigonometric values for FFT implementations:

:"c"

_{0}= 1:"s"_{0}= 0:"c"_{"n"+1}= "c"_{"n"}− (α"c"_{"n"}+ β "s"_{"n"}):"s"_{"n"+1}= "s"_{"n"}+ (β "c"_{"n"}− α "s"_{"n"})where α = 2 sin²(π/"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.

**ee also***

Numerical analysis

*CORDIC

*Exact trigonometric constants **References*** Carl B. Boyer, "A History of Mathematics", 2nd ed. (Wiley, New York, 1991).

* Manfred Tasche and Hansmartin Zeuner, "Improved roundoff error analysis for precomputed twiddle factors," "J. Computational Analysis and Applications"**4**(1), 1-18 (2002).

* James C. Schatzman, "Accuracy of the discrete Fourier transform and the fast Fourier transform," "SIAM J. Sci. Comput."**17**(5), 1150-1166 (1996).

* Vitit Kantabutra, "On hardware for computing exponential and trigonometric functions," "IEEE Trans. Computers"**45**(3), 328–339 (1996).

* R. P. Brent, " [*http://doi.acm.org/10.1145/321941.321944 Fast Multiple-Precision Evaluation of Elementary Functions*] ", "J. ACM"**23**, 242-251 (1976).

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Trigonometric functions**— Cosine redirects here. For the similarity measure, see Cosine similarity. Trigonometry History Usage Functions Generalized Inverse functions … Wikipedia**Exact trigonometric constants**— Exact constant expressions for trigonometric expressions are sometimes useful, mainly for simplifying solutions into radical forms which allow further simplification.All values of sine, cosine, and tangent of angles with 3° increments are… … Wikipedia**Trigonometry**— Trig redirects here. For other uses, see Trig (disambiguation). The Canadarm2 robotic manipulator on the International Space Station is operated by controlling the angles of its joints. Calculating the final position of the astronaut at the end… … Wikipedia**List of numerical analysis topics**— This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia**List of trigonometry topics**— This is a list of trigonometry topics, by Wikipedia page.*Angle *Angle excess *Brahmagupta interpolation formula *Chebyshev polynomials *Conway triangle notation *De Moivre s formula *Dirichlet kernel *Euler s formula *Exact trigonometric… … Wikipedia**List of basic trigonometry topics**— For a more comprehensive list, see the List of trigonometry topics. Trigonometry is a branch of mathematics which deals with angles, triangles and trigonometric functions such as sine, cosine and tangent.The following outline is provided as an… … Wikipedia**List of mathematics articles (G)**— NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… … Wikipedia**Generate**— may refer to:* CreateScience and math * Generate and test (trial and error) * Generating function, in math and physics * Generating primes * Generating set * Generating trigonometric tablesOther * Generated collection, in music theory *… … Wikipedia**Square root of 5**— The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. This number appears in the formula for the golden ratio. It can be denoted in surd form as::sqrt{5}.It is an irrational algebraic number.… … Wikipedia**List of computability and complexity topics**— This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia