algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...

, precomputation is the act of performing an initial

computation Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm). Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...

before

run time Run(s) or RUN may refer to: Places * Run (island), one of the Banda Islands in Indonesia * Run (stream), a stream in the Dutch province of North Brabant People * Run (rapper), Joseph Simmons, now known as "Reverend Run", from the hip-hop group ...

to generate a

lookup table 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 v wi ...

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 Hard coding (also hard-coding or hardcoding) is the software development practice of embedding data directly into the source code of a computer program, program or other executable object, as opposed to obtaining the data from external sources or ...

mathematical constants, such as π and e, rather than computing their approximations to the necessary precision at run time. In

database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...

s, the term materialization is used to refer to storing the results of a precomputation, such as in a

materialized view In computing, a materialized view is a database object that contains the results of a query. For example, it may be a local copy of data located remotely, or may be a subset of the rows and/or columns of a table or join result, or may be a summary ...

Overview

Precomputing a set of intermediate results at the beginning of an algorithm's execution can often increase

algorithmic efficiency In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algor ...

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 Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory * Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a ...

subset of values and

interpolating In the mathematics, 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 engineering and science, one ...

for intermediate input values, since interpolation is also a linear operation.

History

Before the advent of computers, printed

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

trigonometric table 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 w ...

s, logarithm tables, and tables of statistical density functions School children are often taught to memorize "

times table In mathematics, a multiplication table (sometimes, less formally, a times table) is a mathematical table used to define a multiplication operation for an algebraic system. The decimal multiplication table was traditionally taught as an essenti ...

s" 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, a countryman of Prosper of Aquitaine and also working in Rome, produced in AD 457 an Easter Cycle, which was based on the consular list provided by Prosper's Chronicle. This dependency caused scholars to think that Prosper h ...

wrote a 98-column multiplication table which gave (in

Roman numerals Roman numerals are a numeral system that originated in ancient Rome and remained the usual way of writing numbers throughout Europe well into the Late Middle Ages. Numbers are written with combinations of letters from the Latin alphabet, eac ...

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

Examples

Even modern computer implementations of digital

trigonometric function In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all ...

s often use precomputed lookup tables to either provide coefficients for

interpolation 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 engineering and science, one often has a n ...

algorithms or to initialise successive

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

s. Many attacks on

cryptosystem In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, such as confidentiality (encryption). Typically, a cryptosystem consists of three algorithms: one for key generation, one for ...

s involve precomputation. Examples of large-scale precomputation as part of modern efficient algorithms include: *

Rainbow table A rainbow table is an efficient way to store data that has been computed in advance to facilitate cracking passwords. To protect stored passwords from compromise in case of a data breach, organizations avoid storing them directly, instead transfo ...

s *

Perfect hash In computer science, a perfect hash function for a set is a hash function that maps distinct elements in to a set of integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to impl ...

es * The

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. Attack A revised version of this preprint was placed online in January 20 ...

* Precalculated

BSP tree In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a represent ...

s for visibility calculations in 3D graphics * Radiosity precomputation for illumination in 3D graphics

Compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

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 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 that run faster than the originals while being guaranteed to ...

of the program code itself. Examples of this sort of precomputation include

dataflow analysis In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming. Software architecture Dataf ...

and

strength reduction In compiler construction, 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 ...

steps.

References

{{reflist Software optimization

Overview

History

Examples

See also

References