La raíz cuadrada inversa rápida , a veces denominada Fast InvSqrt () o por la constante hexadecimal 0x5F3759DF , es un algoritmo que estima 1 ⁄ √ x , el recíproco (o inverso multiplicativo) de la raíz cuadrada de un número de coma flotante de 32 bits. x en formato de coma flotante IEEE 754 . Esta operación se utiliza en el procesamiento de señales digitales para normalizar un vector, es decir, escalarlo a la longitud 1. Por ejemplo, los programas de gráficos por computadora usan raíces cuadradas inversas para calcularángulos de incidencia y reflexión para iluminación y sombreado . El algoritmo es mejor conocido por su implementación en 1999 en el código fuente de Quake III Arena , un videojuego de disparos en primera persona que hizo un uso intensivo de gráficos 3D . El algoritmo solo comenzó a aparecer en foros públicos como Usenet en 2002 o 2003. [1] [nota 1] En ese momento, en general era computacionalmente costoso calcular el recíproco de un número de punto flotante, especialmente a gran escala; la raíz cuadrada inversa rápida pasó por alto este paso.
El algoritmo acepta un número de coma flotante de 32 bits como entrada y almacena un valor reducido a la mitad para su uso posterior. Entonces, el tratamiento de los bits que representan el número de coma flotante como un entero de 32 bits, un desplazamiento lógico a la derecha por un bit se lleva a cabo y el resultado resta del número 0x 5F3759DF, que es una representación de punto flotante de una aproximación de √ 2 127 . [3] Esto da como resultado la primera aproximación de la raíz cuadrada inversa de la entrada. Tratando los bits nuevamente como un número de punto flotante, 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 mostró que el código tenía raíces más profundas tanto en el hardware como en el software de los gráficos por computadora. Los ajustes y alteraciones pasaron por Silicon Graphics y 3dfx Interactive , con la implementación de Gary Tarolli para SGI Indigo como el primer uso conocido. No se sabe cómo se derivó originalmente la constante, aunque la investigación ha arrojado algo de luz sobre los posibles métodos. [ cita requerida ]
Con los subsiguientes avances de hardware, especialmente la instrucción SSE x86 , este método no es generalmente aplicable a la computación moderna, [4] aunque sigue siendo un ejemplo interesante tanto históricamente [5] como para máquinas más limitadas, como sistemas embebidos de bajo costo. Sin embargo, más fabricantes de sistemas integrados están incluyendo aceleradores trigonométricos y otros aceleradores matemáticos como CORDIC , obviando la necesidad de tales algoritmos.rsqrtss
Motivación
La raíz cuadrada inversa de un número de coma flotante se utiliza para calcular un vector normalizado . [6] Los programas pueden utilizar vectores normalizados para determinar ángulos de incidencia y reflexión . Los programas de gráficos 3D deben realizar millones de estos cálculos cada segundo para simular la iluminación. Cuando se desarrolló el código a principios de la década de 1990, la mayor parte de la potencia de procesamiento de punto flotante estaba por detrás de la velocidad del procesamiento de números enteros. [1] Esto era problemático para los programas de gráficos 3D antes de la llegada del hardware especializado para manejar la transformación y la iluminación .
La longitud del vector se determina calculando su norma euclidiana : la raíz cuadrada de la suma de cuadrados de los componentes del vector . Cuando cada componente del vector se divide por esa longitud, el nuevo vector será un vector unitario que apunta en la misma dirección. En un programa de gráficos 3D, todos los vectores están en un espacio tridimensional , por lo que v sería un vector ( v 1 , v 2 , v 3 ) .
es la norma euclidiana del vector.
es el vector (unitario) normalizado, usando || v || 2 para representar v2
1+ v2
2+ v2
3.
que relaciona el vector unitario con la raíz cuadrada inversa de los componentes de la distancia. La raíz cuadrada inversa se puede utilizar para calcular v̂ porque esta ecuación es equivalente a
donde el término fraccionario es la raíz cuadrada inversa de || v || 2 .
En ese momento, la división de coma flotante era generalmente cara en comparación con la multiplicación; el algoritmo de raíz cuadrada inversa rápida pasó por alto el paso de división, lo que le dio su ventaja de rendimiento. Quake III Arena , un videojuego de disparos en primera persona , utilizó el algoritmo de raíz cuadrada inversa rápida para acelerar el cálculo de gráficos, pero desde entonces el algoritmo se ha implementado en algunos sombreadores de vértices de hardware dedicados que utilizan matrices de puertas programables en campo (FPGA). [7]
Resumen del código
El siguiente código es la implementación rápida de raíz cuadrada inversa de Quake III Arena , despojada de las directivas del preprocesador de C , pero que incluye el texto del comentario original exacto: [8]
float Q_rsqrt ( número flotante ) { i largo ; flotar x2 , y ; const float threehalfs = 1.5F ; x2 = número * 0.5F ; y = número ; i = * ( largo * ) & y ; // pirateo maligno de nivel de bits de punto flotante i = 0x5f3759df - ( i >> 1 ); // ¿Qué carajo? y = * ( flotante * ) & i ; y = y * ( tres mitades - ( x2 * y * y ) ); // 1ra iteración // y = y * (tres mitades - (x2 * y * y)); // 2da iteración, esto se puede eliminarreturn y ; }
En ese momento, el método general para calcular la raíz cuadrada inversa era calcular una aproximación para 1 ⁄ √ x , luego revise esa aproximación a través de otro método hasta que se encuentre dentro de un rango de error aceptable del resultado real. Los métodos de software comunesa principios de la década de 1990 obtuvieron aproximaciones de unatabla de búsqueda. [9] La clave de la raíz cuadrada inversa rápida era calcular directamente una aproximación utilizando la estructura de números de punto flotante, lo que resulta más rápido que las búsquedas de tablas. El algoritmo fue aproximadamente cuatro veces más rápido que calcular la raíz cuadrada con otro método y calcular el recíproco mediante la división de punto flotante. [10] El algoritmo fue diseñado con laespecificación de punto flotante de 32 bitsIEEE 754-1985en mente, pero la investigación de Chris Lomont mostró que podría implementarse en otras especificaciones de punto flotante. [11]
Las ventajas en velocidad que ofrece el truco de la raíz cuadrada inversa rápida provienen de tratar la palabra de coma flotante de 32 bits [nota 2] como un número entero , y luego restarla de una constante " mágica ", 0x 5F3759DF . [1] [12] [13] [14] Esta resta de enteros y desplazamiento de bits dan como resultado un patrón de bits que, cuando se redefine como un número de punto flotante, es una aproximación aproximada de la raíz cuadrada inversa del número. Se realiza una iteración del método de Newton para obtener cierta precisión y el código está terminado. El algoritmo genera resultados razonablemente precisos utilizando una primera aproximación única para el método de Newton ; sin embargo, es mucho más lento y menos preciso que usar la instrucción SSErsqrtss
en procesadores x86 también lanzada en 1999. [4] [15]
De acuerdo con el estándar C, se considera que reinterpretar un valor de punto flotante como un número entero quitando el puntero a él puede causar un comportamiento inesperado ( comportamiento indefinido ). Este problema podría evitarse utilizando la función de biblioteca memcpy
. El siguiente código sigue los estándares de C, aunque a costa de necesitar una variable adicional y más memoria: el valor de punto flotante se coloca en una unión anónima que contiene un miembro entero sin signo adicional de 32 bits, y los accesos a ese entero proporcionan un bit vista de nivel del contenido del valor de punto flotante.
#include // uint32_tfloat Q_rsqrt ( número flotante ) { const float x2 = número * 0.5F ; const float threehalfs = 1.5F ; union { float f ; uint32_t i ; } conv = { . f = número }; conv . i = 0x5f3759df - ( conv . i >> 1 ); conv . f * = tres mitades - ( x2 * conv . f * conv . f ); volver conv . f ; }
Sin embargo, el tipo de juego de palabras a través de una unión es un comportamiento indefinido en C ++. Un método correcto para hacer esto en C ++ es mediante std::bit_cast
. Eso también permite que la función funcione en constexpr
contexto.
// solo funciona después del estándar C ++ 20 #include #include ímites>#include constexpr float Q_rsqrt ( número flotante ) noexcept { static_assert ( std :: numeric_limits < float > :: is_iec559 ); // (habilitar solo en IEEE 754) float const y = std :: bit_cast < float > ( 0x5f3759df - ( std :: bit_cast < std :: uint32_t > ( número ) >> 1 )); return y * ( 1.5f - ( número * 0.5f * y * y )); }
Ejemplo resuelto
Como ejemplo, el número x = 0.15625 se puede usar para calcular1 ⁄ √ x ≈ 2,52982. Los primeros pasos del algoritmo se ilustran a continuación:
0011_1110_0010_0000_0000_0000_0000_0000 Patrón de bits de x e i0001_1111_0001_0000_0000_0000_0000_0000 Desplazar una posición a la derecha: (i >> 1)0101_1111_0011_0111_0101_1001_1101_1111 El número mágico 0x5F3759DF0100_0000_0010_0111_0101_1001_1101_1111 El resultado de 0x5F3759DF - (i >> 1)
Interpretación como representación IEEE de 32 bits:
0_01111100_01000000000000000000000 1.25 × 2 −3 0_00111110_00100000000000000000000 1.125 × 2 −65 0_10111110_01101110101100111011111 1.432430 ... × 2 63 0_10000000_01001110101100111011111 1.307430 ... × 2 1
La reinterpretación de este último patrón de bits como un número de coma flotante da la aproximación y = 2.61486 , que tiene un error de aproximadamente 3.4%. Después de una sola iteración del método de Newton , el resultado final es y = 2.52549 , un error de solo 0.17%.
Algoritmo
El algoritmo calcula 1 ⁄ √ x realizando los siguientes pasos:
- Alias el argumento x a un número entero como una forma de calcular una aproximación de log 2 ( x )
- Utilice esta aproximación para calcular una aproximación de log 2 ( 1 ⁄ √ x ) = −1/2 log 2 ( x )
- Alias de nuevo a un flotante, como una forma de calcular una aproximación de la exponencial base 2
- Refina la aproximación usando una sola iteración del método de Newton.
Representación de punto flotante
Dado que este algoritmo se basa en gran medida en la representación a nivel de bits de números de punto flotante de precisión simple, aquí se proporciona una breve descripción de esta representación. Para codificar un número real x distinto de cero como un flotador de precisión simple, el primer paso es escribir x como un número binario normalizado : [16]
donde el exponente e x es un número entero, m x ∈ [0, 1) , y 1. b 1 b 2 b 3 ... es la representación binaria del "significando" (1 + m x ) . Dado que el bit único antes del punto en el significado es siempre 1, no es necesario almacenarlo. A partir de esta forma, se calculan tres enteros sin signo: [17]
- S x , el "bit de signo", es 0 si x > 0 y 1 si x <0 (1 bit)
- E x = e x + B es el "exponente sesgado", donde B = 127 es el " sesgo del exponente " [nota 3] (8 bits)
- M x = m x × L , donde L = 2 23 [nota 4] (23 bits)
Luego, estos campos se empaquetan, de izquierda a derecha, en un contenedor de 32 bits. [18]
Como ejemplo, considere nuevamente el número x = 0.15625 = 0.00101 2 . Normalizando x rendimientos:
- x = +2 −3 (1 + 0,25)
y así, los tres campos enteros sin signo son:
- S = 0
- E = −3 + 127 = 124 = 0111 1100 2
- M = 0,25 × 2 23 =2 097 152 = 010 0000 0000 0000 0000 0000 2
estos campos están empaquetados como se muestra en la siguiente figura:
Aliasing a un número entero como un logaritmo aproximado
Si 1 ⁄ √ x se iba a calcular sin una computadora o una calculadora, unatabla de logaritmossería útil, junto con elregistro deidentidad b ( 1 ⁄ √ x ) = -1/2log b ( x ) , que es válido para todas las bases b . La raíz cuadrada inversa rápida se basa en esta identidad, y en el hecho de que aliasar un float32 a un entero da una aproximación aproximada de su logaritmo. Aquí es cómo:
Si x es un número normal positivo :
luego
y dado que m x ∈ [0, 1) , el logaritmo del lado derecho se puede aproximar mediante [19]
donde σ es un parámetro libre utilizado para ajustar la aproximación. Por ejemplo, σ = 0 produce resultados exactos en ambos extremos del intervalo, mientras que σ = 1/2 - 1 + ln (ln (2))/2ln (2)≈ 0.0430357 produce la aproximación óptima (la mejor en el sentido de la norma uniforme del error).
Por tanto, existe la aproximación
Interpretar el patrón de bits de coma flotante de x como un entero I x produce [nota 5]
Entonces parece que I x es una aproximación lineal escalonada y desplazada por partes de log 2 ( x ) , como se ilustra en la figura de la derecha. En otras palabras, log 2 ( x ) se aproxima por
Primera aproximación del resultado
El cálculo de y = 1 ⁄ √ x se basa en la identidad
Usando la aproximación del logaritmo anterior, aplicada tanto a x como a y , la ecuación anterior da:
Por tanto, una aproximación de I y es:
que está escrito en el código como
i = 0x5f3759df - ( i >> 1 );
El primer término de arriba es el número mágico
de lo cual se puede inferir que σ ≈ 0.0450466 . El segundo término,1/2I x , se calcula desplazando los bits de I x una posición a la derecha. [20]
Método de Newton
Con y como la raíz cuadrada inversa, f ( y ) = 1/y 2- x = 0 . La aproximación producida por los pasos anteriores se puede refinar utilizando un método de búsqueda de raíces , un método que encuentra el cero de una función . El algoritmo utiliza el método de Newton : si hay una aproximación, y n para y , entonces se puede calcular una mejor aproximación y n +1 tomando y n - f ( y n )/f ′ ( y n ), donde f ′ ( y n ) es la derivada de f ( y ) en y n . [21] Para el f ( y ) anterior ,
donde f ( y ) = 1/y 2- x y f ′ ( y ) = - 2/y 3.
Tratar y como un número de punto flotante, y = y*(threehalfs - x/2*y*y);
es equivalente a
Al repetir este paso, utilizando la salida de la función ( y n 1 ) como la entrada de la siguiente iteración, el algoritmo de causa y para converger a la raíz cuadrada inversa. [22] Para los propósitos del motor Quake III , solo se utilizó una iteración. Una segunda iteración permaneció en el código pero fue comentada . [14]
Precisión
Como se señaló anteriormente, la aproximación es sorprendentemente precisa. El gráfico único de la derecha traza el error de la función (es decir, el error de la aproximación después de que se ha mejorado ejecutando una iteración del método de Newton), para entradas que comienzan en 0.01, donde la biblioteca estándar da como resultado 10.0 , mientras que InvSqrt () da 9.982522, lo que hace la diferencia 0.017479, o 0.175% del valor verdadero, 10. El error absoluto solo cae a partir de ese momento, mientras que el error relativo permanece dentro de los mismos límites en todos los órdenes de magnitud.
Historia
El código fuente de Quake III no se publicó hasta QuakeCon 2005 , pero las copias del código de raíz cuadrada inversa rápida aparecieron en Usenet y otros foros ya en 2002 o 2003. [1] La especulación inicial apuntó a John Carmack como el probable autor del código, pero objetó y sugirió que fue escrito por Terje Mathisen, un programador de ensamblaje consumado que previamente había ayudado a id Software con la optimización de Quake . Mathisen había escrito una implementación de un código similar a fines de la década de 1990, pero los autores originales demostraron estar mucho más atrás en la historia de los gráficos por computadora en 3D con la implementación de Gary Tarolli para SGI Indigo como posible uso temprano conocido. 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 . [23] Cleve Moler aprendió sobre este truco del código escrito por William Kahan y KC Ng en Berkeley alrededor de 1986. [24] Jim Blinn también demostró una aproximación simple de la raíz cuadrada inversa en una columna de 1997 para IEEE Computer Graphics and Applications . [25] [26] Paul Kinney implementó un método rápido para la computadora FPS T Series [27] alrededor de 1986. El sistema incluía hardware de punto flotante vectorial que no era rico en operaciones enteras. Los valores de punto flotante se hicieron flotar para permitir la manipulación para crear la aproximación inicial.
Mejoras posteriores
número mágico
No se sabe con precisión cómo se determinó el valor exacto del número mágico. Chris Lomont desarrolló una función para minimizar el error de aproximación eligiendo el número mágico R en un rango. Primero calculó la constante óptima para el paso de aproximación lineal como 0x5F37642F , cerca de 0x5F3759DF , pero esta nueva constante dio un poco menos de precisión después de una iteración del método de Newton. [28] Luego, Lomont buscó un óptimo constante incluso después de una y dos iteraciones de Newton y encontró 0x5F375A86 , que es más preciso que el original en cada etapa de iteración. [28] Concluyó preguntando si el valor exacto de la constante original se eligió mediante derivación o prueba y error . [29] Lomont dijo que el número mágico para el doble de tipo de tamaño IEEE754 de 64 bits es 0x5FE6EC85E7DE30DA , pero luego Matthew Robertson demostró que era exactamente 0x5FE6EB50C7B537A9 . [30]
Jan Kadlec redujo el error relativo en un factor adicional de 2,7 ajustando las constantes en la iteración del método de Newton único, [31] llegando después de una búsqueda exhaustiva de
conv . i = 0x5F1FFFF9 - ( conv . i >> 1 ); conv . f * = 0,703952253f * ( 2,38924456f - x * conv . f * conv . f ); volver conv . f ;
Ahora está disponible un análisis matemático completo para determinar el número mágico para números de punto flotante de precisión simple. [32]
Cero hallazgo
Intermedio al uso de una o dos iteraciones del método de Newton en términos de velocidad y precisión es una sola iteración del método de Halley . En este caso, el método de Halley equivale a aplicar el método de Newton con la fórmula inicial. El paso de actualización es entonces
donde la implementación debe calcular solo una vez, a través de una variable temporal.
Ver también
- Métodos de cálculo de raíces cuadradas § Aproximaciones que dependen de la representación de coma flotante
- número mágico
Notas
- ^ Hubo una discusión en el foro de desarrolladores chino CSDN en 2000. [2]
- ^ El uso del tipo
long
reduce la portabilidad de este código en los sistemas modernos. Para que el código se ejecute correctamente,sizeof(long)
debe tener 4 bytes; de lo contrario, pueden producirse salidas negativas. En muchos sistemas modernos de 64 bits,sizeof(long)
es de 8 bytes. El reemplazo más portátil esint32_t
. - ^ E x debe estar en el rango [1, 254] para que x sea representable como un número normal .
- ^ Los únicos números reales que se pueden representar exactamente como punto flotante son aquellos para los que M x es un número entero. Otros números solo se pueden representar de forma aproximada redondeándolos al número exactamente representable más cercano.
- ^ S x = 0 ya que x > 0 .
Referencias
- ↑ a b c d Sommefeldt, Rys (29 de noviembre de 2006). "Origen del rápido InvSqrt () de Quake3" . Beyond3D . Consultado el 12 de febrero de 2009 .
- ^ "Discusión sobre CSDN" . Archivado desde el original el 2 de julio de 2015.
- ^ Munafo, Robert. "Propiedades notables de números específicos" . mrob.com . Archivado desde el original el 16 de noviembre de 2018.
- ^ a b Ruskin, Elan (16 de octubre de 2009). "Raíz cuadrada de sincronización" . Requiere ensamblaje . Consultado el 7 de mayo de 2015 .
- ^ feilipu. "z88dk es una colección de herramientas de desarrollo de software que apunta a las computadoras 8080 y z80" .
- ^ Blinn 2003 , p. 130.
- ^ Middendorf 2007 , págs. 155-164.
- ^ "quake3-1.32b / code / game / q_math.c" . Arena Quake III . id Software . Consultado el 21 de enero de 2017 .
- ^ Eberly 2001 , p. 504.
- ^ Lomont 2003 , p. 1.
- ^ Lomont 2003 .
- ^ Lomont 2003 , p. 3.
- ^ McEniry 2007 , p. 2, 16.
- ↑ a b Eberly , 2001 , p. 2.
- ^ Niebla, Agner. "Listas de latencias de instrucción, rendimientos y desgloses de microoperaciones para CPU Intel, AMD y VIA" (PDF) . Consultado el 8 de septiembre de 2017 .
- ^ Goldberg 1991 , p. 7.
- ^ Goldberg 1991 , págs. 15-20.
- ^ Goldberg 1991 , p. dieciséis.
- ^ McEniry 2007 , p. 3.
- ^ Hennessey y Patterson 1998 , p. 305.
- ^ Hardy 1908 , pág. 323.
- ^ McEniry 2007 , p. 6.
- ^ Sommefeldt, Rys (19 de diciembre de 2006). "Origen del rápido InvSqrt () de Quake3 - Segunda parte" . Beyond3D . Consultado el 19 de abril de 2008 .
- ^ Moler, Cleve. "Guerra espacial simpléctica" . MATLAB Central - El rincón de Cleve . MATLAB . Consultado el 21 de julio de 2014 .
- ^ Blinn 1997 , págs. 80-84.
- ^ "Implementación sqrt en fdlibm" .
- ^ Fazzari, Rod; Miles, Doug; Carlile, Brad; Groshong, Judson (1988). "Una nueva generación de hardware y software para la serie FPS T". Actas de la conferencia Array de 1988 : 75–89.
- ↑ a b Lomont , 2003 , p. 10.
- ^ Lomont 2003 , págs. 10-11.
- ^ Matthew Robertson (24 de abril de 2012). "Una breve historia de InvSqrt" (PDF) . UNBSJ.
- ^ Kadlec, enero (2010). "Řrřlog :: Mejora de la raíz cuadrada inversa rápida" (blog personal) . Consultado el 14 de diciembre de 2020 .
- ^ Moroz y col. 2018 .
Bibliografía
- Blinn, Jim (julio de 1997). "Trucos de punto flotante". Gráficos y aplicaciones informáticos IEEE . 17 (4): 80. doi : 10.1109 / 38.595279 .
- Blinn, Jim (2003). Rincón de Jim Blinn: notación, notación de notación . Morgan Kaufmann. ISBN 1-55860-860-5.
- Eberly, David (2001). Diseño de motor de juego 3D . Morgan Kaufmann. ISBN 978-1-55860-593-0.
- Goldberg, David (1991). "Lo que todo informático debería saber sobre la aritmética de punto flotante". Encuestas de computación ACM . 23 (1): 5–48. doi : 10.1145 / 103162.103163 . S2CID 222008826 .
- Hardy, Godfrey (1908). Un curso de matemáticas puras . Cambridge, Reino Unido : Cambridge University Press . ISBN 0-521-72055-9.
- Hennessey, John; Patterson, David A. (1998). Organización y Diseño de Computadoras (2ª ed.). San Francisco, CA: Morgan Kaufmann Publishers. ISBN 978-1-55860-491-9.
- Lomont, Chris (febrero de 2003). "Raíz cuadrada inversa rápida" (PDF) . Consultado el 13 de febrero de 2009 .
- McEniry, Charles (agosto de 2007). "Las matemáticas detrás del código de función de raíz cuadrada inversa rápida" (PDF) . Archivado desde el original (PDF) el 11 de mayo de 2015.
- Middendorf, Lars; Mühlbauer, Felix; Umlauf, George; Bodba, Christophe (1 de junio de 2007). "Embedded Vertex Shader en FPGA" (PDF) . En Rettberg, Achin (ed.). Diseño de sistemas integrados: temas, técnicas y tendencias . Conferencia de trabajo IFIP TC10: Simposio internacional de sistemas integrados (IESS). et al. Irvine, California : Springer. doi : 10.1007 / 978-0-387-72258-0_14 . ISBN 978-0-387-72257-3. Archivado (PDF) desde el original el 1 de mayo de 2019.
- Striegel, Jason (4 de diciembre de 2008). "Raíz cuadrada inversa rápida de Quake" . Hackszine . O'Reilly Media . Archivado desde el original el 15 de febrero de 2009 . Consultado el 7 de enero de 2013 .
- IEEE Computer Society (1985), 754-1985 - Estándar IEEE para aritmética binaria de punto flotante , Instituto de ingenieros eléctricos y electrónicos
- Moroz, Leonid V .; Walczyk, Cezary J .; Hrynchyshyn, Andriy; Holimath, Vijay; Cieslinski, Jan L. (enero de 2018). "Cálculo rápido de raíz cuadrada inversa con el uso de enfoque analítico constante mágica". Matemática Aplicada y Computación . Elsevier Science Inc. 316 (C): 245-255. arXiv : 1603.04483 . doi : 10.1016 / j.amc.2017.08.025 . S2CID 7494112 .
Otras lecturas
- Kushner, David (agosto de 2002). "La hechicería de Id". Espectro IEEE . 39 (8): 42–47. doi : 10.1109 / MSPEC.2002.1021943 .
enlaces externos
- 0x5f3759df , más investigaciones sobre la precisión y la generalización del algoritmo por Christian Plesner Hansen
- Origen del InvSqrt rápido de Quake3 ()
- Código fuente de Quake III Arena
- Implementación de InvSqrt en DESMOS
- "Raíz cuadrada inversa rápida: un algoritmo de Quake III" ( YouTube )