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

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