Algoritmo de la raíz cuadrada inversa rápida
De Wikipedia, la enciclopedia encyclopedia
La raíz cuadrada inversa rápida, a veces conocida como Fast InvSqrt() o por la constante hexadecimal 0x5F3759DF, es un algoritmo que estima , el recíproco (o inverso multiplicativo) de la raíz cuadrada de un número en punto flotante de 32 bits. Esta operación se utiliza en el procesamiento digital de señales para normalizar un vector, es decir, convertirlo en un vector de módulo 1. Por ejemplo, los programas de gráficos por ordenador utilizan las raíces cuadradas inversas para calcular los ángulos de incidencia y reflexión para la iluminación y el sombreado. El algoritmo es más conocido por su implementación en 1999 en el código fuente del videojuego de disparos en primera persona Quake III Arena, que hacía un gran uso de los gráficos en 3D. El algoritmo no empezó a aparecer en foros públicos como Usenet hasta 2002 o 2003. El cálculo de las raíces cuadradas suele depender de muchas operaciones de división, que para los números en coma flotante son computacionalmente costosas. El cuadrado inverso rápido genera una buena aproximación con un solo paso de división. Se han descubierto otros videojuegos anteriores a Quake 3 que utilizan un algoritmo similar, aunque la implementación de Quake sigue siendo el ejemplo más conocido.
El algoritmo acepta un número en coma flotante de 32 bits como entrada y almacena un valor dividido a la mitad para su uso posterior. A continuación, tratando los bits que representan el número en punto flotante como un entero de 32 bits, se realiza un desplazamiento lógico a la derecha de un bit y el resultado se resta del número 0x5F3759DF (en notación decimal: 1.597.463.007), que es una representación en punto flotante de una aproximación de . Esto resulta en la primera aproximación de la raíz cuadrada inversa de la entrada. Tratando los bits de nuevo como un número en punto flotante, se ejecuta una iteración del método de Newton, produciendo una aproximación más precisa.
El algoritmo se atribuyó originalmente a John Carmack, pero una investigación demostró que el código tenía raíces más profundas tanto en el hardware como en el software de los gráficos por ordenador. Los ajustes y alteraciones pasaron por Silicon Graphics y 3dfx Interactive, y la constante original se derivó de una colaboración entre Cleve Moler y Gregory Walsh, mientras Gregory trabajaba para Ardent Computing a finales de la década de los 80. Walsh y Moler adaptaron su versión a partir de un documento inédito de William Kahan y K.C. Ng difundido en mayo de 1986.
Con los posteriores avances en el hardware, especialmente los rsqrtss
en instrucciones SSE para x86, este método no es aplicable en general a la informática de propósito general, aunque sigue siendo un ejemplo interesante históricamente, así como para máquinas más limitadas, como los sistemas de bajo coste. Sin embargo, cada vez son más los fabricantes que incluyen aceleradores trigonométricos y otros aceleradores matemáticos como CORDIC, obviando la necesidad de estos algoritmos.