In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a lookup table (LUT) is an
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
that replaces
runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from
hash tables
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
in a way that, to retrieve a value
with key
, a hash table would store the value
in the slot
where
is a
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
i.e.
is used to compute the slot, while in the case of LUT, the value
is stored in slot
, thus directly addressable.
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
In computing, input/output (I/O, or informally io or IO) is the communication between an information processing system, such as a computer, and the outside world, possibly a human or another information processing system. Inputs are the signals ...
operation. The tables may be
precalculated and stored in
static
Static may refer to:
Places
*Static Nunatak, a nunatak in Antarctica
United States
* Static, Kentucky and Tennessee
*Static Peak, a mountain in Wyoming
**Static Peak Divide, a mountain pass near the peak
Science and technology Physics
*Static el ...
program storage, calculated (or
"pre-fetched") as part of a program's initialization phase (
memoization
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. 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
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware de ...
also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality.
History
![Abramowitz&Stegun](https://upload.wikimedia.org/wikipedia/commons/2/2e/Abramowitz%26Stegun.page97.agr.jpg)
Before the advent of computers, lookup tables of values were used to speed up hand calculations of complex functions, such as in
trigonometry
Trigonometry () is a branch of mathematics that studies relationships between side lengths and angles of triangles. The field emerged in the Hellenistic world during the 3rd century BC from applications of geometry to astronomical studies. T ...
,
logarithms
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
, and statistical density functions.
In ancient (499 AD) India,
Aryabhata
Aryabhata (ISO: ) or Aryabhata I (476–550 CE) was an Indian mathematician and astronomer of the classical age of Indian mathematics and Indian astronomy. He flourished in the Gupta Era and produced works such as the ''Aryabhatiya'' (which ...
created one of the first
sine tables, which he encoded in a Sanskrit-letter-based number system. In 493 AD,
Victorius of Aquitaine
Victorius of Aquitaine, a countryman of Prosper of Aquitaine and also working in Rome, produced in AD 457 an Easter Cycle, which was based on the consular list provided by Prosper's Chronicle. This dependency caused scholars to think that Prosper ...
wrote a 98-column multiplication table which gave (in
Roman numerals
Roman numerals are a numeral system that originated in ancient Rome and remained the usual way of writing numbers throughout Europe well into the Late Middle Ages. Numbers are written with combinations of letters from the Latin alphabet, eac ...
) 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" Modern school children are often taught to memorize "
times tables
In mathematics, a multiplication table (sometimes, less formally, a times table) is a mathematical table used to define a multiplication operation for an algebraic system.
The decimal multiplication table was traditionally taught as an esse ...
" 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
In computing, input/output (I/O, or informally io or IO) is the communication between an information processing system, such as a computer, and the outside world, possibly a human or another information processing system. Inputs are the signals ...
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 manual
caching 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 computer
spreadsheet
A spreadsheet is a computer application for computation, organization, analysis and storage of data in tabular form. Spreadsheets were developed as computerized analogs of paper accounting worksheets. The program operates on data entered in cel ...
s, with the initial version of
VisiCalc
VisiCalc (for "visible calculator") is the first spreadsheet computer program for personal computers, originally released for Apple II by VisiCorp on 17 October 1979. It is often considered the application that turned the microcomputer from a hob ...
(1979) including a
LOOKUP
function among its original 20 functions. This has been followed by subsequent spreadsheets, such as
Microsoft Excel
Microsoft Excel is a spreadsheet developed by Microsoft for Microsoft Windows, Windows, macOS, Android (operating system), Android and iOS. It features calculation or computation capabilities, graphing tools, pivot tables, and a macro (comp ...
, and complemented by specialized
VLOOKUP
and
HLOOKUP
functions to simplify lookup in a vertical or horizontal table. In Microsoft Excel the
XLOOKUP
function has been rolled out starting 28 August 2019.
Limitations
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 of
universe
The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the universe. Acc ...
—where the keys are drawn—is large, it might be impractical or impossible to be stored in
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
. Hence, in this case, a
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
would be a preferable alternative.
Examples
Trivial hash function
For a
trivial hash function
Index mapping (or direct addressing, or a trivial hash function) in computer science describes using an array, in which each position corresponds to a key in the universe of possible values.
The technique is most effective when the universe of keys ...
lookup, the unsigned
raw data
Raw data, also known as primary data, are ''data'' (e.g., numbers, instrument readings, figures, etc.) collected from a source. In the context of examinations, the raw data might be described as a raw score (after test scores).
If a scientist ...
value is used ''directly'' 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 in
constant time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Counting bits in a series of bytes
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 the ''
population function''. For example, the decimal number "37" is "00100101" in binary, so it contains three bits that are set to binary "1".
A simple example of
C code, designed to count the 1 bits in a ''int'', might look like this:
int count_ones(unsigned int x)
The above implementation requires 32 operations for an evaluation of a 32-bit value, which can potentially take several
clock cycles
In electronics and especially synchronous digital circuits, a clock signal (historically also known as ''logic beat'') oscillates between a high and a low state and is used like a metronome to coordinate actions of digital circuits.
A clock signa ...
due to
branching. It can be "
unrolled" into a lookup table which in turn uses
trivial hash function
Index mapping (or direct addressing, or a trivial hash function) in computer science describes using an array, in which each position corresponds to a key in the universe of possible values.
The technique is most effective when the universe of keys ...
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
In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled.
The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concept ...
script could be used to dynamically generate and append the table to the
source file
In computing, source code, or simply code, is any collection of code, with or without comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the wo ...
. Sum of ones in each byte of the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
can be calculated through
trivial hash function
Index mapping (or direct addressing, or a trivial hash function) in computer science describes using an array, in which each position corresponds to a key in the universe of possible values.
The technique is most effective when the universe of keys ...
lookup on each byte; thus, effectively avoiding branches resulting in considerable improvement in performance.
int count_ones(int input_value) }
Lookup tables in image processing
![Red Green Blue 16 bit Look up Table Sample](https://upload.wikimedia.org/wikipedia/commons/6/6a/Red_Green_Blue_16_bit_Look_up_Table_Sample.svg)
In data analysis applications, such as
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
, a lookup table (LUT) is used to transform the input data into a more desirable output format. For example, a grayscale picture of the planet Saturn will be transformed into a color image to emphasize the differences in its rings.
A classic example of reducing run-time computations using lookup tables is to obtain the result of a
trigonometry
Trigonometry () is a branch of mathematics that studies relationships between side lengths and angles of triangles. The field emerged in the Hellenistic world during the 3rd century BC from applications of geometry to astronomical studies. T ...
calculation, such as the
sine
In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side that is oppo ...
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 interpolate to the sine of the desired value, instead of calculating by mathematical formula. Lookup tables are thus used by mathematics
coprocessor
A coprocessor is a computer processor used to supplement the functions of the primary processor (the CPU). Operations performed by the coprocessor may be floating-point arithmetic, graphics, signal processing, string processing, cryptography o ...
s in computer systems. An error in a lookup table was responsible for Intel's infamous
floating-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 of power
y] to replace a function to calculate x
y 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 using
interpolation
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a n ...
. 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 the higher accuracy. Depending on the values being precomputed,
precomputation
In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is often used in algo ...
with interpolation can also be used to shrink the lookup table size while maintaining accuracy.
In
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
, lookup tables are often called
LUT Lut may refer to:
* Lut, a prophet mentioned in the Qur'an
* Lut, Iran, a village in Amol County, Mazandaran Province
* Lut (Lowlet), a village in Sari County, Mazandaran Province, Iran
* Dasht-e Lut, a desert in southeastern Iran
* Lut, a small t ...
s (or 3DLUT), and give an output value for each of a range of index 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. In
computed tomography, "windowing" refers to a related concept for determining how to display the intensity of measured radiation.
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 of
polluting the cache may also become a problem. Table accesses for large tables will almost certainly cause a
cache miss
In computing, a cache ( ) is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewher ...
. This phenomenon is increasingly becoming an issue as processors outpace memory. A similar issue appears in
rematerialization
In computer science, rematerialization or remat is a compiler optimization which saves time by recomputing a value instead of loading it from memory. It is typically tightly integrated with register allocation, where it is used as an alternative ...
, a
compiler optimization
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power con ...
. In some environments, such as the
Java programming language
Java is a high-level, class-based, object-oriented programming language that is designed to have as few implementation dependencies as possible. It is a general-purpose programming language intended to let programmers ''write once, run anywh ...
, 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.
Computing sines
Most computers only perform basic arithmetic operations and cannot directly calculate the
sine
In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side that is oppo ...
of a given value. Instead, they use the
CORDIC
CORDIC (for "coordinate rotation digital computer"), also known as Volder's algorithm, or: Digit-by-digit method Circular CORDIC (Jack E. Volder), Linear CORDIC, Hyperbolic CORDIC (John Stephen Walther), and Generalized Hyperbolic CORDIC (GH C ...
algorithm or a complex formula such as the following
Taylor series
In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
to compute the value of sine to a high degree of precision:
:
(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
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
, 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'' through array indexing operation. This will be close to the correct value because sine is a
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
with a bounded rate of change. For example:
real array sine_table 1000..1000for x from -1000 to 1000
sine_table = sine(pi * x / 1000)
function lookup_sine(x)
return sine_table ound(1000 * x / pi)
![Interpolation example linear](https://upload.wikimedia.org/wikipedia/commons/6/67/Interpolation_example_linear.svg)
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
In mathematics, linear interpolation is a method of curve fitting using linear polynomials to construct new data points within the range of a discrete set of known data points.
Linear interpolation between two known points
If the two known poin ...
, 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 function
In mathematical analysis, the smoothness of a function (mathematics), function is a property measured by the number of Continuous function, continuous Derivative (mathematics), derivatives it has over some domain, called ''differentiability cl ...
s such as the sine function. Here is an example using linear interpolation:
function lookup_sine(x)
x1 = floor(x*1000/pi)
y1 = sine_table 1 y2 = sine_table1+1
1 (one, unit, unity) is a number representing a single or the only entity. 1 is also a numerical digit and represents a single unit of counting or measurement. For example, a line segment of ''unit length'' is a line segment of length 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
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. F ...
s. For smoother interpolation of table lookup that is continuous and has continuous
first derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
, one should use the
cubic Hermite spline
In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form, that is, by its values and first derivatives at the end points of the corresponding ...
.
Another solution that uses a quarter of the space but takes a bit longer to compute would be to take into account the relationships between sine and cosine along with their symmetry rules. In this case, the lookup table is calculated by using the sine function for the first quadrant (i.e. sin(0..pi/2)). When we need a value, we assign a variable to be the angle wrapped to the first quadrant. We then wrap the angle to the four quadrants (not needed if values are always between 0 and 2*pi) and return the correct value (i.e. first quadrant is a straight return, second quadrant is read from pi/2-x, third and fourth are negatives of the first and second respectively). For cosine, we only have to return the angle shifted by pi/2 (i.e. x+pi/2). For tangent, we divide the sine by the cosine (divide-by-zero handling may be needed depending on implementation):
function init_sine()
for x from 0 to (360/4)+1
sine_table = sin(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 < 180) return sine_table 0-y if (x < 270) return -sine_table y return -sine_table 0-y
function lookup_cosine(x)
return lookup_sine(x + 90)
function lookup_tan(x)
return lookup_sine(x) / lookup_cosine(x)
When using interpolation, the size of the lookup table can be reduced by using ''
nonuniform sampling
Nonuniform sampling is a branch of sampling theory involving results related to the Nyquist–Shannon sampling theorem. Nonuniform sampling is based on Lagrange interpolation and the relationship between itself and the (uniform) sampling theorem. N ...
'', 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 field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a n ...
.
Other usages of lookup tables
Caches
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):
* one piece (the tag) contains the value of the remaining bits of the address; if these bits match with those from the memory address to read or write, then the other piece contains the cached value for this address.
* the other piece maintains the data associated to that 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).
Hardware LUTs
In
digital logic
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more Binary number, binary inputs that produces a single binary output. Depending on the context, the term may refer to an id ...
, a lookup table can be implemented with a
multiplexer
In electronics, a multiplexer (or mux; spelled sometimes as multiplexor), also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The sel ...
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 an
ASIC
An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficien ...
whose purpose is specific to a function, or provided by
D latch
In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and ...
es which allow for configurable values. (
ROM
Rom, or ROM may refer to:
Biomechanics and medicine
* Risk of mortality, a medical classification to estimate the likelihood of death for a patient
* Rupture of membranes, a term used during pregnancy to describe a rupture of the amniotic sac
* ...
,
EPROM
An EPROM (rarely EROM), or erasable programmable read-only memory, is a type of programmable read-only memory (PROM) chip that retains its data when its power supply is switched off. Computer memory that can retrieve stored data after a power s ...
,
EEPROM
EEPROM (also called E2PROM) stands for electrically erasable programmable read-only memory and is a type of non-volatile memory used in computers, usually integrated in microcontrollers such as smart cards and remote keyless systems, or as a ...
, or
RAM
Ram, ram, or RAM may refer to:
Animals
* A male sheep
* Ram cichlid, a freshwater tropical fish
People
* Ram (given name)
* Ram (surname)
* Ram (director) (Ramsubramaniam), an Indian Tamil film director
* RAM (musician) (born 1974), Dutch
* ...
.)
An ''n''-bit LUT can encode any ''n''-input
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
by storing the
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
of the function in the LUT. This is an efficient way of encoding
Boolean logic
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denote ...
functions, and LUTs with 4-6 bits of input are in fact the key component of modern
field-programmable gate array
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
s (FPGAs) which provide reconfigurable hardware logic capabilities.
Data acquisition and control systems
In
data acquisition Data acquisition is the process of sampling signals that measure real-world physical conditions and converting the resulting samples into digital numeric values that can be manipulated by a computer. Data acquisition systems, abbreviated by the acro ...
and
control system
A control system manages, commands, directs, or regulates the behavior of other devices or systems using control loops. It can range from a single home heating controller using a thermostat controlling a domestic boiler to large industrial c ...
s, lookup tables are commonly used to undertake the following operations in:
* The application of
calibration
In measurement technology and metrology, calibration is the comparison of measurement values delivered by a device under test with those of a calibration standard of known accuracy. Such a standard could be another measurement device of know ...
data, so as to apply corrections to uncalibrated measurement or
setpoint values; and
* Undertaking
measurement unit
A unit of measurement is a definite magnitude of a quantity, defined and adopted by convention or by law, that is used as a standard for measurement of the same kind of quantity. Any other quantity of that kind can be expressed as a multip ...
conversion; and
* Performing generic user-defined computations.
In some systems,
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s may also be defined in place of lookup tables for these calculations.
See also
*
Associative array
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an as ...
*
Branch table
In computer programming, a branch table or jump table is a method of transferring program control (Branch (computer science), branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of b ...
*
Gal's accurate tables Gal's accurate tables is a method devised by Shmuel Gal to provide accurate values of special functions using a lookup table and interpolation. It is a fast and efficient method for generating values of functions like the exponential function, expon ...
*
Memoization
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
*
Memory-bound function
Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of free memory required to hold the working data. This is in contrast to algorithms that are compute-bound, where th ...
*
Shift register lookup table
A shift register lookup table, also shift register LUT or SRL, refers to a component in digital circuitry. It is essentially a shift register of variable length. The length of SRL is set by driving address pins high or low and can be changed dyna ...
*
Palette, a.k.a. color lookup table or CLUT – for the usage in computer graphics
*
3D lookup table – usage in film industry
References
{{Reflist
External links
*
Fast table lookup using input character as index for branch table
Art of Assembly: Calculation via Table LookupsBy Sean Eron Anderson of
Stanford University
Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...
Memoization in C++by Paul McNamee,
Johns Hopkins University
Johns Hopkins University (Johns Hopkins, Hopkins, or JHU) is a private university, private research university in Baltimore, Maryland. Founded in 1876, Johns Hopkins is the oldest research university in the United States and in the western hem ...
showing savings
"The Quest for an Accelerated Population Count"by Henry S. Warren, Jr.
Arrays
Associative arrays
Computer performance
Software optimization
Articles with example C code