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 possiblity, 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).
| Table of contents |
|
2 A better, but still imperfect, recurrence formula 3 References |
A quick, but inaccurate, algorithm for calculating a table of N approximations sn for sin(2&pin/N) and cn for cos(2πn/N) is:
This is simply the Euler method for integrating the differential equation:
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 (s202 = -1.0368 instead of -0.9757). For N = 1024, the maximum error in the sine values is ~0.015 (s803 = -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 simple recurrence formula to generate trigonometric tables is based on Euler's formula and the relation:
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 often used to generate trigonometric values for FFT implementations:
See also:
A quick, but inaccurate, approximation
for n = 0,...,N-1, where d = 2π/N.
with initial conditions s(0)=0 and c(0)=1, whose analytical solution is s = sin(t) and c = cos(t).A better, but still imperfect, recurrence formula
This leads to the following recurrence to compute trigonometric values sn and cn as above:
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).
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.
References