Mientras jugamos a algún videojuego, posiblemente no notemos todos los detalles realizados, salvo que alguno no encaje y esté mal hecho. Una reflexión de la luz bien hecha nos será algo natural, pero un detalle que refleje en un sentido irreal será rápidamente advertido.
Los desarrolladores del Quake III se encontraron con un problema al tratar de hacer uno de estos detalles: el de la iluminación y la reflexión de la misma. Al ser un juego en tres dimensiones, debían calcular la norma (longitud) del vector que incidía. Así como en dos dimensiones se calcula con el Teorema de Pitágoras, en tres dimensiones es igual pero con tres vectores:
La suma de los cuadrados de los tres vectores (uno que correspondía a cada eje) no era un problema de calcular. La lentitud venía cuando había que calcular la raíz cuadrada, ya que eran apróximadamente millones que calcular en apenas un segundo -menos tiempo, de hecho-. Una tarea lenta para los mediados de los 90′, cuando fue desarrollado.
La creación de una función para calcular la inversa de la raíz cuadrada de forma rápida fue, por un lado, vital para la creación del juego. Por otro lado, fue totalmente novedosa por el modo en el que se hacía el cálculo.
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
return x*(1.5f - xhalf*x*x);
}Esa es la función que se creó en 1990 para el Quake III que luego se dio a conocer en OpenArena (la versión opensource) y que resulta hasta 4 veces más rápida que 1/sqrt(x).
La función trabaja con la forma en la que se almacenan los números en las memorias de las computadoras, por lo que entenderla de manera rápida es imposible sin los conocimientos previos (así como explicarla). (Para los interesados, pueden leer el paper de Chris Lomont en donde explica matemáticamente lo que hace la función.)
Pero básicamente lo que hace la función es tomar el número deseado en notación científica, y pasar a negativo y dividir por la mitad al exponente (luego con el método de aproximación de Newton se consigue algo más cercano al valor real, pero no es lo que nos interesa).
Para conseguir eso, que el exponente se vuelva negativo y luego partirlo por la mitad, se necesitaba una multplicación (por -1) y luego una división (por 2). Lo cual era un trabajo pesado para la computadora en aquellos tiempos -debido a la cantidad de esas cuentas que se tenían que hacer-, por lo se necesitaba una forma más liviana. Y esto es lo que hace esta función, hace todo simplemente con sumas y restas.
Para pasarlo a negativo, usa un viejo truco: restarle a cero el número que queremos pasar a negativo. El problema era la pesada división por 2…
Y ahí es donde entra nuestro número mágico, 0x5f3759df. Una forma de dividir al exponente por dos es haciéndole un shift (aquí es donde habría que entender la forma en la se almacenan los números), que corre un lugar a todos los bits en la memoria de ese número. Esto provoca que el exponente se divida por dos… pero también el número de la base.
Por ejemplo, si tuviésemos 5.4^10, al shiftearlo, tendríamos 2.7^5, cuando en realidad quisiéramos 5.4^5.
0x5f3759df entra en juego y restando al número anterior corrige esa falla, dejando que solo la división afecte al exponente.
Con el tiempo, nuevos números mágicos fueron encontrados que actuaban mejor que 0x5f3759df, pero sin dudas el honor de haber sido el primero se lo lleva este último.
No importa si la explicación fue entendida o no. Lo importante es que programadores encontraron otras formas de hacer cálculos matemáticos, de hecho encontraron una forma para calcular la inversa de la raíz cuadrada con sumas y restas. Y eso es lo bello/importante/sorprendente de la matemática… día a día se siguen encontrando diferentes caminos para llegar a lo mismo, caminos que verifican que es una ciencia casi-perfecta… o perfecta.
