## Fast Fourier Transform

<*algorithm*> (FFT) An algorithm for computing the Fourier
transform of a set of discrete data values. Given a finite
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.

The FFT is a mainstay of numerical analysis. Gilbert Strang described it as "the most important algorithm of our generation". The FFT also provides the asymptotically fastest known algorithm for multiplying two polynomials.

Versions of the algorithm (in C and Fortran) can be found
on-line from the GAMS server *here*.

["Numerical Methods and Analysis", Buchanan and Turner].

Last updated: 1994-11-09

Try this search on Wikipedia, OneLook, Google

**Nearby terms:**

**Fast Fourier Transform**» Fast Packet » Fast Page Mode Dynamic Random Access Memory » Fast SCSI