Todo sobre la inversa rápida de la raíz cuadrada
El algoritmo
- El algoritmo de la inversa rápida de la raíz cuadrada se hizo famoso por el código fuente de Quake 3, y fue usado por John Carmack.
- Este algoritmo manipula los bits de un número de punto flotante para calcular rápidamente la inversa de su raíz cuadrada.
- Ejemplo de código:
float Q_rsqrt(float number) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = *(long*)&y; // hack a nivel de bits de punto flotante
i = 0x5f3759df - ( i >> 1 ); // constante mágica
y = *(float*)&i;
y = y * ( threehalfs - ( x2 * y * y ) ); // primera iteración
return y;
}
Punto flotante de 32 bits: representación
Punto flotante de 32 bits: interpretación de bits
- La representación interna del punto flotante normalmente no es importante para los programadores.
- Sin embargo, entender bien esta representación permite diseñar algoritmos eficientes.
- Si el patrón de bits de un punto flotante se interpreta como un entero, se obtiene una aproximación de la función logarítmica.
log2(x) ≈ Ix / L - B
Método de Newton
Conclusión
- Este algoritmo fue diseñado a partir de una comprensión profunda de los detalles matemáticos internos del sistema de punto flotante, aprovechando operaciones que se ejecutan rápidamente en una computadora.
- Aunque su origen no está del todo claro, es un ejemplo de ingeniería muy eficiente y bien diseñada.
La opinión de GN⁺
- Importancia histórica: este algoritmo fue un método innovador ideado para superar las limitaciones del hardware de aquella época.
- Valor educativo: ayuda mucho a entender la estructura interna del punto flotante y sus principios matemáticos.
- Aplicación moderna: en el hardware actual puede ser menos necesario, pero los principios del algoritmo siguen siendo útiles.
- Posibilidad de optimización: el valor de sus constantes puede optimizarse, lo que deja espacio para más investigación.
- Mirada crítica: en el hardware moderno puede haber métodos mejores, así que siempre es importante compararlo con la tecnología más reciente.
2 comentarios
Ese código curioso que vuelve a aparecer de vez en cuando... jaja
Comentarios en Hacker News
Soporte de instrucciones SSE: las computadoras fabricadas después de 1999 soportan el conjunto de instrucciones SSE, y pueden calcular rápidamente la inversa de la raíz cuadrada mediante la instrucción
_mm_rsqrt_ps.Avances del hardware moderno: en el hardware moderno, el cálculo de la inversa de la raíz cuadrada puede realizarse rápidamente en la CPU, y es un error pensar que todas las operaciones de punto flotante se descargan al GPU.
Implementación en MMIX: hay un ejemplo de código que implementa el cálculo de la inversa de la raíz cuadrada en lenguaje MMIX. Este código asume originalmente que el número es mayor que 2^-1021.
Error tipográfico en la fórmula: hay un error tipográfico en la fórmula de punto flotante. Debe corregirse a
(-1)^S.Interpretación del logaritmo: interpretar el patrón de bits sin procesar no es una aproximación lineal por tramos del logaritmo. Las líneas entre los puntos de datos no existen realmente.
Referencia en Wikipedia: hay una buena discusión sobre esta función y su historia en Wikipedia. Enlace de Wikipedia
Recopilación de código en GitHub: se reunió en GitHub algo de código relacionado. Enlace de GitHub
Referencia en StackOverflow: también vale la pena revisar una pregunta de StackOverflow sobre una aproximación optimizada de baja precisión. Enlace de StackOverflow
Experiencia en optimización de motores 3D: antes de Quake, ya se acumulaba experiencia construyendo motores 3D, y la optimización algorítmica siempre gana.
Recomendación de video en YouTube: hay un video interesante sobre este tema. Enlace de YouTube
Ladrón de tiempo productivo: este tema me absorbió y me quitó mucho tiempo productivo.
Número mágico óptimo: el número mágico del famoso fragmento de código no es la constante óptima. Es posible encontrar una constante mejor, y se puede buscar el número mágico óptimo con un cuaderno de Jupyter.