Los desarrolladores de juegos no lo tuvieron fácil en los años 90. Debido a que tenían una potencia informática extremadamente limitada, tuvieron que escribir su código de la manera más eficiente posible. Consideremos, por ejemplo, el shooter en primera persona Quake III Arena, habitualmente llamado Quake 3: los jugadores navegaban por un mundo tridimensional, por lo que los programadores tenían que encontrar las formas más inteligentes de manejar los gráficos 3D y los cálculos asociados.
Quake 3 se lanzó en 1999 y está considerado uno de los mejores juegos de ordenador de su época. Tuvo un impacto duradero en la industria. Este legado no se debió tanto a la historia, sino a que Quake 3 fue uno de los primeros shooters multijugador en primera persona. Los jugadores pueden conectar sus computadoras mediante cables de red o Internet para competir en tiempo real.
El código del juego también dejó huella. Incluía un algoritmo extremadamente eficiente que todavía sorprende a los expertos y despierta la curiosidad de los científicos.
Sobre el apoyo al periodismo científico
Si está disfrutando este artículo, considere apoyar nuestro periodismo galardonado al suscribiéndose. Al comprar una suscripción, ayudas a garantizar el futuro de historias impactantes sobre los descubrimientos y las ideas que dan forma a nuestro mundo actual.
un código extraño
Para determinar matemáticamente las orientaciones de objetos, personajes u otros jugadores en el espacio tridimensional, se crea un vector, que es esencialmente una flecha que muestra la dirección. Para comparar vectores, es necesario normalizarlos a la misma longitud, por lo que hay que escalarlos en consecuencia. Y ahí es donde surge un cálculo complicado: la raíz cuadrada inversa, que es uno dividido por la raíz cuadrada de un número.
Si te pidiera que calcularas la raíz cuadrada inversa de 26 sin una calculadora, probablemente te quedarías atascado por un tiempo y, sinceramente, yo también. En la década de 1990, las computadoras enfrentaban el mismo desafío. Aunque pudieron hacer cálculos, el proceso exigió mucha potencia de procesamiento, lo que puede significar que el cálculo lleva mucho tiempo. Un problema era la propia raíz cuadrada; otra fue la división. Es por eso que los programadores de Quake 3 buscaron una mejor manera de encontrar esta raíz cuadrada inversa. Y de hecho, sus código fuente reveló una solución ingeniosa.
Lo fascinante es que los desarrolladores nunca anunciaron su truco. Si el código fuente de Quake 3 no se hubiera vuelto abierto, su método podría haber permanecido oculto para siempre. Pero una vez que fue lanzado, los entusiastas curiosos se dieron cuenta. Cuando descubrieron el fragmento de código para calcular la raíz cuadrada inversa, quedaron desconcertados: era difícil de seguir y los comentarios adjuntos de los desarrolladores no fueron particularmente útiles. Pero poco a poco la gente descubrió cómo funcionaba el código.
hoy hay muchos tutoriales que le guiarán paso a paso a través del código del programa. Estos tutoriales aprovechan características especiales del lenguaje de programación C. Por ejemplo, los números se almacenan en ubicaciones de la computadora llamadas direcciones de memoria, que luego se manipulan. Esta es una forma inteligente de evitar operaciones computacionales intensivas como la división. “Piense en ello como si le pusieran la etiqueta equivocada a algo en la tienda y así convencer al empleado, pero aquí está C, nos engañamos”. explicó el informático Daniel Harrington de la Universidad de Toronto. en una presentación.
Desde una perspectiva matemática, el código se explica fácilmente. Para determinar la raíz cuadrada inversa, primero se hace una suposición de la solución (que generalmente es incorrecta) y luego se refina esa estimación mediante un procedimiento establecido. De esta forma, poco a poco se van alcanzando mejores soluciones.
Nada de esto es innovador o nuevo. Lo impresionante, sin embargo, es que normalmente se necesitan de cuatro a cinco iteraciones del proceso antes de que el resultado se acerque lo suficiente a una solución real. Este proceso requiere mucha potencia informática. En Quake 3, el valor inicial (es decir, el número estimado utilizado en el primer paso del proceso) se eligió de manera tan inteligente que solo es necesario un paso de optimización.
Buscando un número mágico
Los pasos de optimización corresponden al llamado método de Newton-Raphsonque aproxima los valores en los que una función produce una salida de 0, o la raíz de funciones, a lo largo de muchas iteraciones. Esto puede parecer contradictorio al principio, ya que lo que se desea es calcular la raíz cuadrada inversa y no un cero cualquiera. Pero los programadores emplean un truco: definen la función a aproximar como la diferencia entre el valor estimado inicial y el resultado real. Gracias al método de Newton-Raphson, el error se vuelve progresivamente menor, lo que permite acercarse cada vez más a la solución exacta.
Para pensar en esto, imagina que quieres calcular la raíz cuadrada inversa de 2,5. El algoritmo comienza con una suposición determinada: digamos 3.1. Para determinar la diferencia con la solución real, eleva al cuadrado el valor inicial y divide uno por el resultado. Si 3,1 fuera realmente la raíz cuadrada inversa de 2,5, entonces 1 dividido por 3,1 al cuadrado sería 2,5. El resultado real es 0,1. La diferencia es por tanto de 2,4.
El método Newton-Raphson reduce esta diferencia en cada iteración para que gradualmente te acerques al valor exacto. Normalmente se necesitan de cuatro a cinco pasos de este tipo para llegar a un resultado fiable. Sin embargo, Quake 3 redujo significativamente las iteraciones.
La clave está en cómo se calcula el valor inicial de los pasos de Newton. El algoritmo del método opera esencialmente en tres pasos:
Tome el número dado cuya raíz cuadrada inversa se va a calcular y conviértalo en la dirección de memoria correspondiente (una ubicación en los datos almacenados en la computadora).
Este valor se reduce a la mitad y se resta del valor hexadecimal 0x5f3759df. Este es el valor inicial del método de Newton.
A continuación, realice un paso de Newton.
Particularmente misteriosa es la cadena críptica 0x5f3759df, que desde entonces ha pasado a la historia de la informática como el «número mágico». Es la razón por la que sólo es necesaria una iteración para obtener una solución aproximada para la raíz cuadrada inversa que produce un error de como máximo 0,175 por ciento.
Tan pronto como el código del programa estuvo disponible como fuente abierta, los expertos se preguntaron sobre el origen de ese número mágico. En un artículo técnico publicado en 2003, el informático Chris Lomont escribió: «¿De dónde viene este valor y por qué funciona el código?»
El número hexadecimal 0x5f3759df corresponde a 1.597.463.007 en notación decimal. Al desglosar los pasos individuales del código del programa, Lomont se dio cuenta de que podía obtener 1.597.463.007 mediante ciertos cálculos. Para simplificar estos cálculos, aquí hay una forma de representar el cálculo involucrado:
los valores 3⁄2223 y 127 provienen de convertir las representaciones numéricas a C. Pero el origen de 0,0450465 es menos obvio.
Lomont investigó matemáticamente qué valor produce un resultado óptimo para diferentes entradas. En otras palabras: ¿qué valor inicial se aproxima mejor a la raíz cuadrada inversa y, por tanto, debería conducir al menor error? Llegó a un valor de 1.597.465.647 que es aproximadamente:
Esto corresponde a los valores encontrados en el código fuente de Quake 3. El resultado es bastante cercano a los valores encontrados allí.
Cuando Lomont comparó sus resultados con los del original, se encontró con una sorpresa. En dos pasos del método Newton-Raphson, su constante calculada funcionó mejor: el error máximo posible fue menor que con el valor en el código original. «Sin embargo, sorprendentemente, después de una iteración de Newton, tiene un error relativo máximo más alto», escribe Lomont. «Lo que nuevamente plantea la pregunta: ¿cómo se derivó la constante del código original?»
En su cálculo, el informático sólo había considerado qué número daría teóricamente el mejor valor posible, despreciando el número de pasos de Newton. En busca de una constante mejor, Lomont repitió su cálculo y optimizó para obtener la mejor solución posible para un solo paso de Newton. Llegó a un valor de 1.597.463.174 que es aproximadamente:
Cuando puso este resultado a prueba práctica, en realidad arrojó resultados ligeramente mejores que el número mágico en el código de Quake 3.
Lomont señaló en su artículo que, dado que ambas constantes son aproximaciones, cualquiera de ellas es una buena opción en la práctica. Añadió que esperaba conocer al autor original de la constante para saber cómo derivaron el número mágico.
Las comunidades en línea comenzaron una búsqueda incesante de esta persona misteriosa. Particularmente dedicado a este esfuerzo fue El informático Rys Sommefeldt.quien contactó por primera vez a John Carmack, el desarrollador principal de Quake 3. Carmack no estaba seguro de quién codificó este fragmento y, sin embargo, solo podía ofrecer conjeturas.
Sommefeldt se puso en contacto con algunos de los desarrolladores más destacados de la década de 1990, quienes sugirieron otros posibles autores sin reclamar la autoría para ellos mismos. Ahora parece que Greg Walsh, que trabajó para el fabricante de ordenadores Ardent Computer a finales de los años 1980, introdujo el número mágico en el algoritmo de la raíz cuadrada inversa. Luego llegó al algoritmo de Quake 3 a través de varios otros individuos. Pero hasta el día de hoy no está claro exactamente cómo se determinó el número mágico.
Esa no es una conclusión particularmente satisfactoria. Sin embargo, la historia del código de Quake 3 (o al menos la parte que gira en torno a la raíz cuadrada inversa) es extremadamente fascinante. Es sorprendente cuánto esfuerzo y capacidad intelectual se destinaba a la programación de software eficiente en aquel entonces, una tendencia que a menudo se pasa por alto hoy en día gracias a la potencia informática actual.
Este artículo apareció originalmente en Spektrum der Wissenschaft y fue reproducido con autorización.
