Algoritmo inverso rápido de raíz cuadrada
El algoritmo de inversión rápida de raíz cuadrada es el siguiente:
I. Algoritmo rápido
El algoritmo de inversión rápida de raíz cuadrada es una raíz cuadrada aritmética adecuada para calcular rápidamente. el producto (en lo sucesivo denominado algoritmo inverso (raíz cuadrada) (debe tomar un número de coma flotante de 32 bits que cumpla con el formato estándar IEEE754). ). Este algoritmo probablemente fue inventado por primera vez por SGI a principios de la década de 1990 y luego se utilizó en el código fuente de Quake III Arena de 1999.
Pero no fue hasta 2002-2003 que este algoritmo apareció en foros públicos como Usenet. La ventaja de este algoritmo es que reduce la enorme sobrecarga computacional que implica encontrar la raíz cuadrada recíproca de una operación de punto flotante, que a menudo se requiere en gráficos por computadora para lidiar con ángulos fluctuantes y reflejos de iluminación y proyecciones.
Origen
Originalmente se pensó que el algoritmo de velocidad inversa de raíz cuadrada había sido inventado por John Carmack, pero una investigación posterior reveló que el algoritmo se había utilizado en hardware y software de gráficos por computadora antes de eso. , y se ha utilizado en productos SGI y 3dfx. Se entiende que este algoritmo fue utilizado por primera vez por Gary-Tarolli. El origen de esta constante sigue siendo desconocido hasta el día de hoy, aunque en estudios posteriores se han propuesto varias fuentes posibles.
La raíz cuadrada recíproca de un número de punto flotante se usa a menudo para calcular vectores regularizados, que se utilizan en programas de gráficos tridimensionales que utilizan vectores regularizados para lograr efectos de iluminación y proyección que requieren millones de operaciones por segundo. Cálculo de la raíz cuadrada recíproca. Antes de la aparición de dispositivos de hardware especiales para manejar la transformación de coordenadas y la iluminación, estos cálculos se realizaban mediante software, que era muy lento. Antes de la llegada de dispositivos de hardware especializados para manejar transformaciones de coordenadas y fuentes de luz, estos cálculos se realizaban en software y la velocidad de cálculo era muy lenta.
Tres números de punto flotante
Para comprender este código, primero debe comprender el formato de los números de punto flotante. Un número de punto flotante con 32 bits binarios representa un número racional, y estos 32 bits se dividen en tres partes según su significado: primero, el primer bit es el bit de signo, si es 0, es un número positivo, en caso contrario es un número negativo; los siguientes 8 bits están desplazados (para hacer posible la representación -127-128); los últimos 23 bits son el número de dígitos significativos, excepto el bit más alto;
La estructura anterior está representada por una fórmula, donde la mantisa (en este caso el desplazamiento) y el valor del exponente determinan si los dígitos significativos (llamados mantisa en el artículo de Lomont y McEniry) representan decimales o números enteros. Tome la imagen de arriba como ejemplo y descríbala como (), luego el número de punto flotante que representa es.