Hacker News Reader

Comment by cma | Hacker News Reader

Wouldn't it take an infinite lookup table to do this satisfying any two integers and still get an order-complexity speedup? The integers can be any size. You can't specify an arbitrarily variable sized lookup table in the normal formulation of these problems without computing the lookup table as part of the computation.

View on HN

You seem to under the impression that we don’t currently use lookup tables for multiplication.

But your right in that we don’t have a huge LUT as it’s not worth it.

Small one in the ALU though, for partial products to add can be worth the additional wire length.

I don't believe that changes asymptotic worst case order complexity for multiplication of arbitrary sized integers on its own, naively applied. That's not the same as saying it doesn't provide any speedup to them.

Never infinite if you have bounds on integer size. For n bits of input it's always possible to have a 2^n space complexity lookup table that's O(1) speed since 2^n covers all possibilities of n bits.

You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.

I think the thing non-mathematicians and non-CS people who only know complexity theory vaguely need to remember is that complexity theory has nothing to do with reality.

A 2^64bits lookup table only has O(1) lookup if you ignore the impossibility of creating a machine that has 2 exabytes of storage where all those bytes have the same access time. Or you'd have to redefine O(1) to be “at most the worst case”. But strictly speaking from the mathematical definition it’s O(1). Which is why no one in practical engineering takes most complexity results seriously as the entire field maps to practice poorly precisely for these reasons (all our machines use fixed integer math and have limited tape storage)

The whole point of this problem is that there are no bounds on integer size.

The whole point of complexity theory is that there are no bounds on input size.

Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite. Thats the end state of Blums speedup theorem in either direction and it doesn’t limit to any bounds. I just stating a limited of bounds above for the sake of giving understanding. Complexity theory doesn’t care that 2^n space complexity doesn’t work when n is infinite anymore than it cares that nlogn also doesn’t work when n is infinite. It’s not the point.

nah dude. i'll allow any finite size lookup table, but not an infinite one.

And yet you seem to allow an infinitely big operand

why do you accuse me of this? i'm deeply uncomfortable with that, as well. it's possible to object for multiple reasons.

no it doesn't. making the table takes O(2^n) time

Congrats, you just solved P=NP.

> Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite.

That's just incorrect. Are you assuming the table starts pre-filled, and has O(1) lookup? Nobody is using a model like that for this problem.

2^n space complexity doesn't automatically mean you get to fill that space with 2^n chosen computed values for free.

There's models with "oracle"s for various sub-problems and such (that's essentially what you're describing as the ability you're baking in to your model of computation, it can look up the answer to any multiplication for free), but that's not an interesting model for this problem.

If you do that you're just asking "hey, how long does it take to multiply two numbers if multiplying two numbers is free". Boring question, and not the one anyone else is asking.

for any fixed size, populating the lookup table is constant.

If it's 2^n size, you don't get to assume that filling it is O(1) or even O(n) in really any model unless it says that. That would be quite surprising when analysing this type of problem, because it makes anything about the problem _very_ boring, all the answers are just O(1) then, there's nothing to think or care about then.

2^n isn't a "fixed size" here.

Reply on news.ycombinator.com