Comment by kolinko
4 hours ago
I didn’t read the paper but can’t this just be additionally with doing the actual muls? Or was it a nonconstructive proof?
4 hours ago
I didn’t read the paper but can’t this just be additionally with doing the actual muls? Or was it a nonconstructive proof?
Surely it's a galactic algorithm that you can't physically run? You wouldn't get a constant as small as 2^{-182} without some other numbers elsewhere being incredibly large.
From the "Introduction" section of that paper: "The constants and thresholds in the construction are extremely large".
(And verifying if the algorithm multiplies correctly or not is the less-interesting part of this, anyway. Gets you no closer to verifying the complexity result).
Isn't it possible that all of the integers that have been or will ever be encountered, anywhere, any time, in human history, number less than 2^182? In which case you could argue that integer multiplication is O(1) via LUT :)
Everything is a lookup table in non-standard arithmetic but that's not useful for someone writing the code b/c they don't have access to non-standard integers & have to write an algorithm to reconstruct it.
someone else picked up that bit of math and has run with it and has refined it downwards multiple times. believe it is now in the range of 2^-18 or so
Where?
1 reply →