Lookup table

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a lookup table (LUT) is an <a href="/facts/Array_data_structure/BKGvF8AM">array</a> that replaces <a href="/facts/Runtime_(program_lifecycle_phase)/lCxKsrzB">runtime</a> computation of a mathematical <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> 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 <a href="/facts/Input%2foutput/WQTE8Jas">input/output</a> operation. The tables may be <a href="/facts/Precomputation/8fJVSXz9">precalculated</a> and stored in <a href="/facts/Static_memory_allocation/dYIs2E5p">static</a> program storage, calculated (or <a href="/facts/Prefetcher/AzVy2rIL">"pre-fetched"</a>) as part of a program's initialization phase (<a href="/facts/Memoization/u08VhUKm">memoization</a>), 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. <a href="/facts/Field-programmable_gate_array/M8LSGcAU">FPGAs</a> also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality.
LUTs differ from <a href="/facts/Hash_tables/Ht4ptDPF">hash tables</a> in a way that, to retrieve a value 
 
 
 
 v
 
 
 {\displaystyle v}
 
 with key 
 
 
 
 k
 
 
 {\displaystyle k}
 
, a hash table would store the value 
 
 
 
 v
 
 
 {\displaystyle v}
 
 in the slot 
 
 
 
 h
 (
 k
 )
 
 
 {\displaystyle h(k)}
 
 where 
 
 
 
 h
 
 
 {\displaystyle h}
 
 is a <a href="/facts/Hash_function/rk6MlCt3">hash function</a> i.e. 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is used to compute the slot, while in the case of LUT, the value 
 
 
 
 v
 
 
 {\displaystyle v}
 
 is stored in slot 
 
 
 
 k
 
 
 {\displaystyle k}
 
, thus directly addressable.: 466

Lookup table open-in-new

Lookup table