Precomputation: Difference between revisions

Revision as of 18:01, 1 May 2011

Revision as of 12:29, 19 August 2011

Line 1:

In [[algorithms]], '''Precomputation''' is the act of performing an initial [[computation]] before [[Run time (program lifecycle phase)|run time]] to generate results 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]] and [[E_(mathematical_constant)|e]], rather than computing their approximations to the necessary precision at run time.

'''Precomputation''' is the use in an [[algorithm]] of a (typically relatively expensive) initial [[computation]], the results of which are then used to speed up later parts of that algorithm. The precomputation step may often generate large [[data structure]]s as a result, but can be used to greatly reduce the effort required in the later stage.

== 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 [[cache|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 mathematics|discrete]] subset of values and [[interpolating]] for intermediate input values, since interpolation is also a linear operation.