Fast Fourier Transform (FFT)
An efficient algorithm for computing the discrete Fourier transform of a signal in O(N log N) time instead of O(N²) time, enabling rapid frequency decomposition of signals for applications like signal processing, compression, and detection
As defined in The Most Underrated Algorithm
Where it comes up · 1
- The Most Underrated Algorithm14 claims
Most important claims · 10 of 14Search all claims for “Fast Fourier Transform (FFT)” →
- The Fast Fourier Transform was actually discovered earlier than Cooley and Tukey—mathematician Carl Friedrich Gauss derived it in 1805 while studying the orbits of newly discovered asteroids Pallas, Ceres, and Juno.The Most Underrated Algorithm
- Richard Garwin approached IBM researcher James Cooley to program the FFT algorithm on a computer, but did not tell him the motivation was detecting covert Soviet nuclear tests; instead, Garwin claimed the purpose was to work out the spins in a crystal of helium-3.The Most Underrated Algorithm
- Richard Garwin, when asked about the counterfactual, said an earlier FFT discovery 'would've helped and it might have turned the tide,' validating the historical contingency argument.The Most Underrated Algorithm
- The Fast Fourier Transform is used ubiquitously in modern signal processing including video streaming, radar, sonar, 5G, and WiFi applications.The Most Underrated Algorithm
- Gauss's FFT algorithm was lost to history because it only appeared after his death in volume three of his collected works, and was written in non-standard notation in 19th-century Latin, making it inaccessible to later researchers.The Most Underrated Algorithm
- Cooley and Tukey published the Fast Fourier Transform algorithm in a seminal 1965 paper, and its use immediately took off across science and engineering.The Most Underrated Algorithm
- Image compression using FFT works by taking the pixel brightness values of each row of an image, performing FFT to determine which frequencies are present in the brightness values, and then performing another FFT for the columns of pixels (the order doesn't matter) to get a 2D FFT of the original image.The Most Underrated Algorithm
- The Fast Fourier Transform algorithm works by exploiting the periodic and overlapping nature of sinusoids: due to redundancy in the frequency wave computations, a calculation expecting to require 64 multiplications (8×8) can be reduced to only 24 multiplications.The Most Underrated Algorithm
- If Gauss's FFT algorithm had become widely adopted after his discovery in 1805, the FFT may have transformed our world even more dramatically than it has, as most people don't think about the cumulative impact of their life's work.The Most Underrated Algorithm
- If scientists had been confident in their ability to remotely detect underground nuclear tests in the early 1960s using FFT-level signal processing, then a comprehensive test ban could have been achieved, potentially stopping the nuclear arms race before it proliferated to 70,000 warheads.The Most Underrated Algorithm