The Fast Fourier Transform (FFT) is a cornerstone of digital signal processing, reducing the naïve O(n²) computation of frequency spectra to O(n log n) operations. A recent Hacker News post highlighted an OpenAI manuscript claiming to have devised an even faster Fourier transform. Ben Recht's article on the arg min blog directly examines this claim, explaining what the OpenAI paper actually asserts and why it doesn't represent a practical advancement for real-world applications.
Recht notes that the OpenAI paper claims an asymptotic improvement over the Cooley-Tukey FFT, shaving a minuscule amount off the logarithmic factor in the running time bound. While this is expressed in big-O notation as technically faster, the paper provides no concrete constant factors for ordinary input sizes. Recht's analysis reveals that the alleged speedup exists only in a theoretical model that assumes exact complex arithmetic with unlimited precision. In this model, the magnitudes of the complex numbers grow super-polynomially with the input length, meaning that storing or multiplying these numbers would require exponential memory resources.
When the hidden constants are made explicit, the OpenAI algorithm becomes what computer scientists call a 'galactic algorithm': its running time is O(n log n) but with a constant on the order of 10^100 or larger. For perspective, even when n is as large as 10^100, the classic Cooley-Tukey-Gauss FFT would be about 10^99 times faster. Thus the new method offers no practical advantage for any conceivable signal-processing application; it is only asymptotically better in a model that bears no resemblance to real computers. Recht concludes that while such galactic results may inspire further research, they do not yield usable algorithms for engineers or scientists working with actual hardware.
This image supports the discussion of the algorithm's impractical constant factor in the theoretical model described in the article.