Peter Caeldries

60 years ago this month, the Fast Fourier Transform (FFT) was introduced by Cooley & Tukey (1965) - one of the most important algorithms in signal processing and data analysis. In 1805, Gauss - studying the orbits of asteroids Pallas and Juno - came up with a method to interpolate their trajectories from discrete samples. What he came up with was mathematically very close to the modern FFT but Gauss never published that work, and didn’t analyze its computational complexity. It predated even Fourier’s 1822 work on heat diffusion - but without the framing or generalization that Cooley & Tukey would bring 160 years later. In 1965, Cooley & Tukey published their now-famous algorithm that reduced the cost of computing a Discrete Fourier Transform from 𝑂(𝑛²) to 𝑂(𝑛 log⁡𝑛). This leap made real-time signal processing and digital media compression feasible. From radio telescopes to JPEGs, from audio codecs to quantum mechanics - the FFT is everywhere. It’s one of the most important (and elegant) algorithms of the 20th century - rooted in the genius of Gauss, but brought to life in the computer age.