Most Efficient Way to Map Generic Input To Generic Output 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)} &amp; \text{Math} &amp; \text{Output (f(x))} \\
\hline
0 &amp; 27 \% 5 &amp; 2 \\
1 &amp; 27 \% 2 &amp; 1 \\
2 &amp; 27 \% 3 &amp; 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!
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.