Editing Lookup table (section)

===Discussion===
{{original research section|date=October 2021}}
A classic example of reducing run-time computations using lookup tables is to obtain the result of a [[trigonometry]] calculation, such as the [[sine]] of a value.<ref>{{cite web |author1=Sasao, T.; Butler, J. T.; Riedel, M. D. |title=Application of LUT Cascades to Numerical Function Generators |url=https://apps.dtic.mil/sti/citations/ADA596280 |website=Defence Technical Information Center |publisher=NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING |access-date=17 May 2024}}</ref> 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 be used by mathematics [[coprocessor]]s in computer systems. An error in a lookup table was responsible for Intel's infamous [[Pentium FDIV bug|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[x][y]''' to replace a function to calculate '''x<sup>y</sup>''' 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]]. 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 of [[cache pollution|polluting the cache]] may also become a problem. Table accesses for large tables will almost certainly cause a [[cache miss]]. This phenomenon is increasingly becoming an issue as processors outpace memory. A similar issue appears in [[rematerialization]], a [[compiler optimization]]. In some environments, such as the [[Java (programming language)|Java 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.