0x5f375a86 es un número mágico.
En una coincidencia fortuita, me encontré con este número hexadecimal mágico 0x5f3759df y decidí tomar nota de ello.
La ciencia cambia el mundo, las matemáticas cambian la ciencia.
La última vez me encontré con un número irracional, 0.75, que aparece en el código fuente de Java HashMap y representa el factor de carga predeterminado. Permíteme explicarte brevemente el significado de este valor: cuando la capacidad de HashMap alcanza el 75% de su capacidad total (es decir, cuando hay 12 elementos en una capacidad de 16), se realiza una operación de redimensionamiento para reducir las colisiones de hash y evitar que HashMap se degrade a una lista enlazada, lo que aumentaría significativamente el tiempo de búsqueda. ¿Por qué se eligió el valor 0.75? La explicación es bastante simple: es un compromiso entre la utilización eficiente del espacio y la reducción de los costos de búsqueda, basado principalmente en la distribución de Poisson, y 0.75 minimiza las colisiones.
Bueno, puedo aceptar esta explicación y también puedo aceptar el valor 0.75, pero no puedo imaginar cómo se obtuvo este 0x5f3759df, es algo completamente incomprensible para mí. A continuación, se presenta un poco de información de fondo y una introducción al código de este número mágico, citado en parte de Zhihu: ¿Cuál es la base matemática de la constante en el algoritmo de raíz cuadrada rápida 0x5f3759df? y otro blog: Principios matemáticos de 0x5f3759df; puedes leer la versión en chino aquí: La belleza de las matemáticas: el número mágico 0x5f3759df en el algoritmo de cálculo rápido de raíces cuadradas.
Quake-III Arena es uno de los juegos clásicos de los años 90.
Esta serie de juegos no solo tiene buenos gráficos y contenido, sino que también se puede jugar de manera extremadamente fluida incluso en computadoras con una configuración baja. Esto se debe al desarrollador de su motor 3D, John Carmack. De hecho, en los primeros días de DOS en la década de 1990, cuando cualquier pequeña animación en una PC era asombrosa, John Carmack lanzó el sorprendente Castle Wolfstein, y luego continuó con doom, doomII, Quake... cada vez llevando la tecnología 3D al límite. Su código de motor 3D es extremadamente eficiente, aprovechando al máximo cada instrucción de cálculo de la PC. Incluso Microsoft tuvo que escuchar sus opiniones y realizar modificaciones en Direct3D.
Este número mágico aparece en el código subyacente de este motor 3D y se utiliza para calcular la raíz cuadrada y su recíproco. Según las pruebas, este código es 4 veces más rápido que (float)(1.0/sqrt(x)):
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
Sobre el método iterativo
El método iterativo calcula nuevos valores a partir de los valores antiguos, repitiendo el proceso en un bucle, lo cual es muy adecuado para los lenguajes de programación. El algoritmo iterativo más clásico es el algoritmo de Euclides (algoritmo de división sucesiva), que se utiliza para calcular el máximo común divisor de dos números enteros a y b. Su principio de cálculo se basa en el siguiente teorema:
mcd(a,b) = mcd(b,a mod b)
Además, el método iterativo también se utiliza para calcular secuencias famosas como la serie de Fibonacci. Por lo general, los algoritmos recursivos son más legibles, pero a menudo requieren más recursos. En estos casos, se puede convertir la recursión en iteración para lograr una mayor eficiencia. Esto es algo que he experimentado profundamente al resolver problemas de algoritmos.
Sobre el método de Newton-Raphson
Introducción: Método de Newton-Raphson - Wikipedia
Es sorprendente que una idea que surgió hace 300 años siga siendo relevante hoy en día. Las matemáticas realmente son el fundamento de la civilización. Por lo general, el algoritmo de la raíz cuadrada utiliza el método de Newton-Raphson, que se basa en la fórmula x - f(x)/f'(x) para acercarse continuamente a la raíz de f(x) = a.
En pocas palabras, para calcular la raíz cuadrada, se utiliza la función f(x) = x^2 = a, y su derivada f'(x) = 2*x. Sustituyendo f(x) en x - f(x)/f'(x), obtenemos (x + a/x)/2. Ahora, si elegimos a = 5 y suponemos un valor inicial, como 2, podemos hacer lo siguiente:
5/2 = 2.5; (2.5 + 2)/2 = 2.25;
5/2.25 = 2.22;(2.25+2.22)/2 = 2.235;
5/2.235 = 2.23713;(2.235+2.23713)/2 = 2.236065;
En tan solo tres pasos, obtenemos un valor muy cercano a sqrt(5) = 2.23606797. Podemos prever que al repetir este proceso de iteración, el resultado convergerá hacia sqrt(5). Por lo general, después de 4 a 7 iteraciones, se obtiene un valor relativamente preciso. Esto se basa en la suposición de que el valor inicial es relativamente impreciso. En teoría, si el valor inicial es lo suficientemente preciso, se puede reducir significativamente el número de iteraciones, y es aquí donde entra en juego el número 0x5f3759df.
Puedes consultar el blog mencionado anteriormente para obtener detalles sobre el proceso de derivación. Aquí, citaré la conclusión al final del artículo, que también despertó mi curiosidad sobre los motores de juegos.
Tan sorprendente, tan extraño, tan contrario a la lógica, tan acorde con la lógica, tan hermoso.
Hemos profundizado lo suficiente, al menos yo estoy satisfecho, no hay nada más que investigar. Para mí, a través de este ejercicio, he aprendido principalmente que las operaciones de conversión de bits entre enteros y flotantes no carecen de sentido, son operaciones numéricas extrañas pero económicas y muy útiles en cálculos. Creo que aún hay más usos por descubrir.
Este post está traducido usando ChatGPT, por favor feedback si hay alguna omisión.