A Better, But Still Imperfect, Recurrence Formula
A simple recurrence formula to generate trigonometric tables is based on Euler's formula 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 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:
- 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.
Read more about this topic: Trigonometric Tables
Famous quotes containing the words recurrence and/or formula:
“Forgetfulness is necessary to remembrance. Ideas are retained by renovation of that impression which time is always wearing away, and which new images are striving to obliterate. If useless thoughts could be expelled from the mind, all the valuable parts of our knowledge would more frequently recur, and every recurrence would reinstate them in their former place.”
—Samuel Johnson (17091784)
“I take it that what all men are really after is some form or perhaps only some formula of peace.”
—Joseph Conrad (18571924)