In algorithms, precomputation is the act of performing an initial computation

Computation

Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

 before run time to generate a lookup table

Lookup table

In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...

 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 π

Pi

' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...

 and e

E (mathematical constant)

The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...

, 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

Algorithmic efficiency

In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...

 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

Cache

In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...

 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

Discrete mathematics

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...

 subset of values and interpolating for intermediate input values, since interpolation is also a linear operation.

History

Before the advent of computers, printed lookup table

Lookup table

In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...

s of values were used by people to speed up hand calculations of complex functions, such as in trigonometric tables, logarithm tables

Common logarithm

The common logarithm is the logarithm with base 10. It is also known as the decadic logarithm, named after its base. It is indicated by log10, or sometimes Log with a capital L...

, and tables of statistical density functions
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

Victorius of Aquitaine

Victorius of Aquitaine, a countryman of Prosper of Aquitaine and also working in Rome, produced in 457 an Easter Cycle, which was based on the consular list provided by Prosper's Chronicle. This dependency caused scholars to think that Prosper had been working on his own Easter Annals for quite...

 wrote a 98-column multiplication table which gave (in Roman numerals

Roman numerals

The numeral system of ancient Rome, or Roman numerals, uses combinations of letters from the Latin alphabet to signify values. The numbers 1 to 10 can be expressed in Roman numerals as:...

) 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"

Examples

Even modern computer implementations of digital trigonometric algorithms often use precomputed lookup tables to either provide coefficients for interpolation

Interpolation

In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....

 algorithms or to initialise successive approximation algorithms.

Many attacks on cryptosystem

Cryptosystem

There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...

s involve precomputation.

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

• Rainbow table
  Rainbow table
  A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering the plaintext password, up to a certain length consisting of a limited set of characters. It is a form of time-memory tradeoff, using less...
  
  s
• Perfect hashes
• The cube attack
  Cube attack
  The cube attack is a method of cryptanalysis applicable to a wide variety of symmetric-key algorithms, published by Itai Dinur and Adi Shamir in a September 2008 preprint...
  
  
• Precalculated BSP trees for visibility calculations in in 3D graphics
• Radiosity precomputation for illumination in 3D graphics

Compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

s 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

Partial evaluation

In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way...

 of the program code itself. Examples of this sort of precomputation include dataflow analysis and strength reduction

Strength reduction

Strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array...

steps.