The DFT requires the calculation of the sums
where 
. At first sight, this requires
at least N2 multiplications to generate all N of the
coefficients Hn.
But this is not the case. As explained in "Numerical Recipes", the
summation may be broken into two parts, one over the even-numbered
elements (k = 0,2,4,...) and the other over the odd-numbered elements
(k = 1,3,5,..). In turn, each one of these parts can be broken into its
even-numbered and odd-numbered parts, and the process can be continued,
with careful book-keeping, until the summation has become divided
into 1-point Fourier transforms (which are identity transforms).
This repeated dissection of the series into even- and odd-numbered parts
can be implemented in the computer by reversing the bit-pattern of the
addresses of the data elements. After this is done, the required N
values of Hn can be generated by making a sequence of
2,4,8,...-point summations. The total time for the operation scales not as
N2 but as NlogN, so that for large transforms there
is a enormous saving in time.
As a consequence of the bit-reversal process, the application of the FFT to a vector of data in a computer leaves the resulting components of the transform in a rather mixed-up state. For the programs you will use in this course, this mixed-up state has been sorted out for you, so that the vector available after the FFT consists of values at the following frequency components in increasing order:
[Recall that f(n) = n/(2
), so that the first
frequency point is f=-1/2 and the last+1 (equal to the first) is
f=1/2,
if we define = 1.]
You should also note that the routine you are given is designed to take the FFT of a vector of complex numbers, and it produces a vector of complex Fourier components when it is used. Thus, if you are using real input data, it must be paired with a 0 imaginary part: this is done "invisibly" for you in the software.