Algorithms Series of 5 82 min
On Multiplication
How multiplying big integers got faster: schoolbook n², Karatsuba, the FFT, n log n, and a 2026 preprint claiming to go lower.
Start with Vol. I 2025–2026
- I Schoolbook, Karatsuba, Toom-Cook Why schoolbook multiplication costs O(n²), how Karatsuba gets by with three half-size products, and how Toom-Cook generalizes the trick by interpolation.
- II The Fourier Transform Integer multiplication as convolution, the discrete Fourier transform, and how the Cooley-Tukey FFT computes it in O(N log N), with a worked 8-point example.
- III Schönhage-Strassen and Harvey-van der Hoeven Schönhage-Strassen multiplication modulo 2ᵐ + 1, where its log log n factor comes from, and how Harvey and van der Hoeven reached O(n log n) in 2019.
- IV Sorting and the Mirage of n log n Why comparison sorting's n log n lower bound is a theorem and integer multiplication's never was, though their fast algorithms share one recurrence.
- V Below n log n An unrefereed OpenAI preprint claims integer multiplication below n log n on a multitape Turing machine: how its swap gadget works and how far to trust it.