OpenAI's 'Faster' FFT Runs on Galactic Constants — SkimNews
Get the Tech newsletter
Daily tech — startups, AI labs, chips, the launches that shape the next decade. Free.
- OpenAI released a mathematics paper claiming a faster FFT algorithm, but blogger "argmin" reports the hidden constant is estimated at 10^100 when n=10^12, making the standard Cooley-Tukey FFT roughly 10^99 times faster at practical sizes.
- The OpenAI paper's computational model assumes exact complex arithmetic at arbitrary precision, requiring complex numbers whose magnitudes grow superpolynomially with n — effectively requiring exponential memory if stored as bits, the blog notes.
- Prior theoretical work already constrains what an FFT can do: Jacques Morgenstern proved in 1973 that bounded-magnitude complex coefficients cannot beat ½n log n, and Nir Ailon later showed n log n requires severe numerical instabilities, per the blog.
- OpenAI's wider paper dump also includes a galactic O(n^2.25) matrix multiplication result that shares the same pattern — asymptotically faster but detached from any model of real computers, the author writes.
- The Cooley-Tukey FFT (1965, with earlier credit to Gauss in 1805) runs in roughly 5n log₂ n operations versus n² naively, a 20-fold speedup at n=1,000 and 10,000-fold at n=1,000,000 — the benchmark the new result must beat.
- The author used ChatGPT itself to interrogate OpenAI's math repository, describing the experience as "doing mathematical research" by feeding AI slop back into the slop machine to extract salient facts.
Why it matters: The critique reframes OpenAI's high-profile math release from a "breakthrough" into an artifact of asymptotic formalism detached from real computation — a discipline-wide pattern where "linear time" can mean anything from 50n to 10^80n. If taken seriously by hiring committees or publication venues, galactic-algorithm results could divert research effort toward proofs that are technically true but functionally irrelevant to actually running code.
Ask SkimNews
