|
In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. The speed gain can be significant, since retrieving a value from memory is often faster than undergoing an expensive computation. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
A binary tree, a simple type of branching linked data structure. ...
In computer programming, a group of homogeneous elements of a specific data type is known as an array, one of the simplest data structures. ...
It has been suggested that Map (C++ container) be merged into this article or section. ...
A classic example is a trigonometry table. Calculating the sine of a value every time such a sine is needed can be prohibitively slow in some applications. To avoid this, the application can take a few seconds when it first starts to precalculate the sine of a number of values, for example for each whole number of degrees. Later, when the program wants the sine of a value, it uses the lookup table to retrieve the sine of a nearby value from a memory address instead of calculating it using a mathematical formula. Lookup tables are also used by math co-processors, and an error in a lookup table was responsible for Intel's infamous floating point bug. Wikibooks has a book on the topic of Trigonometry Trigonometry (from the Greek trigonon = three angles and metron = measure [1]) is a branch of mathematics which deals with triangles, particularly triangles in a plane where one angle of the triangle is 90 degrees (right triangles). ...
In mathematics, the trigonometric functions are functions of an angle, important when studying triangles and modeling periodic phenomena. ...
In mathematics, the trigonometric functions are functions of an angle, important when studying triangles and modeling periodic phenomena. ...
Before the advent of computers, similar tables were used by people to speed up hand calculations. Particularly prevalent were tables of values for trigonometry, logarithms, and statistical density functions.
There are intermediate solutions that use tables in combination with a small amount of computation, often using interpolation. This allows better accuracy for values falling between two precomputed values. This requires slightly more time but can greatly enhance accuracy in applications that require it. Depending on the values being precomputed, this technique can also be used to shrink the lookup table size while retaining about the same accuracy. In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ...
In image processing, lookup tables are often called LUTs, and they link index numbers to output values. One common LUT, called the colormap or palette, is used to determine the colors and intensity values with which a particular image will be displayed. UPIICSA IPN - Binary image In the broadest sense, image processing is any form of information processing for which both the input and output are images, such as photographs or frames of video. ...
3D LUT, stands for 3D LookUp Table. ...
A palette, in computer graphics, is a designated subset of the total range of colours supported by a computer graphics system. ...
It's important to note that, while often effective, lookup tables can result in a severe penalty if the computation it replaces is relatively simple, not only because retrieving the result from memory may require more time, but also because it may increase memory requirements and pollute the cache. If the table is large, each table access will almost certainly cause a cache miss. This is increasingly becoming an issue as processors outrace memory. A similar issue appears in rematerialization, a compiler optimization. In some environments, such as the Java programming language, table lookups can be even more expensive due to mandatory bounds checking involving an additional comparison and branch for each lookup. Look up cache in Wiktionary, the free dictionary. ...
This article is about the computer term. ...
This article is about the compiler optimization. ...
Compiler optimization is the process of tuning the output of a compiler to minimise some attribute (or maximise the efficiency) of an executable program. ...
Java is an object-oriented programming language developed by James Gosling and colleagues at Sun Microsystems in the early 1990s. ...
There are two fundamental limitations on when it is possible to construct a lookup table for a problem. 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 restriction is the time required to initially compute the table values - although this doesn't need to be done often, if it requires prohibitive time, it may make the table inappropriate to use.
Examples
Computing sine Most computers, which only perform basic arithmetic operations, cannot directly calculate the sine of a given value. Instead, they use a complex formula such as the following Taylor series to compute the value of sine to a high degree of precision: In mathematics, the trigonometric functions are functions of an angle, important when studying triangles and modeling periodic phenomena. ...
As the degree of the Taylor series rises, it approaches the correct function. ...
 (for x close to 0)
However, this can be expensive to compute, especially on slow processors, and there are many applications, particularly in traditional computer 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 of x we choose the sine of the value closest to x. This will be close to the correct value because sine is a continuous function with a bounded rate of change. For example: Computer graphics (CG) is the field of visual computing, where one utilizes computers both to generate visual images synthetically and to integrate or alter visual and spatial information sampled from the real world. ...
In mathematics, a continuous function is a function for which, intuitively, small changes in the input result in small changes in the output. ...
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 the sine function 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 less 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 our example using linear interpolation: This plot illustrates linear interpolation. ...
Linear interpolation is a process employed in mathematics, and numerous applications including computer graphics. ...
In mathematics, a smooth function is one that is infinitely differentiable, i. ...
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) When using interpolation, it's often beneficial to use 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. In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ...
Counting 1 bits Another, more 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 number, sometimes called the population function. For example, the number 37 is 100101 in binary, so it contains three set bits. A simple piece of C code designed to count the 1 bits in a 32-bit int might look like this: Wikibooks has a book on the topic of C Programming The C programming language (often, just C) is a general-purpose, procedural, imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ...
int count_ones(unsigned int x) { int i, result = 0; for(i=0; i<32; i++) { result += x & 1; x = x >> 1; } return result; } Unfortunately, this simple algorithm can take potentially hundreds of cycles on a modern architecture, because it makes many branches (loops) and branching is slow. This can be ameliorated using loop unrolling and some other more clever tricks, but there is a simple and fast solution using table lookup: simply construct a table bits_set with 256 entries giving the number of one bits set in each possible byte value. We then use this table to find the number of ones in each byte of the integer and add up the results. With no branches, four memory accesses, and almost no arithmetic, this can be dramatically faster than the algorithm above: Wikipedia does not yet have an article with this exact name. ...
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]; }
Sine Table Example // C 8-bit Sine Table const unsigned char sinetable[256] = { 128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174, 176,179,182,185,188,191,193,196,199,201,204,206,209,211,213,216, 218,220,222,224,226,228,230,232,234,236,237,239,240,242,243,245, 246,247,248,249,250,251,252,252,253,254,254,255,255,255,255,255, 255,255,255,255,255,255,254,254,253,252,252,251,250,249,248,247, 246,245,243,242,240,239,237,236,234,232,230,228,226,224,222,220, 218,216,213,211,209,206,204,201,199,196,193,191,188,185,182,179, 176,174,171,168,165,162,159,156,152,149,146,143,140,137,134,131, 128,124,121,118,115,112,109,106,103,99, 96, 93, 90, 87, 84, 81, 79, 76, 73, 70, 67, 64, 62, 59, 56, 54, 51, 49, 46, 44, 42, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 18, 16, 15, 13, 12, 10, 9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 42, 44, 46, 49, 51, 54, 56, 59, 62, 64, 67, 70, 73, 76, 79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124 };
Hardware LUTs In digital logic, an n-bit lookup table can be implemented with a multiplexer whose select lines are the inputs of the LUT and whose inputs are constants. An n-bit LUT can encode any n-input Boolean logic function by modeling such functions as truth tables. This is an efficient way of encoding Boolean logic functions, and 4-bit LUTs are in fact the key component of modern FPGAs. Digital circuits are electric circuits based on a number of discrete voltage levels. ...
A multiplexer (or mux or, more rarely, muldex) is a device that encodes or multiplexes information from two or more data sources into a single channel. ...
Boolean logic is a complete system for logical operations. ...
Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...
Boolean logic is a complete system for logical operations. ...
An Altera FPGA with 20,000 cells. ...
See also |
Feeds |
Contact