Entendiendo la Raíz Cuadrada Inversa Rápida de Quake
Un artículo y un artículo de investigación describen una forma rápida y aparentemente mágica de calcular la raíz cuadrada inversa (1 1/\sqrt{x}.), utilizada en el juego Quake.
No soy un experto en gráficos, pero aprecio por qué las raíces cuadradas son útiles. El teorema de Pitágoras calcula la distancia entre puntos, y la división por distancia ayuda a normalizar los vectores. (Normalizar a menudo es solo un término elegante para división.)
Juegos en 3D como Quake dividen por zillones de distancia (sí, zillones) de veces por segundo, por lo que las mejoras de rendimiento «menores» ayudan enormemente. No queremos tomar la raíz cuadrada y dividir de la manera normal: la exponenciación y la división son muy, muy caras para la CPU.
Dadas estas condiciones, aquí está la fórmula mágica para obtener Qu 1/\sqrt{x}$, como se encuentra en Quake (mis comentarios insertados):
Mi comprensión: Este increíble truco estima la raíz inversa utilizando el método de aproximación de Newton, y comienza con una gran conjetura inicial.
Para hacer la suposición, toma el número de punto flotante en notación científica, y niega & reduce a la mitad el exponente para obtener algo cercano a la raíz cuadrada inversa. Luego ejecuta una ronda del método de aproximación de Newton para refinar aún más la estimación y tada, tenemos algo cerca de la raíz cuadrada inversa.
Método de aproximación de Newton
El método de Newton se puede utilizar para encontrar raíces aproximadas de cualquier función. Puede seguir iterando el método para acercarse cada vez más a la raíz, pero esta función solo usa 1 paso. Aquí hay un curso intensivo sobre el método de Newton (era nuevo para mí):
Puedes seguir repitiendo este proceso (conectando tu nueva conjetura a la fórmula) y obtener aproximaciones más cercanas para tu raíz. Finalmente, usted tiene un «nuevo adivinar» que hace que f(nuevo supongo) muy, muy cerca de cero, es una raíz! (O lo suficientemente cerca para el trabajo del gobierno, como dicen).
Claramente, queremos que nuestro error sea lo más pequeño posible. Eso significa encontrar la » x » que hace que el error(x) = 0, que es lo mismo que encontrar la raíz de la ecuación de error. Si insertamos error (x) en la fórmula de aproximación de Newton:
y tomar los derivados adecuados:
podemos conectarlos para obtener la fórmula para una mejor suposición:
Que es exactamente la ecuación que ves en el código anterior, recordando que x es nuestra nueva conjetura (g) y «xhalf» es la mitad del valor original ($0.5 i$):
x = x*(1.5f - xhalf*x*x);
Con esta fórmula, podemos comenzar con una conjetura «g» y repetir la fórmula para obtener mejores conjeturas. Pruebe esta demostración para usar varias iteraciones para encontrar el cuadrado inverso:
Así que, amigos míos, la pregunta es: «¿Cómo podemos hacer una buena conjetura inicial?»
Hacer una buena suposición
¿Cuál es una buena suposición para la raíz cuadrada inversa? Es un poco una pregunta capciosa our nuestra mejor suposición para la raíz cuadrada inversa es la raíz cuadrada inversa en sí!
Ok hotshot, te preguntas, ¿cómo obtenemos realmente 1 1 / \sqrt{x}??
Aquí es donde entra en juego la magia. Digamos que tienes un número en forma de exponente o notación científica:
Ahora, si quieres encontrar la raíz cuadrada regular, dividirías el exponente por 2:
Y si desea la raíz cuadrada inversa, divida el exponente por -2 para voltear el signo:
Entonces, ¿cómo podemos obtener el exponente de un número sin otras operaciones costosas?
Los flotadores se almacenan en forma de exponente mantissa
Bueno, estamos de suerte. Los números de coma flotante son almacenados por computadoras en forma de exponente mantisa, por lo que es posible extraer y dividir el exponente.
Pero en lugar de hacer división explícitamente (caro para la CPU), el código usa otro truco inteligente: cambia bits. El desplazamiento a la derecha en una posición es lo mismo que dividir por dos (puedes probar esto para cualquier potencia de 2, pero truncará el resto). Y si quieres obtener un número negativo, en lugar de multiplicarlo por -1 (las multiplicaciones son caras), solo resta el número de «0» (las restas son baratas).
Por lo tanto, el código convierte el número de coma flotante en un entero. Luego cambia los bits por uno, lo que significa que los bits exponentes se dividen por 2 (cuando finalmente volvemos a convertir los bits en un flotador). Y por último, para negar el exponente, restamos del número mágico 0x5f3759df. Esto hace algunas cosas: preserva la mantisa (la parte no exponente, también conocida como 5 en :5 5 \cdot 10^6)), maneja exponentes impares-pares, cambiando bits del exponente a la mantisa, y todo tipo de cosas funky. El periódico tiene más detalles y explicaciones, no lo entendí todo la primera vez. Como siempre, siéntase libre de comentar si tiene una mejor explicación de lo que está sucediendo.
El resultado es que obtenemos una suposición inicial que es realmente cercana a la raíz cuadrada inversa real. Luego podemos hacer una sola ronda del método de Newton para refinar la suposición. Son posibles más rondas (a un costo computacional adicional), pero una ronda es todo lo que se necesita para la precisión necesaria.
Entonces, ¿por qué el número mágico?
El gran truco es cómo se almacenan los números enteros y los números de coma flotante. Números de coma flotante como 5 5.4 \ cdot 10^6 store almacena su exponente en un rango separado de bits que «5.4». Cuando cambias el número entero, divides el exponente por 2, así como también divides el número (5.4) por 2. Aquí es donde entra el número mágico does hace algunas correcciones geniales para esta división, que no entiendo del todo. Sin embargo, hay varios números mágicos que se podrían usar this este pasa a minimizar el error en la mantisa.
El número mágico también corrige los exponentes pares / impares; el documento menciona que también puede encontrar otros números mágicos para usar.
Recursos
Hay más discusión sobre reddit (usuario pb_zeppelin) y slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 y mi comentario
Otros Posts De Esta Serie
- Sistemas Numéricos y Bases
- La Guía Rápida de GUIDs
- Entendiendo la Raíz Cuadrada Inversa Rápida de Quake
- Una Introducción Simple A Las Redes Informáticas
- Intercambie dos variables usando XOR
- Entendiendo Pequeño Orden de bytes Endianos
- Unicode y Tú
- Un poco sobre formatos de archivo binarios
- Algoritmos de clasificación