Doubting Knuth: why O(n) integer multiplication may not be the true lower bound
burny_tech · x · 2026-10-10
- Since 1979, Schönhage-Strassen has given O(n) integer multiplication in the Word RAM model, and Knuth's TAOCP declared fast multiplication "solved, except for constant-factor improvements."
- The author doubted that claim: with bit-packed inputs, reading the factors and writing the output takes only O(n/log n) words, and addition can match that bound — so linear time is not an obvious lower bound.
- If OpenAI's recent result holds up, it beats O(n), vindicating the skepticism of Knuth's conclusion.
More from Research
- Inferring goals from failure: online Bayesian goal inference for boundedly-rational agents — xuanalogue · 2026-10-11
- Alignment researcher points to Rohin Shah's value learning sequence and IRL model misspecification — xuanalogue · 2026-10-11
- Looped LM paper: 1.6B model matches full-cache baseline with 3x smaller KV cache — rupspace · 2026-10-11
- Pure RL discovers superhuman robot strategies in sim, transfers zero-shot to real hardware — KyleMorgenstein · 2026-10-11
- Softmax picks probabilities, cross-entropy picks the target: a 3-class walkthrough — techNmak · 2026-10-11
- PartLLM brings LLM-powered 3D mesh part segmentation to SIGGRAPH Asia with code released — Promptmethus · 2026-10-11