Editing Trigonometric tables (section)

== A better, but still imperfect, recurrence formula ==
{{original research|date=December 2018}}

A simple recurrence formula to generate trigonometric tables is based on [[Euler's formula]] and the relation:

:<math>e^{i(\theta + \Delta)} = 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> &minus; ''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''&nbsp;&minus;&nbsp;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>&nbsp;&minus;&nbsp;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(ε&nbsp;''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<ref>{{harvnb|Singleton|1967}}</ref>) 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>&nbsp;&minus;&nbsp;(&alpha; ''c''<sub>''n''</sub>&nbsp;+&nbsp;&beta; ''s''<sub>''n''</sub>)
:''s''<sub>''n''+1</sub> = ''s''<sub>''n''</sub>&nbsp;+&nbsp;(&beta;&nbsp;''c''<sub>''n''</sub>&nbsp;&minus;&nbsp;&alpha;&nbsp;''s''<sub>''n''</sub>)

where α = 2&nbsp;sin<sup>2</sup>(π/''N'') and β = sin(2π/''N''). The errors of this method are much smaller, O(ε&nbsp;√''N'') on average and O(ε&nbsp;''N'') in the worst case, but this is still large enough to substantially degrade the accuracy of FFTs of large sizes.