En algoritmos , el cálculo previo es el acto de realizar un cálculo inicial antes del tiempo de ejecución para generar una tabla de búsqueda que puede ser utilizada por un algoritmo para evitar cálculos repetidos cada vez que se ejecuta. El cálculo previo se utiliza 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 tiempo de ejecución.
En las bases de datos , el término materialización se utiliza para referirse al almacenamiento de los resultados de un cálculo previo, [1] [2] como en una vista materializada . [3] [4]
Precalcular un conjunto de resultados intermedios al comienzo de la ejecución de un algoritmo a menudo puede aumentar sustancialmente la eficiencia algorítmica . Esto resulta ventajoso cuando una o más entradas se limitan 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 los retrasos en el almacenamiento en caché ), cualquier algoritmo con un componente que tenga una eficiencia peor que constante en un rango de entrada pequeño se puede mejorar 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 valores de entrada intermedios, ya que la interpolación también es una operación lineal.
Antes de la llegada de las computadoras, las personas utilizaban tablas de búsqueda de valores impresas para acelerar los cálculos manuales de funciones complejas, como en tablas trigonométricas , tablas de logaritmos y tablas de funciones estadísticas de densidad [5] A los niños en edad escolar a menudo se les enseña a memorizar " Tablas de multiplicar " para evitar cálculos de los números más utilizados (hasta 9 x 9 o 12 x 12). Ya en el año 493 d.C., Victorio de Aquitania escribió una tabla de multiplicar 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 comenzaban con mil, descendiendo por centenas a cien, luego descendiendo de decenas a diez, luego de unidades a uno, y luego las fracciones hasta 1/144" [6]
Incluso las implementaciones informáticas modernas de funciones trigonométricas digitales suelen utilizar tablas de búsqueda precalculadas para proporcionar coeficientes para algoritmos de interpolación o para inicializar algoritmos de aproximación sucesivos .
Muchos ataques a los criptosistemas implican cálculo previo.
Ejemplos de precomputación a gran escala como parte de algoritmos modernos y eficientes incluyen:
Los compiladores utilizan ampliamente el cálculo previo como un medio para aumentar la velocidad de ejecución del código resultante: este cálculo previo puede considerarse, de hecho, como una forma de evaluación parcial del código del programa en sí. Ejemplos de este tipo de cálculo previo incluyen análisis de flujo de datos y pasos de reducción de fuerza .