2
$\begingroup$

Lookup tables are one way to map x values to f(x) values. This lets you do computation in advance, and can give a low cost (performance wise) answer to complex calculations when they are needed in performance intensive applications.

Another method to map x values to f(x) values is to use the chinese remainder theorem to encode values into a (often large) number and use modulus to get the values back out

For instance, if the modulus "lookup table" was the number 27, it could encode the values 2,1,0 by using divisors 5,2,3 respectively:

$\begin{array}{c|c} \text{Input (x)} & \text{Math} & \text{Output (f(x))} \\ \hline 0 & 27 \% 5 & 2 \\ 1 & 27 \% 2 & 1 \\ 2 & 27 \% 3 & 0 \\ \end{array} $

(More info on that technique here: http://blog.demofox.org/2015/11/13/hiding-a-lookup-table-in-a-modulus-operation/)

The modulus method seems like it would always be slower and take more memory than a straight lookup table.

Is there a more efficient mapping of input values to output values than just using a table?

I'm interested mainly in efficiency of computation time to pull a result out of a mapping, but memory efficiency is also interesting, as well as efficiency in creating the object to begin with, if anyone has any interesting info on that.

Thanks!

$\endgroup$
2
$\begingroup$

From an asymptotic perspective: No, there's no more efficient mapping than just using a table. Lookup in a table is $O(1)$, and you can't beat $O(1)$.

From a practical perspective: The answer will depend upon the exact application domain. For instance, sometimes using a cache will speed up things (by only a constant factor, but in practice constant factors can help), if the access pattern exhibits some locality. It's impossible to give a general answer without knowing the specifics of the particular way you plan to use the lookup table.

However, no, you shouldn't expect there to be some clever number theory trick to build a faster lookup table. Roughly speaking, a lookup table is as fast as you can get; all that remains is some practical optimizations.


Memory efficiency is a different matter, and depends upon the function f. Sometimes it can be faster to compute f(x) from scratch than to look up x in the table. Sometimes, if you've previously computed f(x') and if x' is "close" to x, then you can efficiently compute f(x). It all depends on the function.

$\endgroup$
2
  • $\begingroup$ Thanks for the info. Do you happen to know off the top of your head if my assumption is true about the modulus situation? Will it always use more memory than a regular lookup table? Particularly just the number itself, not the co-prime keys to decode the values from the table. There could be a deterministic algorithm to derive though, such as Fermat Numbers which give O(1) lookup for a given index in an infinite list of co-primes (yes they get large quickly, but let's pretend they didnt!). $\endgroup$ – Alan Wolfe Nov 17 '15 at 0:59
  • $\begingroup$ @AlanWolfe, I didn't understand the specifics of what exactly you were proposing in detail, and I didn't read the external link, so I can't really comment on the specifics of that specific scheme. The answer will depend on exactly how the CRT is used. In general, with reasonable use of the CRT, the memory usage should be similar to that of a regular lookup table (asymptotically equivalent). Basically, the CRT looks cute but it doesn't really help: it doesn't reduce memory usage, it doesn't allow for faster lookups -- but on the upside, it doesn't need to make memory usage significantly worse. $\endgroup$ – D.W. Nov 17 '15 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.