Tablas precisas de Gal

Las tablas precisas de Gal son un método ideado por Shmuel Gal en la década de 1980[1]​ para proporcionar valores precisos de funciones especiales, utilizando una tabla de búsqueda e interpolación. Es un método rápido y eficiente para generar valores de funciones como las funciones exponenciales o trigonométricas con una precisión de último bit para casi todos los valores de argumento sin utilizar aritmética de precisión extendida.

Procedimiento de cálculo

editar

La idea principal en las tablas precisas de Gal es una tabulación diferente para la función especial que se está calculando. Comúnmente, el rango se divide en varios subrangos, cada uno con valores precalculados y fórmulas de corrección. Para calcular la función, se busca el punto más cercano y se calcula una corrección en función de la distancia al punto buscado.

La idea de Gal es no calcular previamente valores equidistantes, sino perturbar los puntos x de modo que tanto x como f(x) sean casi exactamente representables en el formato numérico elegido. Mediante la búsqueda en aproximadamente 1000 valores a cada lado del valor de x que se desea, se puede encontrar un valor tal que f (x) se puede representar con menos de ± 1/2000 bit de error de redondeo. Si la corrección también se calcula con una precisión de ± 1/2000 bit (que no requiere precisión adicional de punto flotante siempre que la corrección sea menor que 1/2000, la magnitud del valor almacenado f(x) y la corrección calculada está a más de ± 1/1000 de bit de exactamente medio bit (el caso de redondeo que requiere un cálculo más), entonces se sabe si el valor exacto de la función debe redondearse hacia arriba o hacia abajo.

La técnica proporciona una manera eficiente de calcular el valor de la función dentro de ± 1/1000 bit menos significativo, es decir, 10 bits adicionales de precisión. Si esta aproximación está a más de ± 1/1000 de un bit de distancia de exactamente la mitad de camino entre dos valores representables (que ocurre siempre excepto 2/1000 de las veces, es decir, en el 99.8% de los casos), entonces el resultado correctamente redondeado es claro.

Combinado con un algoritmo de recuperación de precisión extendida, esto puede calcular el resultado correctamente redondeado en un tiempo promedio muy razonable.

En tan solo el 0.2% de las veces (2 de cada 1000), se requiere una evaluación de la función de mayor precisión para resolver la incertidumbre del redondeo, pero esto es tan infrecuente que tiene poco efecto en el tiempo promedio de cálculo.[2]

El problema de generar valores de función que son precisos hasta el último bit se conoce como el dilema del creador de tablas.

Véase también

editar

Referencias

editar

Bibliografía

editar