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.51056⋅10−4n)O(n \log^{1-7.51056\cdot 10^{\scriptstyle -4}} n)ClaimedlydakisSourcelydakis
2O(nlog⁡1−7.49917⋅10−4n)O(n \log^{1-7.49917\cdot 10^{\scriptstyle -4}} n)ClaimedrohanarunSourcerohanarun
3O(nlog⁡1−7.49899⋅10−4n)O(n \log^{1-7.49899\cdot 10^{\scriptstyle -4}} n)ClaimedchafreakySourcechafreaky
4O(nlog⁡1−7.46709⋅10−4n)O(n \log^{1-7.46709\cdot 10^{\scriptstyle -4}} n)ClaimedchafreakySourcechafreaky
5O(nlog⁡1−7.45513⋅10−4n)O(n \log^{1-7.45513\cdot 10^{\scriptstyle -4}} n)ClaimedchafreakySourcechafreaky
6O(nlog⁡1−7.45287⋅10−4n)O(n \log^{1-7.45287\cdot 10^{\scriptstyle -4}} n)ClaimedrohanarunSourcerohanarun
7O(nlog⁡1−7.44728⋅10−4n)O(n \log^{1-7.44728\cdot 10^{\scriptstyle -4}} n)ClaimedjacklightChenSourcejacklightChen
8O(nlog⁡1−7.44728⋅10−4n)O(n \log^{1-7.44728\cdot 10^{\scriptstyle -4}} n)ClaimedrohanarunSourcerohanarun
9O(nlog⁡1−7.44719⋅10−4n)O(n \log^{1-7.44719\cdot 10^{\scriptstyle -4}} n)Claimedsannidhi-hemanthSourcesannidhi-hemanth
10O(nlog⁡1−7.44714⋅10−4n)O(n \log^{1-7.44714\cdot 10^{\scriptstyle -4}} n)ClaimedM6LISourceM6LI

κ\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