An Almost Fft()

Fft() calculates the Fourier transform and its inverse for a vector of n reals, or a complex vector stored in a nx2 matrix. This Fft does not require n to be a power of 2. However it slows down for n>1000, or for n with a smallest prime factor greater than 19. In such cases it may be better to resort to a 2n fft and zero padding (see [21]). You can calculate the inverse fft by supplying the variable INZEE=FFALSE. See the example program testreg.cpp for calculating the first 5 serial correlations using the fft method.

The program is a translation of a FORTRAN program found in Conte and de Boor( see [7] ). The translation was produced by R. G. Davies in his matrix class, NEWMAT currently available in the Borland C++ library of Compuserve. I have quite unashamedly translated it for use in YAMP. I have, however, added the ability to do the inverse fft, so I don't feel like a total thief. My version is slower since it calculates offsets in vectors rather than incrementing pointers across the heap. My version is also slower in the virtual memory model since it must page memory almost constantly. My guess is that explicit evaluation of the discrete Fourier transform is faster since it requires less memory paging. I eventually need to see what can be done about this.