Incomputer science, alookup table (LUT) is anarray that replacesruntime computation of a mathematicalfunction with a simpler array indexing operation, in a process termed asdirect addressing. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation orinput/output operation.[1] The tables may beprecalculated and stored instatic 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 fromhash tables in a way that, to retrieve a value with key, a hash table would store the value in the slot where is ahash function i.e. is used to compute the slot, while in the case of LUT, the value is stored in slot, thus directly addressable.[2]: 466
Before the advent of computers, lookup tables of values were used to speed up hand calculations of complex functions, such as intrigonometry,logarithms, and statistical density functions.[3]
In ancient (499 AD) India,Aryabhata created one of the firstsine tables, which he encoded in a Sanskrit-letter-based number system. In 493 AD,Victorius of Aquitaine wrote a 98-column multiplication table which gave (inRoman 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"[4] 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).
Early in the history of computers,input/output operations were particularly slow – even in comparison to processor speeds of the time. It made sense to reduce expensive read operations by a form of manualcaching by creating either static lookup tables (embedded in the program) or dynamic prefetched arrays to contain only the most commonly occurring data items. Despite the introduction of systemwide caching that now automates this process, application level lookup tables can still improve performance for data items that rarely, if ever, change.
Lookup tables were one of the earliest functionalities implemented in computerspreadsheets, with the initial version ofVisiCalc (1979) including aLOOKUP
function among its original 20 functions.[5] This has been followed by subsequent spreadsheets, such asMicrosoft Excel, and complemented by specializedVLOOKUP
andHLOOKUP
functions to simplify lookup in a vertical or horizontal table. In Microsoft Excel theXLOOKUP
function has been rolled out starting 28 August 2019.
Although the performance of a LUT is a guaranteed for a lookup operation, no two entities or values can have the same key. When the size ofuniverse—where the keys are drawn—is large, it might be impractical or impossible to be stored inmemory. Hence, in this case, ahash table would be a preferable alternative.[2]: 468
For atrivial hash function lookup, the unsignedraw data value is useddirectly as an index to a one-dimensional table to extract a result. For small ranges, this can be amongst the fastest lookup, even exceeding binary search speed with zero branches and executing inconstant time.[6]
One discrete problem that is expensive to solve on many computers is that of counting the number of bits that are set to 1 in a (binary) number, sometimes called thepopulation function. For example, the decimal number "37" is "00100101" in binary, so it contains three bits that are set to binary "1".[7]: 282
A simple example ofC code, designed to count the 1 bits in aint, might look like this:[7]: 283
intcount_ones(unsignedintx){intresult=0;while(x!=0){x=x&(x-1);result++;}returnresult;}
The above implementation requires 32 operations for an evaluation of a 32-bit value, which can potentially take severalclock cycles due tobranching. It can be "unrolled" into a lookup table which in turn usestrivial hash function for better performance.[7]: 282-283
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 aruntime algorithm can be used to generate thebits_set array, it's an inefficient usage of clock cycles when the size is taken into consideration, hence a precomputed table is used—although acompile time script could be used to dynamically generate and append the table to thesource file. Sum of ones in each byte of theinteger can be calculated throughtrivial hash function lookup on each byte; thus, effectively avoiding branches resulting in considerable improvement in performance.[7]: 284
intcount_ones(intinput_value){unionfour_bytes{intbig_int;chareach_byte[4];}operand=input_value;constintbits_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]]);}}
![]() | This sectionpossibly containsoriginal research. Pleaseimprove it byverifying the claims made and addinginline citations. Statements consisting only of original research should be removed.(October 2021) (Learn how and when to remove this message) |
"Lookup tables (LUTs) are an excellent technique for optimizing the evaluation of functions that are expensive to compute and inexpensive to cache. ... For data requests that fall between the table's samples, an interpolation algorithm can generate reasonable approximations by averaging nearby samples."[8]
In data analysis applications, such asimage processing, a lookup table (LUT) can be used to transform the input data into a more desirable output format. For example, a grayscale picture of the planet Saturn could be transformed into a color image to emphasize the differences in its rings.
In image processing, lookup tables are often calledLUTs (or 3DLUT), and give an output value for each of a range of index values. One common LUT, called thecolormap orpalette, is used to determine the colors and intensity values with which a particular image will be displayed. Incomputed tomography, "windowing" refers to a related concept for determining how to display the intensity of measured radiation.
![]() | This sectionpossibly containsoriginal research. Pleaseimprove it byverifying the claims made and addinginline citations. Statements consisting only of original research should be removed.(October 2021) (Learn how and when to remove this message) |
A classic example of reducing run-time computations using lookup tables is to obtain the result of atrigonometry calculation, such as thesine of a value.[9] 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 interpolate to the sine of the desired value, instead of calculating by mathematical formula. Lookup tables can thus used by mathematicscoprocessors in computer systems. An error in a lookup table was responsible for Intel's infamousfloating-point divide bug.
Functions of a single variable (such as sine and cosine) may be implemented by a simple array. Functions involving two or more variables require multidimensional array indexing techniques. The latter case may thus employ a two-dimensional array ofpower[x][y] to replace a function to calculatexy for a limited range of x and y values. Functions that have more than one result may be implemented with lookup tables that are arrays of structures.
As mentioned, there are intermediate solutions that use tables in combination with a small amount of computation, often usinginterpolation. Pre-calculation combined with interpolation can produce higher accuracy for values that fall between two precomputed values. This technique requires slightly more time to be performed but can greatly enhance accuracy in applications that require it. Depending on the values being precomputed,precomputation with interpolation can also be used to shrink the lookup table size while maintaining accuracy.
While often effective, employing a lookup table may nevertheless result in a severe penalty if the computation that the LUT replaces is relatively simple. Memory retrieval time and the complexity of memory requirements can increase application operation time and system complexity relative to what would be required by straight formula computation. The possibility ofpolluting the cache may also become a problem. Table accesses for large tables will almost certainly cause acache miss. This phenomenon is increasingly becoming an issue as processors outpace memory. A similar issue appears inrematerialization, acompiler optimization. In some environments, such as theJava programming language, table lookups can be even more expensive due to mandatory bounds-checking involving an additional comparison and branch for each lookup.
There are two fundamental limitations on when it is possible to construct a lookup table for a required operation. One is the amount of memory that is available: one cannot construct a lookup table larger than the space available for the table, although it is possible to construct disk-based lookup tables at the expense of lookup time. The other is the time required to compute the table values in the first instance; although this usually needs to be done only once, if it takes a prohibitively long time, it may make the use of a lookup table an inappropriate solution. As previously stated however, tables can be statically defined in many cases.
Most computers only perform basic arithmetic operations and cannot directly calculate thesine of a given value. Instead, they use theCORDIC algorithm or a complex formula such as the followingTaylor series to compute the value of sine to a high degree of precision:[10]: 5
However, this can be expensive to compute, especially on slow processors, and there are many applications, particularly in traditionalcomputer graphics, that need to compute many thousands of sine values every second. A common solution is to initially compute the sine of many evenly distributed values, and then to find the sine ofx we choose the sine of the value closest tox through array indexing operation. This will be close to the correct value because sine is acontinuous function with a bounded rate of change.[10]: 6 For example:[11]: 545–548
realarraysine_table[-1000..1000]forxfrom-1000to1000sine_table[x]=sine(pi*x/1000)functionlookup_sine(x)returnsine_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 islinear 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 forsmooth functions such as the sine function. Here is an example using linear interpolation:
functionlookup_sine(x)x1=floor(x*1000/pi)y1=sine_table[x1]y2=sine_table[x1+1]returny1+(y2-y1)*(x*1000/pi-x1)
Linear interpolation provides for an interpolated function that is continuous, but will not, in general, have continuousderivatives. For smoother interpolation of table lookup that is continuousand has continuousfirst derivative, one should use thecubic Hermite spline.
When using interpolation, the size of the lookup table can be reduced by usingnonuniform 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, seeinterpolation.
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 sub-range of bits composing an external memory (or disk) address (notably the lowest bits of any possible external address):
A single (fast) lookup is performed to read the tag in the lookup table at the index specified by the lowest bits of the desired external storage address, and to determine if the memory address is hit by the cache. When a hit is found, no access to external memory is needed (except for write operations, where the cached value may need to be updated asynchronously to the slower memory after some time, or if the position in the cache must be replaced to cache another address).
Indigital logic, a lookup table can be implemented with amultiplexer whose select lines are driven by the address signal and whose inputs are the values of the elements contained in the array. These values can either be hard-wired, as in anASIC whose purpose is specific to a function, or provided byD latches which allow for configurable values. (ROM,EPROM,EEPROM, orRAM.)
Ann-bit LUT can encode anyn-inputBoolean function by storing thetruth table of the function in the LUT. This is an efficient way of encodingBoolean logic functions, and LUTs with 4-6 bits of input are in fact the key component of modernfield-programmable gate arrays (FPGAs) which provide reconfigurable hardware logic capabilities.
Indata acquisition andcontrol systems, lookup tables are commonly used to undertake the following operations in:
In some systems,polynomials may also be defined in place of lookup tables for these calculations.
{{cite web}}
: CS1 maint: multiple names: authors list (link)