Trigonometric Tables - A Better, But Still Imperfect, Recurrence Formula

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 s_n and c_n as above:

c₀ = 1

s₀ = 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 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:

c₀ = 1

s₀ = 0

c_n+1 = c_n − (αc_n + β s_n)

s_n+1 = s_n + (β c_n − α s_n)

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.