Precomputation

Last updated January 18, 2023

Part of a 20th-century precomputed mathematical table of common logarithms. Abramowitz&Stegun.page97.agr.jpg — Part of a 20th-century precomputed mathematical table of common logarithms.

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 algorithms that depend on the results of expensive computations that don't depend on the input of the algorithm. A trivial example of precomputation is the use of hardcoded mathematical constants, such as π and e, rather than computing their approximations to the necessary precision at run time.

Overview

Precomputing a set of intermediate results at the beginning of an algorithm's execution can often increase algorithmic efficiency substantially. This becomes advantageous when one or more inputs is constrained to a small enough range that the results can be stored in a reasonably sized block of memory. Because memory access is essentially constant in time complexity (except for caching delays), any algorithm with a component which has worse than constant efficiency over a small input range can be improved by precomputing values. In some cases efficient approximation algorithms can be obtained by computing a discrete subset of values and interpolating for intermediate input values, since interpolation is also a linear operation.

History

Before the advent of computers, printed lookup tables of values were used by people to speed up hand calculations of complex functions, such as in trigonometric tables, logarithm tables, and tables of statistical density functions ^[5] School children are often taught to memorize "times tables" to avoid calculations of the most commonly used numbers (up to 9 x 9 or 12 x 12). Even as early as 493 A.D., Victorius of Aquitaine wrote a 98-column multiplication table which gave (in Roman numerals) 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" ^[6]

Examples

Even modern computer implementations of digital trigonometric functions often use precomputed lookup tables to either provide coefficients for interpolation algorithms or to initialise successive approximation algorithms.

Many attacks on cryptosystems involve precomputation.

Examples of large-scale precomputation as part of modern efficient algorithms include:

Rainbow tables
Perfect hashes
The cube attack
Precalculated BSP trees for visibility calculations in 3D graphics
Radiosity precomputation for illumination in 3D graphics

Compilers use precomputation extensively as a means of increasing the run-time speed of the resulting code: this precomputation can be regarded as in effect a form of partial evaluation of the program code itself. Examples of this sort of precomputation include dataflow analysis and strength reduction steps.

Related Research Articles

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 mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number $x$ to the base $b$ is the exponent to which $b$ must be raised, to produce $x$ . For example, since $1000 = 10 3$ , the logarithm base 10 of $1000$ is $3$ , or $log 10 (1000) = 3$ . The logarithm of $x$ to base $b$ is denoted as $log b (x)$ , or without parentheses, $log b x$ , or even without the explicit base, $log x$ , when no confusion is possible, or when the base does not matter such as in big O notation.

<span class="mw-page-title-main">Numerical analysis</span> Study of algorithms using numerical approximation

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. It is the study of numerical methods that attempt at finding approximate solutions of problems rather than the exact ones. Numerical analysis finds application in all fields of engineering and the physical sciences, and in the 21st century also the life and social sciences, medicine, business and even the arts. Current growth in computing power has enabled the use of more complex numerical analysis, providing detailed and realistic mathematical models in science and engineering. Examples of numerical analysis include: ordinary differential equations as found in celestial mechanics, numerical linear algebra in data analysis, and stochastic differential equations and Markov chains for simulating living cells in medicine and biology.

The number $π$ is a mathematical constant that is the ratio of a circle's circumference to its diameter, approximately equal to 3.14159. The number $π$ appears in many formulas across mathematics and physics. It is an irrational number, meaning that it cannot be expressed exactly as a ratio of two integers, although fractions such as $are commonly used to approximate it. Consequently, its decimal representation never ends, nor enters a permanently repeating pattern. It is a transcendental number, meaning that it cannot be a solution of an equation involving only sums, products, powers, and integers. The transcendence of π implies that it is impossible to solve the ancient challenge of squaring the circle with a compass and straightedge. The decimal digits of π appear to be randomly distributed, but no proof of this conjecture has been found.$

In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering. The calculation of mathematical tables was an important area of study, which led to the development of the first mechanical computing devices.

<span class="mw-page-title-main">Linear interpolation</span> Method of curve fitting to construct new data points within the range of known data points

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.

In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.

Mathematical tables are lists of numbers showing the results of a calculation with varying arguments. Trigonometric tables were used in ancient Greece and India for applications to astronomy and celestial navigation, and continued to be widely used until electronic calculators became cheap and plentiful, in order to simplify and drastically speed up computation. Tables of logarithms and trigonometric functions were common in math and science textbooks, and specialized tables were published for numerous applications.

An approximation is anything that is intentionally similar but not exactly equal to something else.

In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables 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 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 operation. The tables may be precalculated and stored in static program storage, calculated as part of a program's initialization phase (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 items in an array and, in some programming languages, may include pointer functions to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality.$

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 the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

