fftrFFT of Real Valued Sequence.
double x, sine;
fftr(x, m, sine);
Computes the (complex valued) discrete Fourier transform of the real valued sequence x. The input sequence x contains n = 2**m samples. The program fills array sine[k] with n/4 + 1 values of sin(2 PI k / n).
Data format for complex valued output is real part followed by imaginary part. The output is developed in the input array x.
The algorithm takes advantage of the fact that the FFT of an n point real sequence can be obtained from an n/2 point complex FFT.
A radix 2 FFT algorithm is used.
Execution time on an LSI-11/23 with floating point chip is 1.0 sec for n = 256.
E. Oran Brigham, The Fast Fourier Transform; Prentice-Hall, Inc., 1974