precomputation

Precomputation refers to the phase in which certain computations are performed before the main execution of a program or system, with the results stored for later use. The goal is to reduce the time required for frequent operations by trading off extra upfront computation and memory for faster online responses. Precomputation is common in algorithm design, data structures, cryptography, simulations, and databases.

Examples include precomputed lookup tables for functions, caches and memoization in dynamic programming, and sieve techniques that generate lists of primes in advance. In graphics, precomputed shading or lighting tables speed rendering. In cryptography, tables of discrete logarithms or hashes can speed up repeated operations under a fixed context. In numerical computing, precomputed values of expensive transcendental functions or interpolation grids are used.

Key considerations include the time and space required to perform and store the precomputation, the frequency of the queried operations, and how often inputs change, which affects cache invalidation. The primary design trade-off is time versus space and the online speedup versus maintenance cost. Improper precomputation can waste resources or expose stale data.

Related concepts include memoization, caching, and the broader time-space trade-off in algorithms. Precomputation can enable real-time systems by reducing latency and allow large problems to be solved incrementally through offline work.