Raíz cuadrada inversa rápida
El algoritmo de velocidad recíproca de raíz cuadrada es un algoritmo adecuado para calcular rápidamente el recíproco de la raíz cuadrada aritmética del producto (en lo sucesivo, raíz cuadrada) ( en este caso, se requiere un formato estándar IEEE754 de 32 bits (número de punto flotante). Este algoritmo probablemente fue inventado por primera vez por SGI a principios de la década de 1990 y luego implementado en el código fuente de Quake III Arena en 1999, pero no apareció en foros públicos como grupos de noticias hasta 2002-2003.
La ventaja de este algoritmo es que reduce el enorme coste computacional que provocan las operaciones de coma flotante al calcular el recíproco de la raíz cuadrada. En el campo de los gráficos por computadora, si desea calcular el ángulo de fluctuación y el efecto de reflexión de la iluminación y la proyección, a menudo es necesario calcular el recíproco de la raíz cuadrada.
Este algoritmo primero recibe un número de punto flotante con signo de 32 bits, luego lo trata como un entero de 32 bits, lo desplaza hacia la derecha una vez (toma la mitad y réstalo con el "número mágico" hexadecimal). 0x5f3759df, de esta manera se puede obtener la primera aproximación del recíproco de la raíz cuadrada del número de punto flotante de entrada.
Luego se usa nuevamente como el número de punto flotante original y se usa el método de iteración de Newton. se utiliza para iterar para obtener una aproximación más precisa hasta que se obtenga la aproximación requerida. Al calcular el valor aproximado de la raíz cuadrada recíproca de un número de punto flotante, este algoritmo es 4 veces más rápido que usar la división de punto flotante directamente. /p>
Origen del algoritmo
El algoritmo de velocidad recíproca de raíz cuadrada es el más antiguo. Se cree que fue inventado por John Carmack, pero investigaciones posteriores revelaron que el algoritmo tenía aplicaciones previas en ambos. campos de hardware y software de gráficos por computadora, como SGI y 3dfx. Hasta donde sabemos, este algoritmo fue desarrollado por primera vez por Gary Tarolli en 2016. Utilizado en el desarrollo de SGI Indigo, el origen de esta constante aún no está claro, aunque es posible. Se han sugerido fuentes en investigaciones relacionadas posteriores.
Como se mencionó anteriormente, hay representaciones en complemento a dos. El primer bit de un entero positivo con signo es 0, y los siguientes bits se utilizan para representar su valor. El número de punto flotante tiene un alias y se almacena como un número entero, el valor del número entero es, donde e representa el exponente y m representa el número significativo de la figura anterior. Por ejemplo, si las muestras en la figura se procesan como números de punto flotante; Es fácil saber que el valor del modelo entero obtenido por la transformación es
Debido a que la función recíproca de la raíz cuadrada solo puede manejar números positivos, los números de punto flotante (es decir, los anteriores) El signo. bit de Si) debe ser 0, lo que garantiza que el entero con signo convertido también debe ser un número positivo. La transformación anterior brinda viabilidad a los cálculos posteriores. El primer paso es desplazar la lógica de operación hacia la derecha en un bit. , divide la forma entera larga del número por 2.