An algorithm for computing the DiscreteFourierTransform in O(n log n) time, as opposed to the naive O(n^2) algorithm. See http://www.wikipedia.org/wiki/Fast_Fourier_transform

See also: FourierTransform, FourierAnalysis, ComplexFourierSeries, PeriodicFunction

Note that the FFT is an algorithm, not the transform. You don't calculate the FFT, you use the FFT to calculate the FT. This is a common mistake, and among people who understand these things makes you look ignorant, sometimes stupid, even if you're simply inexperienced.

EditText of this page (last edited May 22, 2008) or FindPage with title or text search