The article examines OpenAI’s claim of a faster Fourier transform presented in their “main.pdf” paper. It notes that the classic Cooley‑Tukey FFT computes a length‑n discrete Fourier transform in fewer than 5 n log₂ n arithmetic operations, giving a 20‑fold speedup for n = 1 000 and a 10 000‑fold speedup for n = 1 000 000 compared with the naïve n² approach. OpenAI’s result is expressed in big‑O notation as O(n), but the hidden constant C is astronomically large—estimated at about 10¹⁰⁰ when the threshold N is 10¹²—making the algorithm slower than the Cooley‑Tukey method for any feasible input size. The analysis points out that the claimed speedup relies on an unrealistic model of computation that assumes exact complex arithmetic with arbitrarily large magnitudes, which would require exponential memory and operations not available on real hardware. Theoretical limits such as Morgenstern’s ½ n log n bound (under bounded‑magnitude coefficients) and Ailon’s n log n bound (without severe numerical instability) are cited to show that breaking the FFT barrier would require impractical assumptions. Consequently, the OpenAI contribution is characterized as a “galactic” algorithm: asymptotically faster in theory but irrelevant for practical signal‑processing applications.
Read original
hackernews