0x5F3759DF: el número mágico que hizo posible la 3D

En algún lugar del código fuente de Quake III Arena, el juego de disparos de 1999 que le enseñó a toda una generación lo que se sentía al jugar a 125 fotogramas por segundo, hay una función. Tiene una veintena de líneas, calcula un trozo de matemáticas perfectamente corriente y, justo en mitad, luce un comentario que se ha vuelto legendario: // what the f***?. Ni siquiera los programadores que la publicaron estaban del todo seguros de por qué funcionaba. La proeza que lograban — calcular uno entre la raíz cuadrada de un número, más rápido de lo que el hardware de la época podía hacerlo honestamente — es uno de los trucos más hermosos de la historia del código. Y en su núcleo hay un único número hexadecimal, casi mágico: 0x5F3759DF.

Por qué un juego se pasa el día dividiendo por una raíz cuadrada

La 3D, bajo las explosiones, es una cantidad enorme de geometría. Para saber cómo una superficie atrapa la luz, cómo refleja una pared, si un enemigo está delante o detrás de ti, el motor maneja sin parar vectores normalizados: flechitas de longitud exactamente uno, apuntando en una dirección. Convertir cualquier flecha en una flecha de longitud uno significa dividir cada una de sus componentes por su longitud, y una longitud es una raíz cuadrada. Así que el motor necesita 1 / √x, la raíz cuadrada inversa, millones de veces por segundo.

La forma honesta de calcular eso en una CPU de 1999 era brutalmente lenta. Las raíces cuadradas y las divisiones figuraban entre las operaciones más caras de un procesador — el tipo de cosa que, repetida millones de veces por fotograma, convertía tu trepidante shooter en un pase de diapositivas. La pregunta de los programadores no era, pues, cómo obtener la respuesta exacta, sino cuánto podemos acercarnos, rápido, y lo bastante bien para que nadie lo note.

El truco de bits que no debería funcionar

He aquí el juego de manos. Un número de coma flotante — la forma en que los ordenadores guardan los decimales — no es más que un patrón de bits: un signo, un exponente y una fracción. La idea genial es que esa disposición codifica en secreto un logaritmo. Los bits del exponente equivalen, a grandes rasgos, a la parte entera del log₂ de tu número, y los bits de la fracción aproximan el resto.

Y la raíz cuadrada inversa, en el mundo de los logaritmos, resulta casi trivial: hacer 1/√x equivale a multiplicar el logaritmo por −½. El algoritmo hace entonces algo que parece una locura total. Toma el número en coma flotante, reinterpreta sus bits en crudo como un entero corriente (sin conversión, solo «leer la misma memoria como si fuera otro tipo») y luego calcula, a grandes rasgos, mágico − (i >> 1). El desplazamiento a la derecha divide el valor entre dos; la resta a la constante mágica invierte el signo y aplica la corrección. Vuelve a leer esos bits enteros como un flotante y — asombro — tienes una estimación excelente de 1/√x. Una sola línea de manipulación de bits, de aspecto ilegal, ha sustituido una raíz cuadrada y una división.

Qué es realmente 0x5F3759DF

Ese número mágico no es aleatorio, y no es una errata. Es la constante que hace que todo el truco del logaritmo cuadre. Cuando divides entre dos e inviertes esos bits del exponente, introduces un pequeño error sistemático, y 0x5F3759DF está afinado para mantenerlo tan equilibrado — tan pequeño en el peor de los casos — como sea posible. Es, en sentido literal, el entero mejor elegido de todo este rincón de los gráficos por ordenador.

La estimación que produce es buena, pero no perfecta, así que el código termina con una pasada del método de Newton — una técnica de hace siglos para afinar una aproximación. Una sola iteración toma la respuesta tosca y la refina hasta cerca del 0,17 % del valor real. Más que suficiente para iluminar un rocket-jump en un deathmatch, y todo el conjunto corría aproximadamente cuatro veces más rápido que el cálculo directo. (Una segunda pasada de Newton apretaría aún más el error, pero ¿para qué pagar una precisión que nadie ve?)

El misterio del autor

Durante años, la leyenda atribuyó 0x5F3759DF a John Carmack, el célebre programador jefe de id Software. La historia era pulcra — codificador genial, truco genial — pero era falsa. Carmack publicó el código; no inventó el número.

Cuando id liberó el código fuente de Quake III en la QuakeCon de 2005, el enigma solo se hizo más espeso, y programadores curiosos se pusieron a escarbar. El rastro, reconstruido en buena parte por una investigación de 2006, conduce, a través del fabricante de chips Ardent Computer, hasta un programador llamado Greg Walsh, que ideó la famosa constante a finales de los años ochenta. Walsh había aprendido la idea de fondo del trucaje de bits del matemático Cleve Moler (el creador de MATLAB), quien a su vez la había visto en un artículo no publicado de 1986 firmado por William Kahan y K. C. Ng en Berkeley — siendo Kahan precisamente el hombre que coescribió la norma que rige cómo los ordenadores manejan los números en coma flotante. Aquel apaño que parecía un feliz accidente era en realidad la inteligencia destilada de algunas de las mentes más profundas del cálculo numérico de la época, pasada de mano en mano durante más de una década antes de hacer volar al fin un cohete.

El remate

La última pirueta es casi poética. Unos años después de hacerse público el código, varios matemáticos se sentaron a buscar el número mágico verdaderamente óptimo — y encontraron uno ligeramente mejor, 0x5F375A86. La constante legendaria, la grabada en el folclore de la programación, la del comentario atónito al lado, nunca llegó a ser del todo la mejor opción. Era simplemente lo bastante buena, lo bastante rápida y estaba entregada — que, al final, es exactamente la forma en que se hace un juego.