Editing Lookup table (section)

{{Short description|Array that replaces runtime computation with a simpler array indexing operation}}
{{Use dmy dates|date=November 2019}}

In [[computer science]], a '''lookup table''' ('''LUT''') is an [[array data structure|array]] that replaces [[runtime (program lifecycle phase)|runtime]] computation of a mathematical [[function (mathematics)|function]] with a simpler array indexing operation, in a process termed as '''''direct addressing'''''. 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]] operation.<ref>{{cite web |url=http://pmcnamee.net/c++-memoization.html |title=Automated Memoization in C++ |first=Paul |last=McNamee |date=21 August 1998 |url-status=unfit |archive-url=https://web.archive.org/web/20190416012134/http://pmcnamee.net/c++-memoization.html |archive-date=2019-04-16}}</ref> The tables may be [[precomputation|precalculated]] and stored in [[static memory allocation|static]] program storage, calculated (or [[prefetcher|"pre-fetched"]]) as part of a program's initialization phase (''[[memoization]]''<!--note: not the same as "memorization"-->), 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. [[Field-programmable gate array|FPGAs]] also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality.
LUTs differ from [[hash tables]] in a way that, to retrieve a value <math>v</math> with key <math>k</math>, a hash table would store the value <math>v</math> in the slot <math>h(k)</math> where <math>h</math> is a [[hash function]] i.e. <math>k</math> is used to compute the slot, while in the case of LUT, the value <math>v</math> is stored in slot <math>k</math>, thus directly addressable.<ref name="Kwok95">{{cite journal|journal=Communications in Numerical Methods in Engineering|volume=11|issue=5|first1=W.|last1=Kwok|first2=K.|last2=Haghighi|first3=E.|last3=Kang|year=1995|doi=10.1002/cnm.1640110511|title=An efficient data structure for the advancing-front triangular mesh generation technique|pages=465–473|url=https://onlinelibrary.wiley.com/doi/10.1002/cnm.1640110511|publisher=Wiley & Sons}}</ref>{{rp|p=466}}