alt Hacker NewsWouldn'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.
Replies
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.
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.