<span class="mw-page-title-main">Scientific calculator</span> Calculator designed to calculate problems in science, engineering, and mathematics

A scientific calculator is an electronic calculator, either desktop or handheld, designed to perform mathematical operations. They have completely replaced slide rules and are used in both educational and professional settings.

In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. The discrete log problem is of fundamental importance to the area of public key cryptography.

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 has also been used in other contexts, such as in simple mutually recursive descent parsing. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling.

CORDIC, also known as Volder's algorithm, or: Digit-by-digit methodCircular CORDIC, Linear CORDIC, Hyperbolic CORDIC, and Generalized Hyperbolic CORDIC, is a simple and efficient algorithm to calculate trigonometric functions, hyperbolic functions, square roots, multiplications, divisions, and exponentials and logarithms with arbitrary base, typically converging with one digit per iteration. CORDIC is therefore also an example of digit-by-digit algorithms. CORDIC and closely related methods known as pseudo-multiplication and pseudo-division or factor combining are commonly used when no hardware multiplier is available, as the only operations it requires are additions, subtractions, bitshift and lookup tables. As such, they all belong to the class of shift-and-add algorithms. In computer science, CORDIC is often used to implement floating-point arithmetic when the target platform lacks hardware multiply for cost or space reasons.

Prosthaphaeresis was an algorithm used in the late 16th century and early 17th century for approximate multiplication and division using formulas from trigonometry. For the 25 years preceding the invention of the logarithm in 1614, it was the only known generally applicable way of approximating products quickly. Its name comes from the Greek prosthesis (πρόσθεσις) and aphaeresis (ἀφαίρεσις), meaning addition and subtraction, two steps in the process.

A rainbow table is a precomputed table for caching the output of cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a key derivation function up to a certain length consisting of a limited set of characters. It is a practical example of a space–time tradeoff, using less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple key derivation function with one entry per hash. Use of a key derivation that employs a salt makes this attack infeasible.

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 or the trigonometric functions to within last-bit accuracy for almost all argument values without using extended precision arithmetic.

In computer science, input enhancement is the principle that processing a given input to a problem and altering it in a specific way will increase runtime efficiency or space efficiency, or both. The altered input is usually stored and accessed to simplify the problem. By exploiting the structure and properties of the inputs, input enhancement creates various speed-ups in the efficiency of the algorithm.

References

↑ Jiawei Han; Micheline Kamber (9 June 2011). Data Mining: Concepts and Techniques: Concepts and Techniques. Elsevier. p. 159. ISBN 978-0-12-381480-7.
↑ Sven Groppe (29 April 2011). Data Management and Query Processing in Semantic Web Databases. Springer Science & Business Media. p. 178. ISBN 978-3-642-19357-6.
↑ Karen Morton; Kerry Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 October 2013). Pro Oracle SQL. Apress. p. 48. ISBN 978-1-4302-6220-6.
↑ Marie-Aude Aufaure; Esteban Zimányi (16 January 2012). Business Intelligence: First European Summer School, EBISS 2011, Paris, France, July 3-8, 2011, Tutorial Lectures. Springer Science & Business Media. p. 43. ISBN 978-3-642-27357-5.
↑ Campbell-Kelly, Martin; Croarken, Mary; Flood, Raymond; et al., eds. (2003). The History of Mathematical Tables From Sumer to Spreadsheets. Oxford University Press. ISBN 978-0-19-850841-0.
↑ Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p. 383.)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[HanKamber2011-1] Jiawei Han; Micheline Kamber (9 June 2011). Data Mining: Concepts and Techniques: Concepts and Techniques. Elsevier. p. 159. ISBN 978-0-12-381480-7.

[Groppe2011-2] Sven Groppe (29 April 2011). Data Management and Query Processing in Semantic Web Databases. Springer Science & Business Media. p. 178. ISBN 978-3-642-19357-6.

[MortonOsborne2013-3] Karen Morton; Kerry Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 October 2013). Pro Oracle SQL. Apress. p. 48. ISBN 978-1-4302-6220-6.

[AufaureZimányi2012-4] Marie-Aude Aufaure; Esteban Zimányi (16 January 2012). Business Intelligence: First European Summer School, EBISS 2011, Paris, France, July 3-8, 2011, Tutorial Lectures. Springer Science & Business Media. p. 43. ISBN 978-3-642-27357-5.

[5] Campbell-Kelly, Martin; Croarken, Mary; Flood, Raymond; et al., eds. (2003). The History of Mathematical Tables From Sumer to Spreadsheets. Oxford University Press. ISBN 978-0-19-850841-0.

[6] Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p. 383.)

[1]

[2]

[3]

[4]

[5]

[6]