What's the True Complexity of Integer Multiplication? From n^2 to n log n, Guesses Keep Falling
felpix_ · x · 2026-10-08
A fun speculation thread on the true optimal time complexity of integer multiplication: is it Theta(n sqrt(log n))? The original poster notes history's lesson — Kolmogorov thought n^2, then Schönhage-Strassen suggested n log n — while a reply jokes the answer might be something absurd like n log n over nested logloglog terms.
More from Fun
- Developer builds agent-native Adobe clone, uses Opus 5.5 to reproduce original art — teortaxesTex · 2026-10-08
- Claude cracking down on underage users, screenshot sparks chatter — BecauseCulture · 2026-10-08
- Parody 'SpaceXAI CEO' account congratulates Anthropic on Haiku 5.5 — ns123abc · 2026-10-08
- OpenAI Employee's 'Humans Are Such Bummers' Remark Draws Mockery — GarrisonLovely · 2026-10-08
- From idea to working AI photo booth in 48 hours at Singapore DevDay afterparty — gabrielchua · 2026-10-08
- OpenAI Sora researcher to host Pilates networking night at COLM 2026 — mmmbchang · 2026-10-08