Big O Speedrun
About

Integer multiplication

Multiply two nn-bit integers on a Turing machine with a fixed finite alphabet and a fixed number of one-dimensional tapes.

Classic bound: O(nlog⁡n)O(n \log n) (Harvey and van der Hoeven 2021).

The bound has the form O(nlog⁡1−κn)O(n \log^{1-\kappa} n). κ\kappa is the saving in the logarithmic exponent; higher is better.

RankBoundEvidence levelLevelPlayerDateLink
1O(nlog⁡1−7.510569198⋅10−4n)O(n \log^{1-7.510569198\cdot 10^{\scriptstyle -4}} n)ClaimedGeorge Lydakis @lydakisSourceGeorge Lydakis @lydakis
2O(nlog⁡1−7.499179316⋅10−4n)O(n \log^{1-7.499179316\cdot 10^{\scriptstyle -4}} n)Claimedrohanarun @ViewforgeSourcerohanarun @Viewforge
3O(nlog⁡1−7.498992153⋅10−4n)O(n \log^{1-7.498992153\cdot 10^{\scriptstyle -4}} n)Claimedchafreaky @cfky_Sourcechafreaky @cfky_
4O(nlog⁡1−7.467097209⋅10−4n)O(n \log^{1-7.467097209\cdot 10^{\scriptstyle -4}} n)Claimedchafreaky @cfky_Sourcechafreaky @cfky_
5O(nlog⁡1−7.455135731⋅10−4n)O(n \log^{1-7.455135731\cdot 10^{\scriptstyle -4}} n)Claimedchafreaky @cfky_Sourcechafreaky @cfky_
6O(nlog⁡1−7.452870346⋅10−4n)O(n \log^{1-7.452870346\cdot 10^{\scriptstyle -4}} n)Claimedrohanarun @ViewforgeSourcerohanarun @Viewforge
7O(nlog⁡1−7.447286542⋅10−4n)O(n \log^{1-7.447286542\cdot 10^{\scriptstyle -4}} n)ClaimedZhihao ChenSourceZhihao Chen
8O(nlog⁡1−7.447286502⋅10−4n)O(n \log^{1-7.447286502\cdot 10^{\scriptstyle -4}} n)Claimedrohanarun @ViewforgeSourcerohanarun @Viewforge
9O(nlog⁡1−7.447198826⋅10−4n)O(n \log^{1-7.447198826\cdot 10^{\scriptstyle -4}} n)Claimedsannidhi-hemanthSourcesannidhi-hemanth
10O(nlog⁡1−7.447144996⋅10−4n)O(n \log^{1-7.447144996\cdot 10^{\scriptstyle -4}} n)ClaimedMuhammed Ali MehmoodSourceMuhammed Ali Mehmood

κ\kappa in O(nlog⁡1−κn)O(n \log^{1-\kappa} n), higher is betterκ\kappa in O(nlog⁡1−κn)O(n \log^{1-\kappa} n)log scale, higher is better

ClaimedHuman VerifiedLean Verified
First breakthrough
κ\kappa (log scale)
κ=1: O(n)\kappa=1:\ O(n)

Relevant repos