Algoritmo de la raíz cuadrada inversa rápida
La raíz cuadrada inversa rápida, a veces conocida como Fast InvSqrt() o por la constante hexadecimal 0x5F3759DF, es un algoritmo que estima
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 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.
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.
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.
La raíz cuadrada de un número en coma flotante se utiliza para calcular un vector unitario.
Los programas pueden utilizar vectores unitarios para determinar los ángulos de incidencia y reflexión.
En aquella la época, la división en punto flotante era más larga comparada con la multiplicación; el algoritmo de la raíz cuadrada inversa rápida se saltó el paso de la división, proporcionando ventaja en el rendimiento.
y luego comprobar la aproximación mediante otro método hasta que se obtenía con un margen de error aceptable respecto al resultado correcto.
La clave de la raíz cuadrada inversa rápida era calcular directamente una aproximación utilizando la estructura de los números en punto flotante, demostrando ser más rápida que consultar estas tablas.
El algoritmo era aproximadamente cuatro veces más rápido que calcular la raíz cuadrada con otro método y obtener la inversa mediante la división en punto flotante.
El algoritmo genera resultados razonablemente precisos utilizando una única primera aproximación del método de Newton; sin embargo, es mucho más lento y menos preciso que usar la instrucción de SSE rsqrtss en los procesadores x86 también lanzados en 1999.
Los primeros pasos del algoritmo están ilustrados abajo: Interpretación como una representación en IEEE 32-bits: Reinterpretar este último patrón de bits como números en punto flotante da la aproximación
Según la biblioteca estándar de C, reinterpretar un valor en punto flotante como un número entero eliminándole el puntero puede llegar a causar comportamiento inesperado (comportamiento indefinido).
Esto también permite a la función trabajar en un contexto de constexpr.
Ya que el bit antes del punto en el significando es siempre 1, no necesita ser almacenado.
De esta forma, se calculan tres enteros sin signo.
se obtiene Y así, los tres campos de entero sin signo son: Estos campos se codifican como se muestra en la figura siguiente: La aproximación proporcionada por los primeros pasos del código puede ser refinada utilizando el método del Newton, el cual permite encontrar aproximaciones de los ceros o raíces de una función real.
El método de Newton propone que si hay una aproximación
Para los propósitos del motor de Quake III, sólo se utilizó una iteración.
Una segunda iteración se mantiene en el código pero fue marcada como comentario.
[4] El código fuente de Quake III Arena no se publicó hasta la QuakeCon 2005, pero ya en 2002 o 2003 aparecieron copias del código de raíz cuadrada inversa rápida en Usenet y otros foros.
La especulación inicial apuntaba a John Carmack como el probable autor del código, pero los autores originales demostraron estar mucho más atrás en la historia de los gráficos 3D por computadora.
Rys Sommefeldt concluyó que el algoritmo original fue diseñado por Greg Walsh en Ardent Computer en consulta con Cleve Moler, el creador de MATLAB.
Cleve Moler se enteró de este truco gracias al código escrito por William Kahan y K.C.
