Fourier laboratory
An actual client-side DFT and radix-2 FFT, plus an honest look at the new theoretical bound. Offline-capable; no libraries or network requests.
The all-length theorem uses an exact chirp identity to reduce a general DFT to convolution on a convenient padded length. Here we verify that identity numerically for the selected input. This is not the finite tensor-saving network or the final faster algorithm.
Normalized curves: N², N log₂ N and N(log₂ N)^(1−10⁻¹³). These are shape comparisons, not measured runtime or paper-specific gate counts.
This demo implements the conventional radix-2 FFT, not the 2026 exact-arithmetic sub-N-log-N construction. The latter permits exact complex values, unrestricted prepared constants and a supplied root of unity; it does not promise a faster floating-point browser implementation. Its tiny exponent saving and large hidden constants mean the curves are nearly indistinguishable at realistic sizes.
Sources: OpenAI result #130, Lean scope. Counting conventions here: direct DFT uses N² complex products and N(N−1) sums; radix-2 butterfly FFT uses (N/2)log₂N twiddle products and Nlog₂N sums/subtractions. Trivial multiplications are included. Real JavaScript Number arithmetic is approximate.