A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform of a sequence, or its inverse, converting a signal between its original domain, often time or space, and a representation in the frequency domain. It works by factorizing the discrete Fourier transform's matrix into a product of mostly-zero, sparse factors, which reduces the computational cost of the transform from O(n squared), the cost of applying the definition directly, to O(n log n). The ideas underlying it date as far back as an unpublished 1805 method by Carl Friedrich Gauss, but the algorithm was popularized in its modern form in 1965 by James Cooley and John Tukey. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(n log n), versus O(n squared) for direct evaluation of the discrete Fourier transform. 1 Credited ToBasic ideas trace to an unpublished 1805 method by Carl Friedrich Gauss; popularized in modern form by James Cooley and John Tukey in 1965. 1 Connections
Invented By
Verified en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm: "Cooley and Tukey subsequently published their joint paper" introducing the modern Cooley-Tukey Fast Fourier Transform algorithm.
Verified en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm: "Cooley and Tukey subsequently published their joint paper" introducing the modern Cooley-Tukey Fast Fourier Transform algorithm.
Sources
1. Wikipedia: Fast Fourier Transform
Wikimedia FoundationLead section
from O(n^2), which arises if one simply applies the definition of DFT, to O(n log n), where n is the length of the sequence
Body, history
The basic ideas were popularized in 1965 by James Cooley and John Tukey, though earlier algorithms dated back to 1805 by Carl Friedrich Gauss.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.