En algoritmos , el precálculo es el acto de realizar un cálculo inicial antes del tiempo de ejecución para generar una tabla de búsqueda que un algoritmo puede usar para evitar cálculos repetidos cada vez que se ejecuta. El precálculo se usa a menudo en algoritmos que dependen de los resultados de cálculos costosos que no dependen de la entrada del algoritmo. Un ejemplo trivial de precálculo es el uso de constantes matemáticas codificadas , como π y e , en lugar de calcular sus aproximaciones con la precisión necesaria en el tiempo de ejecución.
En bases de datos , el término materialización se utiliza para referirse al almacenamiento de los resultados de un precálculo, [1] [2] como en una vista materializada . [3] [4]
El cálculo previo de un conjunto de resultados intermedios al comienzo de la ejecución de un algoritmo puede a menudo aumentar sustancialmente la eficiencia del algoritmo . Esto resulta ventajoso cuando una o más entradas están restringidas a un rango lo suficientemente pequeño como para que los resultados puedan almacenarse en un bloque de memoria de tamaño razonable. Debido a que el acceso a la memoria es esencialmente constante en complejidad temporal (excepto por los retrasos de almacenamiento en caché ), cualquier algoritmo con un componente que tenga una eficiencia peor que constante en un rango de entrada pequeño puede mejorarse mediante el cálculo previo de valores. En algunos casos, se pueden obtener algoritmos de aproximación eficientes calculando un subconjunto discreto de valores e interpolando para valores de entrada intermedios, ya que la interpolación también es una operación lineal.
Antes de la llegada de las computadoras, las tablas de búsqueda de valores impresas eran utilizadas por la gente para acelerar los cálculos manuales de funciones complejas, como en las tablas trigonométricas , las tablas de logaritmos y las tablas de funciones de densidad estadística [5]. A los niños en edad escolar se les suele enseñar a memorizar las " tablas de multiplicación " para evitar los cálculos de los números más utilizados (hasta 9 x 9 o 12 x 12). Incluso en el año 493 d. C., Victorio de Aquitania escribió una tabla de multiplicación de 98 columnas que daba (en números romanos ) el producto de cada número de 2 a 50 veces y las filas eran "una lista de números que empezaba con mil, descendía de centenas a cien, luego descendía de decenas a diez, luego de unos a uno, y luego las fracciones hasta 1/144" [6].
Incluso las implementaciones informáticas modernas de funciones trigonométricas digitales a menudo utilizan tablas de búsqueda precalculadas para proporcionar coeficientes para algoritmos de interpolación o para inicializar algoritmos de aproximación sucesivos .
Muchos ataques a criptosistemas implican precomputación.
Algunos ejemplos de precomputación a gran escala como parte de algoritmos modernos y eficientes incluyen:
Los compiladores utilizan ampliamente el precálculo como un medio para aumentar la velocidad de ejecución del código resultante: este precálculo puede considerarse, en efecto, una forma de evaluación parcial del código del programa en sí. Algunos ejemplos de este tipo de precálculo incluyen el análisis del flujo de datos y los pasos de reducción de la fuerza .