Hacker News Reader

Comment by ThePhysicist | Hacker News Reader

I find the paper about beating O(n log n) for integer multiplication also quite fishy, not sure but it seems like too good to be true, I feel like there must be a subtle flaw in that. Maybe that's just me hating these small numbers in the paper, but it seems wrong, unnatural even! I would be similarly skeptical about a physics paper that claims to be able to exceed the speed of light by a tiny fraction. There's no reason n log n is the natural limit here but I see a few good intuitions so having something else that can't be represented in an elegant form seem very "unmathematical" to me.

View on HN

Yes i talked about that in a different thread here. It has fishy ‘assume we have a lookup table for x’ assumptions in it. These are relevant to the main body of the loop. The numbers it deals with are outside of any possible lookup table capability (not enough atoms in the universe for such a table).

The lean proof uses these assume ‘a lookup table’ assumptions. The paper smells with the nlogn^0.99999999 (many more nines actually) and unbelievably close to nlogn statement and then the literal talk of lookup tables pushes it over the edge clearly for me.

Maths can generate weird numbers out of nowhere but it really really looks like an nlogn result with some tricks to get past leen to me

If the table size is constant, no matter how large, then it is correct and important (even if useless; the existing n*log(n) algorithm is already useless).

I honestly think there’s a lot of fuzziness possible in complexity theory because of things like this. Yes you can skip some portions of a calculation and rightfully so by the current established formalisation of complexity theory but i think under another formalisation we’d probably see these nlogn^0.999999 cases become more clearly nlogn.

Cf. Blums speedup theorem for an extreme example of this

Just because something is proven and shown to be true doesn't mean that it's always practical.

The proof can be entirely valid even if it's not actually reasonable to implement and requires an enormous size lookup table - but it still is a meaningful mathematical result and makes progress.

I'm sure there are plenty of times where originally something was proven and thought to be completely impractical but then later had niche use cases or was the bedrock for solving other cases. And the opposite is true: there remain plenty of proofs of things that are mathematically certain but will in all practicality never be useful.

Exactly, big O doesn’t claim it’s actually faster in practice on a computer for all inputs

I'm not familiar with the paper you mention. But it's also worth pointing out that afaik the n log n algorithm itself isn't particularly practical. It's one of these "galactic algorithms" that is asymptotically more optimal, but is so complicated that it's only a real improvement for comically large n. And that's without even considering the mental overhead of implementing and maintaining the thing.

Of course, that's not to say the research is necessarily useless. It's still theoretically interesting to find "better" algorithms if only to shed some light on lower bounds, and so on. And who knows, maybe the line of research could lead to more practical algorithms later on.

it's worth clarifying that Fourier-based integer multiplication as a general class of algorithms are not galactic. For example, there are techniques that are competitive on some computing platforms for as few as 2048 bits, which occurs during RSA encryption

https://eprint.iacr.org/2022/439

this doesn't use the literal n \log n algorithm, which may be galactic. but it uses fundamentally similar techniques.

The whole point of that paper is to show that it's possible in principle. Now people (and AIs) can think of better algorithms, etc.

Regarding elegance, take a look at Graham's number. It was not some meaningful constant - it's just a big-ass number which could be used in existence proof. Human mathematicians have been using this approach for quite some time, it's not really AI doing things odd

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?

@SJ_Swapnil_Jain on X for announcements

repo - https://github.com/swapnil-jain/integer-mult-kappa

I'm no expert, but using multitape TM for this feels to me like a wrong level of abstraction. The whole thing has a lot of smell.

Well the lower bound has been lowered rather significantly since openai's initial proof.

Reply on news.ycombinator.com