Why computers prefer looking things up over doing the math
In short: Calculating a complex sine wave or a logarithm is computationally expensive. To save time, engineers use a clever shortcut: instead of solving a formula, they simply look up the answer in a pre-calculated list. This technique, known as a lookup table, trades memory space for significant processing speed.
At its core, a lookup table (LUT) replaces runtime computation with a simpler array indexing operation. This process, called direct addressing, is often much faster than performing 'expensive' mathematical functions. This principle has existed long before digital computers; ancient mathematicians used tables to speed up hand calculations for trigonometry and logarithms. For instance, in 493 AD, Victorius of Aquitaine authored a 98-column multiplication table for products ranging from 2 to 50 times. This method of pre-calculation is also known as memoization when performed during a program's initialization. Even the Indian mathematician Aryabhata utilized such a system in 499 AD to create an early sine table encoded in Sanskrit letters.
In modern computing, LUTs are used to optimize everything from image processing to cryptography. In image analysis, a LUT can transform a grayscale image of Saturn into a color version to highlight its rings. In cryptography, new techniques are being developed to use LUTs for the linear layers of block ciphers, potentially reducing required memory storage by as much as 87.5% for large matrices. Even hardware components like FPGAs rely on reconfigurable LUTs to provide programmable functionality. Beyond graphics, these tables are vital in medical acoustics for measuring cochlear function. Researchers use level-specific tables to cancel distortion in single-transducer ear measurements.
However, the technique is not without trade-offs. While the performance of a lookup is guaranteed, large tables can cause 'cache misses' because processors cannot keep all the data in high-speed memory. If a table is too massive to fit in memory, developers may use interpolation—drawing a line between known points—to approximate values. This allows for smaller, more manageable tables that maintain high accuracy for smooth functions like sine waves. In some programming environments like Java, lookups can actually be slower due to mandatory bounds-checking. To mitigate errors, developers can use nonuniform sampling, placing more points where a function changes most rapidly.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Lookup table
- Also: Efficient implementation of the linear layer of block ciphers with large MDS matrices based on a new lookup table technique.
To cite this card, link to https://intellectplus.co.uk/app/health-lookup-table.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Heart & circulation · More in Health · Latest · A–Z · All topics
