Precomputation

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.

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.

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] 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.

Examples of this sort of precomputation include dataflow analysis and strength reduction steps.