Lookup table

From Wikipedia, the free encyclopedia
  (Redirected from Table (computing))
Jump to: navigation, search





In ancient (499 CE) India, Aryabhata created one of the first sine tables, which he encoded in a Sanskrit-letter-based number system. In 493 A.D., Victorius of Aquitaine wrote a 98-column multiplication table which gave (in Roman numerals) the product of every number from 2 to 50 times and the rows were "a list of numbers starting with one thousand, descending by hundreds to one hundred, then descending by tens to ten, then by ones to one, and then the fractions down to 1/144" [3] Modern school children are often taught to memorize "times tables" to avoid calculations of the most commonly used numbers (up to 9 x 9 or 12 x 12).



Simple lookup in an array, an associative array or a linked list (unsorted list)[edit]

This is known as a linear search or brute-force search, each element being checked for equality in turn and the associated value, if any, used as a result of the search. This is often the slowest search method unless frequently occurring values occur early in the list. For a one-dimensional array or linked list, the lookup is usually to determine whether or not there is a match with an 'input' data value.

Binary search in an array or an associative array (sorted list)[edit]

An example of a "divide and conquer algorithm", binary search involves each element being found by determining which half of the table a match may be found in and repeating until either success or failure. Only possible if the list is sorted but gives good performance even if the list is lengthy.

Trivial hash function[edit]


Counting bits in a series of bytes[edit]

One discrete problem that is expensive to solve on many computers, is that of counting the number of bits which are set to 1 in a (binary) number, sometimes called the population function. For example, the decimal number "37" is "00100101" in binary, so it contains three bits that are set to binary "1".


int count_ones(unsigned int x) {
    int result = 0;
    while (x != 0)
        result++, x = x & (x-1);
    return result;

This apparently simple algorithm can take potentially hundreds of cycles even on a modern architecture, because it makes many branches in the loop - and branching is slow. This can be ameliorated using loop unrolling and some other compiler optimizations. There is however a simple and much faster algorithmic solution - using a trivial hash function table lookup.

Simply construct a static table, bits_set, with 256 entries giving the number of one bits set in each possible byte value (e.g. 0x00 = 0, 0x01 = 1, 0x02 = 1, and so on). Then use this table to find the number of ones in each byte of the integer using a trivial hash function lookup on each byte in turn, and sum them. This requires no branches, and just four indexed memory accesses, considerably faster than the earlier code.

 /* (this code assumes that 'int' is 32-bits wide) */
 int count_ones(unsigned int x) {
    return bits_set[ x        & 255] + bits_set[(x >>  8) & 255]
         + bits_set[(x >> 16) & 255] + bits_set[(x >> 24) & 255];

The above source can be improved easily, (avoiding AND'ing, and shifting) by 'recasting' 'x' as a 4 byte unsigned char array and, preferably, coded in-line as a single statement instead of being a function. Note that even this simple algorithm can be too slow now, because the original code might run faster from the cache of modern processors, and (large) lookup tables do not fit well in caches and can cause a slower access to memory (in addition, in the above example, it requires computing addresses within a table, to perform the four lookups needed).

Lookup tables in image processing[edit]


A classic example of reducing run-time computations using lookup tables is to obtain the result of a trigonometry calculation, such as the sine of a value. Calculating trigonometric functions can substantially slow a computing application. The same application can finish much sooner when it first precalculates the sine of a number of values, for example for each whole number of degrees (The table can be defined as static variables at compile time, reducing repeated run time costs). When the program requires the sine of a value, it can use the lookup table to retrieve the closest sine value from a memory address, and may also take the step of interpolating to the sine of the desired value, instead of calculating by mathematical formula. Lookup tables are thus used by mathematics co-processors in computer systems. An error in a lookup table was responsible for Intel's infamous floating-point divide bug.






Computing sines[edit]

Most computers, which only perform basic arithmetic operations, cannot directly calculate the sine of a given value. Instead, they use the CORDIC algorithm or a complex formula such as the following Taylor series to compute the value of sine to a high degree of precision:

\operatorname{sin}(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040} (for x close to 0)


 real array sine_table[-1000..1000]
 for x from -1000 to 1000
     sine_table[x] := sine(pi * x / 1000)
 function lookup_sine(x)
     return sine_table[round(1000 * x / pi)]
Linear interpolation on a portion of the sine function


 function lookup_sine(x)
     x1 := floor(x*1000/pi)
     y1 := sine_table[x1]
     y2 := sine_table[x1+1]


 function init_sine()
     for x from 0 to (360/4)+1
         sine_table[x] := sine(2*pi * x / 360)
 function lookup_sine(x)
     x  = wrap x from 0 to 360
     y := mod (x, 90)
     if (x <  90) return  sine_table[   y]
     if (x < 270) return -sine_table[   y]
                  return -sine_table[90-y]
 function lookup_cosine(x)
     return lookup_sine(x + 90)
 function lookup_tan(x)
     return (lookup_sine(x) / lookup_cosine(x))


Other usage of lookup tables[edit]


Main article: Cache (computing)

Storage caches (including disk caches for files, or processor caches for either code or data) work also like a lookup table. The table is built with very fast memory instead of being stored on slower external memory, and maintains two pieces of data for a subrange of bits composing an external memory (or disk) address (notably the lowest bits of any possible external address):

  • the other piece maintains the data associated to that address.


Hardware LUTs[edit]


See also[edit]


  1. ^ http://apl.jhu.edu/~paulmac/c++-memoization.html
  2. ^ Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, eds. (October 2, 2003) [2003]. The History of Mathematical Tables From Sumer to Spreadsheets (1st ed.). New York, USA. ISBN 978-0-19-850841-0. 

External links[edit]