Content deleted Content added
mNo edit summary |
No edit summary |
||
Line 4:
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.
== History ==
[[Image:Abramowitz&Stegun.page97.agr.jpg|thumb|Part of a 20th century table of [[common logarithm]]s in the reference book [[Abramowitz and Stegun]].]]
Before the advent of computers, printed [[lookup table]]s of values were used by people to speed up hand calculations of complex functions, such as in [[trigonometric table]]s, [[Common logarithm|logarithm tables]], and tables of [[statistical density function]]s<ref>{{cite book
Line 30 ⟶ 31:
|id=
}}
</ref>
School children are often taught to memorize "[[times table]]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]] 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" <ref>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.)</ref>
== Examples ==
Even modern computer implementations of digital [[trigonometric algorithm]]s often use precomputed lookup tables to either provide coefficients for [[interpolation]] algorithms or to initialise [[successive approximation]] algorithms.
| |||