lookup table

Uses your system voice; voice and rate in settings.

Q690265Snapshot

≈ 7 min read

Names in other languages

  • Françaistable de correspondance
  • Españoltabla de consulta
  • DeutschLookup-Tabelle
  • calookup table
  • ČeštinaLookup table
  • Englishlookup table
  • etOtsingutabel
  • PolskiTablicowanie

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, a lookup table (LUT) is an array that replaces runtime computation of a mathematical function with a simpler array indexing operation, in a process termed as direct addressing. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation or input/output operation. The tables may be precalculated and stored in static program storage, calculated (or "pre-fetched") as part of a program's initialization phase (memoization ), or even stored in hardware in application-specific platforms. Lookup tables are also used extensively to validate input values by matching against a list of valid (or invalid) items in an array and, in some programming languages, may include pointer functions (or offsets to labels) to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality. LUTs differ from hash tables in that, to retrieve a value v with key k , a hash table would store the value v in the slot h(k) where h is a hash function i.e. k is used to compute the slot, while in the case of LUT, the value v is stored in slot k , thus directly addressable.

In computer science, a lookup table (LUT) is an array that replaces runtime computation of a mathematical function with a simpler array indexing operation, in a process termed as direct addressing. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation or input/output operation. The tables may be precalculated and stored in static program storage, calculated (or "pre-fetched") as part of a program's initialization phase (memoization ), or even stored in hardware in application-specific platforms. Lookup tables are also used extensively to validate input values by matching against a list of valid (or invalid) items in an array and, in some programming languages, may include pointer functions (or offsets to labels) to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality. LUTs differ from hash tables in that, to retrieve a value v with key k , a hash table would store the value v in the slot h(k) where h is a hash function i.e. k is used to compute the slot, while in the case of LUT, the value v is stored in slot k , thus directly addressable. int count_ones(unsigned int x) { int result = 0; while (x != 0) { x = x & (x - 1); result++; } return result; } The above implementation requires 32 operations for an evaluation of a 32-bit value, which can potentially take several clock cycles due to branching. It can be "unrolled" into a lookup table which in turn uses trivial hash function for better performance. The bits array, bits_set with 256 entries is constructed by giving the number of one bits set in each possible byte value (e.g. 0x00 = 0, 0x01 = 1, 0x02 = 1, and so on). Although a runtime algorithm can be used to generate the bits_set array, it's an inefficient usage of clock cycles when the size is taken into consideration, hence a precomputed table is used—although a compile time script could be used to dynamically generate and append the table to the source file. Sum of ones in each byte of the integer can be calculated through trivial hash function lookup on each byte; thus, effectively avoiding branches resulting in considerable improvement in performance. int count_ones(int input_value) { union four_bytes { int big_int; char each_byte[4]; } operand = input_value; const int bits_set[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}; return (bits_set[operand.each_byte[0 + bits_set[operand.each_byte[1 + bits_set[operand.each_byte[2 + bits_set[operand.each_byte[3 ); }} 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)] Unfortunately, the table requires quite a bit of space: if IEEE double-precision floating-point numbers are used, over 16,000 bytes would be required. We can use fewer samples, but then our precision will significantly worsen. One good solution is linear interpolation, which draws a line between the two points in the table on either side of the value and locates the answer on that line. This is still quick to compute, and much more accurate for smooth functions such as the sine function. Here is an example using linear interpolation: function lookup_sine(x) x1 = floor(x * 1000 / pi) y1 = sine_table[x1] y2 = sine_table[x1 + 1] return y1 + (y2 - y1) * (x * 1000 / pi - x1) Linear interpolation provides for an interpolated function that is continuous, but will not, in general, have continuous derivatives. For smoother interpolation of table lookup that is continuous and has continuous first derivative, one should use the cubic Hermite spline. When using interpolation, the size of the lookup table can be reduced by using nonuniform sampling, which means that where the function is close to straight, we use few sample points, while where it changes value quickly we use more sample points to keep the approximation close to the real curve. For more information, see interpolation.

See also

Associative array Branch table Gal's accurate tables Memoization Memory-bound function Nearest-neighbor interpolation Shift register lookup table Palette, a.k.a. color lookup table or CLUT – for the usage in computer graphics 3D lookup table – usage in film industry

References

External links

Fast table lookup using input character as index for branch table Art of Assembly: Calculation via Table Lookups "Bit Twiddling Hacks" (includes lookup tables) By Sean Eron Anderson of Stanford University Memoization in C++ by Paul McNamee, Johns Hopkins University showing savings "The Quest for an Accelerated Population Count" by Henry S. Warren Jr.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354092035 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.