FFTEASY uses a Cooley-Tukey Fast Fourier Transform algorithm. For an excellent discussion of Fourier transforms (continuous and discrete) in general and the Cooley-Tukey algorithm in particular see Numerical Recipes. Here I only briefly describe the algorithm and how it is implemented in FFTEASY.
The heart of the method is the Danielson-Lanczos (DL) formula that
allows one to compute a discrete Fourier transform (DFT) of size by
separately computing two FTs of size . Let be the DFT of a
function
. Then let be the DFT of
the even points and be the DFT of the odd
points . The DL formula then says
(9) |
(10) |
It turns out that rather than keeping track of successive divisions into even and odd points, the data in the original array can be rearranged in such a way that and are always sequential. In other words once the array has been rearranged in this way the DL formula can be used to combine the first two elements into an DFT, and then combine that DFT with the succeeding DFT into an DFT, and so on. The way to rearrange the array to accomplish this is to arrange it in bit-reverse order. In other words if then the four elements of your original array are , , , and . To bit-reverse this array you would swap the middle two elements, leaving the first and last where they are. With some work you should be able to convince yourself that bit-reversal is equivalent to pulling out successive arrays of even and odd points. Otherwise you can take my word for it because I'm not going to prove it to you here.
The following sections describe each of the four FFTEASY functions. Note that all of the functions take as input an array of floats but immediately typecast it as an array of complex numbers, each consisting of two floats representing real and complex parts. So any time I refer to the th element of an array I mean the th complex element, corresponding to the and elements of the actual array of floats. Formulas are given here in terms of complex numbers and then implemented in the functions explicitly in terms of real and imaginary parts.