Comment by CH-Abhinav
1 day ago
New here but how does this help in general? Most of the time we use GEMM over Strassen even though time complexity is lower. Just ask idk anything :)
1 day ago
New here but how does this help in general? Most of the time we use GEMM over Strassen even though time complexity is lower. Just ask idk anything :)
This is integer multiplication, not matrix multiplication. The OpenAI dump also has a matrix multiplication improvement though.
In either case, no practical algorithm is expected to come from it, because the asymptotic gain isn't realized for practical input sizes--sometimes called a "galactic algorithm". But it's theoretically very interesting for breaking through a conjectured barrier.
Not a mathematician, but I don't think there's any point to trying to put it in code at this point. Improvements seem to be coming rapidly at the moment.
it doesn't. it might if you're multiplying numbers in the thousands of digits (but even that is almost assuredly too low). for essentially everyone this is purely a theoretical result.
You're dramatically underestimating. You need something like 2^2^2^5000 digits or something crazy like that.
yes, but even the dramatic underestimate shows how useless it is. I also imagine that current estimates could be significantly optimized if there was some usecase for them. the 1k-10k multiplication regime has actual usecases, so there has been some optimized implementations of theoretical integer multiplication algorithms in this regime.