set of data points, for example a periodic sampling taken from
a real-world signal, the FFT expresses the data in terms of
its component frequencies. It also solves the essentially
identical inverse problem of reconstructing a signal from the
frequency data.
described it as "the most important algorithm of our
generation". The FFT also provides the asymptotically fastest
Versions of the algorithm (in
C and
Fortran) can be found
["Numerical Methods and Analysis", Buchanan and Turner].
(1994-11-09)