31:
66:
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
106:
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
156:) 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"
111:
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
424:
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.)
223:
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
409:
371:
344:
317:
290:
399:
59:
213:
440:
395:
141:
363:
Business
Intelligence: First European Summer School, EBISS 2011, Paris, France, July 3-8, 2011, Tutorial Lectures
76:
148:" 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.,
173:
102:
Precomputing a set of intermediate results at the beginning of an algorithm's execution can often increase
249:
165:
149:
103:
387:
113:
133:
30:
254:
244:
232:
224:
35:
405:
367:
340:
313:
307:
286:
280:
228:
91:
361:
334:
132:
of values were used by people to speed up hand calculations of complex functions, such as in
137:
39:
333:
Karen Morton; Kerry
Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 October 2013).
186:
Examples of large-scale precomputation as part of modern efficient algorithms include:
153:
434:
391:
190:
169:
117:
79:, rather than computing their approximations to the necessary precision at run time.
195:
180:
129:
63:
259:
201:
145:
55:
120:
for intermediate input values, since interpolation is also a linear operation.
47:
227:
of the program code itself. Examples of this sort of precomputation include
108:
68:
17:
90:
is used to refer to storing the results of a precomputation, such as in a
220:
207:
83:
168:
often use precomputed lookup tables to either provide coefficients for
29:
309:
Data
Management and Query Processing in Semantic Web Databases
401:
The
History of Mathematical Tables From Sumer to Spreadsheets
282:
Data Mining: Concepts and
Techniques: Concepts and Techniques
72:
27:
Act of performing an initial computation before run time
360:
Marie-Aude
Aufaure; Esteban Zimányi (16 January 2012).
312:. Springer Science & Business Media. p. 178.
152:
wrote a 98-column multiplication table which gave (in
366:. Springer Science & Business Media. p. 43.
164:Even modern computer implementations of digital
216:precomputation for illumination in 3D graphics
144:School children are often taught to memorize "
8:
279:Jiawei Han; Micheline Kamber (9 June 2011).
210:for visibility calculations in 3D graphics
128:Before the advent of computers, printed
271:
172:algorithms or to initialise successive
7:
54:is the act of performing an initial
34:Part of a 20th-century precomputed
25:
71:mathematical constants, such as
1:
306:Sven Groppe (29 April 2011).
142:statistical density functions
398:; et al., eds. (2003).
404:. Oxford University Press.
457:
285:. Elsevier. p. 159.
183:involve precomputation.
174:approximation algorithms
166:trigonometric functions
388:Campbell-Kelly, Martin
339:. Apress. p. 48.
250:Algorithmic efficiency
150:Victorius of Aquitaine
104:algorithmic efficiency
43:
441:Software optimization
116:subset of values and
33:
134:trigonometric tables
255:Partial evaluation
245:Mathematical table
233:strength reduction
225:partial evaluation
44:
36:mathematical table
411:978-0-19-850841-0
373:978-3-642-27357-5
346:978-1-4302-6220-6
319:978-3-642-19357-6
292:978-0-12-381480-7
229:dataflow analysis
92:materialized view
40:common logarithms
16:(Redirected from
448:
425:
422:
416:
415:
384:
378:
377:
357:
351:
350:
330:
324:
323:
303:
297:
296:
276:
179:Many attacks on
140:, and tables of
138:logarithm tables
21:
456:
455:
451:
450:
449:
447:
446:
445:
431:
430:
429:
428:
423:
419:
412:
386:
385:
381:
374:
359:
358:
354:
347:
332:
331:
327:
320:
305:
304:
300:
293:
278:
277:
273:
268:
241:
162:
126:
100:
88:materialization
28:
23:
22:
15:
12:
11:
5:
454:
452:
444:
443:
433:
432:
427:
426:
417:
410:
396:Flood, Raymond
392:Croarken, Mary
379:
372:
352:
345:
336:Pro Oracle SQL
325:
318:
298:
291:
270:
269:
267:
264:
263:
262:
257:
252:
247:
240:
237:
218:
217:
211:
206:Precalculated
204:
198:
196:Perfect hashes
193:
191:Rainbow tables
161:
158:
154:Roman numerals
125:
122:
99:
96:
62:to generate a
52:precomputation
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
453:
442:
439:
438:
436:
421:
418:
413:
407:
403:
402:
397:
393:
389:
383:
380:
375:
369:
365:
364:
356:
353:
348:
342:
338:
337:
329:
326:
321:
315:
311:
310:
302:
299:
294:
288:
284:
283:
275:
272:
265:
261:
258:
256:
253:
251:
248:
246:
243:
242:
238:
236:
234:
230:
226:
222:
215:
212:
209:
205:
203:
199:
197:
194:
192:
189:
188:
187:
184:
182:
181:cryptosystems
177:
175:
171:
170:interpolation
167:
159:
157:
155:
151:
147:
143:
139:
135:
131:
130:lookup tables
123:
121:
119:
118:interpolating
115:
110:
105:
97:
95:
93:
89:
85:
80:
78:
74:
70:
65:
61:
57:
53:
49:
41:
37:
32:
19:
420:
400:
382:
362:
355:
335:
328:
308:
301:
281:
274:
219:
185:
178:
163:
146:times tables
127:
101:
87:
81:
64:lookup table
51:
45:
260:Memoization
202:cube attack
86:, the term
56:computation
18:Precomputed
266:References
48:algorithms
221:Compilers
214:Radiosity
208:BSP trees
84:databases
69:hardcoded
435:Category
239:See also
160:Examples
114:discrete
98:Overview
60:run time
235:steps.
124:History
109:caching
58:before
408:
370:
343:
316:
289:
406:ISBN
368:ISBN
341:ISBN
314:ISBN
287:ISBN
231:and
200:The
75:and
82:In
46:In
38:of
437::
394:;
390:;
176:.
136:,
94:.
50:,
414:.
376:.
349:.
322:.
295:.
77:e
73:π
42:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
