These 4 programs are FORTRAN subroutines which do
Fourier Transforms by various methods.

DFT does a straight forward Discrete Fourier Transform -
The long way. You could call it a "Slow Fourier Transform".
It is useful to see the basis for some of the short cut
routines more commonly used.

FFT1 and FFT2 are typical Fast Fourier Transform
routines. They have the classical limitation of only working
on 2 to the nth power (2**n) points. You can add zeros to
the end of your data to get enough points. This has a minor
effect on the accuracy - see a reference book for more
details.

NFFT is a unique routine, and can be very useful,
especially if you don't know how many data points you will
have ahead of time. There is a classic misconception that
FFT algorithms only work for 2**n points. Not True! Any
number of points that can be factored into more than one
prime factor can be sped up considerably - 2**n is just the
fastest possible number. NFFT does this for you
automatically. It factors the number of data points and does
the FFT the fastest possible way - from a 2**n all the way
down to DFT speed. It is instructive to try different
numbers of data points and time them - for example, using
the same data, try 512 points, 500 points, and 499 points.

If you have comments or questions, let me know. A good
book on FFT's (and just the Fourier Transform) is the one by
E. Oran Brigham, "The Fast Fourier Transform", Prentice
Hall, 1974.

Bill Wittig
11215 Birmingham Ct.
St. Louis, MO 63138
SLHUG Fido 100/512