I didn’t read the paper but can’t this just be additionally with doing the actual muls? Or was it a nonconstructive proof?

▲

peri-cl 6 hours ago | parent [-]

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).

▲

hyperbovine 6 hours ago | parent | next [-]

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 :)

	▲	measurablefunc 4 hours ago \| parent [-]
		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.

▲

auspiv 6 hours ago | parent | prev [-]

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

▲

throwaway198846 5 hours ago | parent [-]

Where?

	▲	auspiv 4 hours ago \| parent [-]
		@SJ_Swapnil_Jain on X for announcements repo - https://github.com/swapnil-jain/integer-mult-kappa