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.