Fast Fourier Transform

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.

CategoryMath