Whether you prove them to yourself or take my word for them the
formulas given above should be enough for you to follow what the
routine fftc1 does. The first section takes an array of points and
rearranges them into bit-reversed order. This is done by noting that
if you know the bit-reversal
of a binary number
it is easy
to find the bit-reversal
of the number
. To add
to
you start at the right and replace every
with a
until you
reach the first
, which you replace with a
. So to go from
to
you do the bit-reverse of this process, starting
at the left and replacing every
with a
until you reach the
first
, which you replace with a
.
The next part of the routine implements the DL formula on successively
larger blocks, beginning with combining transforms into
transforms. Each time the routine calculates a transform of size
the first
elements represent
and
the next half represent
. These are then used to calculate
and
. Note that in the DL formula
,
, and
, so the only difference between the
formulas for
and
is the sign of
. Finally, the inner loop over the variable
iterates over
all the transforms of size
in the entire array, so if
you are transforming an
array of data you first have to
calculate
transforms, then
transforms, and so on.
Note that the formulas for the real and imaginary parts of are
nothing but
and
. They could have
simply been calculated directly but for the sake of efficiency they
are calculated instead using a recursion formula each time
is
incremented. This formula can be verified simply using the addition
rules for sines and cosines.
Note that the end result of this process is a transform with the
results in sequential order from to
, which by the
periodicity of
is exactly the storage scheme described in
section 2.3.2.
The reverse transform is exactly identical except the sign of the
exponential is reversed and the final output is divided by .
The argument is used in case the elements of the input array
are not sequential but evenly spaced in some larger array. To do a
one-dimensional transform you would almost always want to set
to one, but this option allows fftc1 to be used by fftcn, which does
transforms of multi-dimensional arrays. For all but the last array
index the one-dimensional transforms used by fftcn are not of
sequential data.