What Is a Lookup Table?

In computer science, a lookup table is a data structure such as an array or an associative array calculated at runtime with a simple query operation.

In computer science, a lookup table is a data structure such as an array or an associative array calculated at runtime with a simple query operation.

Chinese name

Lookup table

Subject

In computer science

Features

With simple query operations

Types of

data structure

Lookup table principle

Because extracting values from memory is often much faster than complex calculations, the speed increase is very significant.

A classic example is a triangular table. The sine value required for each calculation may be unbearably slow in some applications. To avoid this, the application can calculate the sine value of a certain number of angles at the beginning, such as calculating the number of each integer angle. Sine value. When the following program needs the sine value, use the lookup table to extract the sine value of the adjacent angle from the memory instead of using a mathematical formula to calculate.

Before the advent of computers, people used similar tables to speed up manual calculations. Very popular tables are trigonometric, logarithmic, and statistical density functions. Another tool used to speed up manual calculations is the slide rule.

Some compromise methods are the use of a lookup table and interpolation at the same time, which requires a small amount of calculation. This method can provide higher accuracy for the part between the two pre-calculated values, which slightly increases the amount of calculation but significantly This improves the accuracy required by the application. According to the pre-calculated values, this method also reduces the size of the lookup table while maintaining the same accuracy.

In image processing, lookup tables are often referred to as LUTs, and they associate index numbers with output values. The color table, as a common LUT, is used to determine the color and intensity to be displayed for a particular image.

Another issue to be aware of is that although lookup tables are often very efficient, if the calculations being replaced are fairly simple, you will lose more than just getting the results from memory, and because it will increase Required memory and corrupted the cache. If the lookup table is too large, cache misses occur almost every time the lookup table is accessed, which becomes an issue when processor speed exceeds memory speed. A similar problem occurs during compiler-optimized rematerialization. In some environments, such as the Java programming language, lookup tables can be more expensive due to the additional comparison and branching of each lookup with mandatory boundary checks.

There are two basic constraints on when to build a lookup table, one is the amount of available memory; you cannot build a table that exceeds the available memory space, although you can build a disk-based lookup table at the cost of lookup speed. Another constraint is the time to initially calculate the lookup table-although this work does not need to be done often, it is not suitable to use the lookup table if the time taken is not acceptable.

Lookup table calculates sine value

Many computers can only perform basic arithmetic operations, not directly calculate the sine of a given value. They use a complex formula such as the following Taylor series (en: Taylor series) to calculate a highly accurate sine:

(x is close to 0)

However, such calculations can be very expensive, especially on low-speed processors. There are many applications, especially traditional computer graphics that require thousands of sine calculations per second. A common solution is to calculate the sine value of many uniformly distributed values at the beginning, and then look up the sine value closest to the required x in the table, this value is very close to the correct value, because the sine function is a finite change Continuous function of rate. E.g:

real array sine_table [-1000..1000]

for x from -1000 to 1000

sine_table [x]: = sine (x / 1000 / pi)

function lookup_sine (x)

return sine_table [round (x / 1000 / pi)]

Image: Interpolation example linear.png

Linear interpolation of some sine functions Unfortunately, the lookup table requires some space: if you use IEEE double-precision floating-point numbers, it will require 16,000 bytes. If fewer sampling points are used, accuracy will be greatly reduced. A better solution is linear interpolation. A straight line is formed between the values of the two points on the left and right sides of the point to be calculated in the table. The value on the line corresponding to this point is the sine of the calculated point. This method is also fast to calculate and has higher accuracy for smooth functions such as sine functions. 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)

When using interpolation, you can benefit from non-uniform sampling, that is, near the straight line, use fewer sampling points, and use more sampling points in the place where the change is fast to maximize the actual curve . For more information, please refer to interpolation.

1 Lookup table calculates 1 digits

population function. For example, the number 37 has a binary form of 100101, so it contains three bits set to 1. A simple C language program that calculates the number of 1's in a 32-bit integer is:

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 will require hundreds of clock cycles to complete on modern architectures, because it causes many branches and loops, and the branch speed is very slow. This can be improved using loop unrolling and other clever tricks, but the simplest and quickest solution is a lookup table: simply build a table of 256 entries containing the number of 1s that each possible value contains. Then use this table to find the number of 1s contained in each byte of the integer and add the results. There are no branches, four memory accesses, and almost no arithmetic operations, which can greatly increase the speed compared to the above algorithm.

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];

}

-------------------------------------------------- --------------------

#include

#define BYTE unsigned char

/ * Define lookup table * /

BYTE numTable [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, 5, 2, 3, 3,

4, 3, 4, 4, 5, 3, 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, 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, 7, 5, 6, 6,

7, 6, 7, 7, 8

};

int main (int argc, char * argv [])

{

int i, num = 0;

BYTE a = 0;

/ * Receive user input * /

printf ("\ nPlease Input a BYTE (0 ~ 255):");

scanf ("% d", & a);

/ * Calculate the number of 1 * /

/ * Use BYTE directly as the index of the array to take out the number of 1, wonderful! * /

printf ("\ nthe num of 1 in the BYTE is% d", checknum [a]);

return 0;

}

Lookup table hardware lookup table

In digital logic, an n-bit lookup table can be implemented using a multiplexer. Its selection line is the input of the LUT, and its input is constant. An n-bit LUT can encode any n-bit input by modeling a Boolean logic function as a truth table. This is an effective way to encode Boolean logic functions. A 4-bit LUT is actually the main component of modern FPGAs.

Using this structure of the PLD chip, we can call it FPGA: such as ACERA, APEX series of Altera, Spartan of Xilinx, Virtex series and so on.

Look-up-table is called LUT for short, and LUT is essentially a RAM. At present, 4-input LUTs are mostly used in FPGAs, so each LUT can be regarded as a 16x1 RAM with a 4-bit address line. After the user describes a logic circuit through a schematic diagram or HDL language, the PLD / FPGA development software will automatically calculate all possible results of the logic circuit and write the results in advance in RAM. In this way, each input signal performs a logic operation equal to Enter an address to look up the table, find out what the address corresponds to, and then output it.