|
|
| (632 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| {{Trigonometry}}
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
| In [[mathematics]], tables of [[trigonometric function]]s are useful in a number of areas. Before the existence of [[pocket calculator]]s, '''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 [[history of computing|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.
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| 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).
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| ==On-demand computation== | | '''MathML''' |
| [[Image:Bernegger Manuale 137.jpg|thumb|right|200px|A page from a 1619 book of [[mathematical table]]s]]
| | :<math forcemathmode="mathml">E=mc^2</math> |
| 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|floating-point]] units, is to combine a [[polynomial]] or [[rational function|rational]] [[approximation theory|approximation]] (such as [[Chebyshev approximation]], best uniform approximation, and [[Padé approximant|Padé approximation]], and typically for higher or variable precisions, [[Taylor series|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 [[multiplication ALU|hardware multiplier]], there is an algorithm called [[CORDIC]] (as well as related techniques) that is more efficient, since it uses only [[shift operator|shift]]s and additions. All of these methods are commonly implemented in [[computer hardware|hardware]] for performance reasons.
| |
|
| |
|
| For [[arbitrary-precision arithmetic|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 number|complex]]) [[elliptic integral]] (Brent, 1976).
| | <!--'''PNG''' (currently default in production) |
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| Trigonometric functions of angles that are [[rational number|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 part|real]] and [[imaginary part]]s, respectively, of a 37th root of unity, corresponding to a root of a [[degree of a polynomial|degree]]-37 polynomial ''x''<sup>37</sup> − 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 number|transcendental]] trigonometric constants, however.
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| ==Half-angle and angle-addition formulas== | | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
|
| |
|
| 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 identity|trigonometric identities]] starting from a known value (such as sin(π/2) = 1, cos(π/2) = 0). This method was used by the ancient astronomer [[Ptolemy]], 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):
| | ==Demos== |
|
| |
|
| :<math>\cos\left(\frac{x}{2}\right) = \pm \sqrt{\tfrac{1}{2}(1 + \cos x)}</math> | | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
|
| |
|
| :<math>\sin\left(\frac{x}{2}\right) = \pm \sqrt{\tfrac{1}{2}(1 - \cos x)}</math>
| |
|
| |
|
| :<math>\sin(x \pm y) = \sin(x) \cos(y) \pm \cos(x) \sin(y)\,</math> | | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| :<math>\cos(x \pm y) = \cos(x) \cos(y) \mp \sin(x) \sin(y)\,</math>
| | ==Test pages == |
|
| |
|
| These were used to construct [[Ptolemy's table of chords]], which was applied to astronomical problems.
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| Various other permutations on these identities are possible: for example, some early trigonometric tables used not sine and cosine, but sine and [[versine]]).
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| ==A quick, but inaccurate, approximation==
| | ==Bug reporting== |
| | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| A quick, but inaccurate, algorithm for calculating a table of ''N'' approximations ''s''<sub>''n''</sub> for [[sine|sin]](2[[Pi|π]]''n''/''N'') and ''c''<sub>''n''</sub> for [[cosine|cos]](2π''n''/''N'') is:
| |
| | |
| :''s''<sub>0</sub> = 0
| |
| :''c''<sub>0</sub> = 1
| |
| :''s''<sub>''n''+1</sub> = ''s''<sub>''n''</sub> + ''d'' × ''c''<sub>''n''</sub>
| |
| :''c''<sub>''n''+1</sub> = ''c''<sub>''n''</sub> − ''d'' × ''s''<sub>''n''</sub>
| |
| for ''n'' = 0,...,''N'' − 1, where ''d'' = 2π/''N''.
| |
| | |
| This is simply the [[Numerical ordinary differential equations#The Euler method|Euler method]] for integrating the [[differential equation]]:
| |
| | |
| :<math>ds/dt = c</math>
| |
| :<math>dc/dt = -s</math>
| |
| | |
| 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''<sub>202</sub> = −1.0368 instead of −0.9757). For ''N'' = 1024, the maximum error in the sine values is ~0.015 (''s''<sub>803</sub> = −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:
| |
| | |
| :<math>e^{i(\theta + \Delta\theta)} = e^{i\theta} \times e^{i\Delta\theta}</math>
| |
| | |
| This leads to the following recurrence to compute trigonometric values ''s''<sub>''n''</sub> and ''c''<sub>''n''</sub> as above:
| |
| | |
| :''c''<sub>0</sub> = 1
| |
| :''s''<sub>0</sub> = 0
| |
| :''c''<sub>''n''+1</sub> = ''w''<sub>''r''</sub> ''c''<sub>''n''</sub> − ''w''<sub>''i''</sub> ''s''<sub>''n''</sub>
| |
| :''s''<sub>''n''+1</sub> = ''w''<sub>''i''</sub> ''c''<sub>''n''</sub> + ''w''<sub>''r''</sub> ''s''<sub>''n''</sub> | |
| for ''n'' = 0, ..., ''N'' − 1, where ''w''<sub>''r''</sub> = cos(2π/''N'') and ''w''<sub>''i''</sub> = 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 unity|root]] of ''z''<sup>''N''</sup> − 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:
| |
| | |
| :''c''<sub>0</sub> = 1
| |
| :''s''<sub>0</sub> = 0
| |
| :''c''<sub>''n''+1</sub> = ''c''<sub>''n''</sub> − (α''c''<sub>''n''</sub> + β ''s''<sub>''n''</sub>)
| |
| :''s''<sub>''n''+1</sub> = ''s''<sub>''n''</sub> + (β ''c''<sub>''n''</sub> − α ''s''<sub>''n''</sub>)
| |
| | |
| where α = 2 sin<sup>2</sup>(π/''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 analysis]]
| |
| * [[CORDIC]]
| |
| * [[Exact trigonometric constants]]
| |
| * [[Aryabhata's sine table]]
| |
| * [[Madhava's sine table]]
| |
| | |
| ==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).
| |
| * Singleton, Richard C. (1967). On computing the fast Fourier transform. ''Comm. ACM'', vol. 10, 647–654.
| |
| * Gal, Shmuel and Bachelis, Boris. An accurate elementary mathematical library for the IEEE floating point standard, ACM Transaction on Mathematical Software (1991).
| |
| | |
| [[Category:Numerical analysis]]
| |
| [[Category:Trigonometry]]
| |
| | |
| [[ar:جداول مثلثية]]
| |
| [[ca:Construcció de les taules trigonomètriques]]
| |
| [[fr:Construction des tables trigonométriques]]
| |
| [[it:Tavola trigonometrica]]
| |
| [[sv:Trigonometrisk tabell]]
| |
