x.com/bigospeedrun/status/2111251443994820914
1 correction found
O(n log^(1 - 0.1) n)
The reported exponent saving is wrong by about two orders of magnitude. Gonzalo Mier’s claimed bound was around κ = 0.001729776..., so the form was O(n log^(1-0.001729776...) n), not O(n log^(1-0.1) n).
Full reasoning
The post says the new integer-multiplication bound is O(n log^(1 - 0.1) n), i.e. an exponent of 0.9 on the logarithm. But the underlying claim associated with Gonzalo Mier gives a much smaller saving: κ = 0.0017297760894051203342..., which corresponds to O(n log^(1-0.001729776...) n).
Two independent sources on the same claim contradict the 0.1 figure:
- Big O Speedrun's integer multiplication leaderboard lists Gonzalo Mier with the bound
O(n log^(1-1.7297760894051203342·10^-3) n)and marks it as Claimed. - Gonzalo Mier's pull request #3143 states explicitly:
C40 = 0.0017297760894051203342384678198935738683and thenκ = ... = 0.0017297760894051203342384678198935738683....
So the post appears to have replaced 0.0017... with 0.1, which materially changes the asymptotic claim. 0.1 would mean a vastly larger improvement than the one actually claimed.
2 sources
- Integer Multiplication · Big O Speedrun
Gonzalo Mier ... O(n log^(1-1.7297760894051203342·10^-3) n) ... Claimed
- research(rank7): certify precision-40 κ above PR3133 by Gonzalo-Mier · Pull Request #3143
The 40-digit certified root endpoint is C40 = 0.0017297760894051203342384678198935738683; κ = ... = 0.0017297760894051203342384678198935738683...