Cuando el código fuente de Quake III Arena se dio a conocer al mundo, contenía un algoritmo desconocido hasta entonces llamado Raíz Cuadrada Inversa Rápida. Esta es la historia de este extraño algoritmo y su funcionamiento, contada por el ingeniero de software retirado de Microsoft Dave Plummer. ¿Para qué sirve? ¿Quién lo inventó? ¿Por qué es tan rápido? ¿De dónde ha salido ese número mágico 0x5F3759DF? ¿cómo puede funcionar esa "conversión" entre entero y coma flotante hecha a lo bestia con un puntero? ¿Por qué fue tan importante?
|
etiquetas: quake , algoritmo , raíz cuadrada , dave plummer 
![El algoritmo FISR (raíz cuadrada inversa rápida) de Quake - la fantástica historia de este algoritmo [ENG]](https://peta.meneame.net/backend/media?type=link&id=3542940&version=0&ts=1629045127&image.jpeg)
Ahora miro de qué va
en.wikipedia.org/wiki/Bhaskara_I's_sine_approximation_formula
Tendrás que ver el video para saber lo que se sabe
Aunque luego menciona que no es el primero que se pregunta por los orígenes y que más allá de Mike Abrash y Carmack se había usado antes en la estación de trabajo SGI Indigo (que apareció en 1991).
Si miras Wikipedia, dice que la implementación en SGI Indigo fue la primera implementación que se conoce y que fue realizada por Gary Tarolli.
en.wikipedia.org/wiki/Fast_inverse_square_root
Sin embargo, la "constante mágica" sería anterior y se encontró que surgió de una colaboración entre Cleve Moler y Gregory Walsh, cuando Gregory estaba trabajando para Ardent Computing a principios de los 80.
Por cierto, esa página de Wikipedia me pareció que explica de forma un poco más clara cómo funciona, hablando del logaritmo en base 2, y mostrando un ejemplo numérico,
aunque reconozco que el vídeo es más ameno porque lo noveliza como una historia con muchas anécdotas y, además, incluye imágenes tanto de los protagonistas como de los fundamentos matemáticos.
Y, de hecho, en el código de Quake la función se llama Q_rsqrt , que si no me equivoco se refiere a "Quick reciprocal of square root" ... (la Q también podría referirse al Quake).
Sin embargo, pese a que "reciprocal" es una palabra más clara, menos ambigua, el algoritmo se conoce como FISR (Fast Inverse Square Root), quizá porque la "i" es vocal haciendo que sea más pronunciable: un acrónimo, que son siglas que en lugar de leerse letra por letra se lee como una palabra (ejs: RADAR, ONU, LASER, etc). En este caso quizá se lea como "fiser" en lugar de decir "efe, i, ese, erre".
Mientras que el mundo de las matemáticas creo que se tiende a minimizar la ambigüedad, en el mundo coloquial de la vida diaria, o incluso ingenieril, se va a lo práctico... lo que se pronuncia rápido, en especial en lugares como Estados Unidos, que son más "cool", más "guays", menos "estirados" / pedantes que los británicos, y en el mundo de la tecnología punta donde usar algo nuevo, aunque sea una palabra nueva, puede dar sensación de estar más a la última y estar en la onda de los últimos avances / inventos / trucos.
La verdad es que si, hay cosas apasionantes por ahi fuera
Aunque es cierto que meter una operación de división puede complicar las cosas, especialmente tiempo atrás cuando los ordenadores (microprocesadores / coprocesadores) no "sabían" dividir... sin embargo, si la máquina tiene operación de división lo que consigues con la fórmula del hindú es más precisión con un mismo número de operaciones o menos.
Otro detalle es que la Serie de Taylor, aunque es exacta dentro del radio de convergencia, es infinita y como no puedes hacer infinitas operaciones lo que haces es truncar, es decir, limitar el grado el polinomio... perdiendo exactitud con un margen de error.
Y otro detalle más es que las series de Taylor suelen tener más error cuanto más te alejas del punto central "c". Recordemos que son potencias de (x - c) así que en el caso x=c tienes garantizado el valor exacto y para valores de x muy cercanos a c la diferencia (x-c) será casi 0 y tendrás valores cercanos a ese punto central pero cuando te alejas, cuanto mayor es la diferencia (x-c) el error suele crecer mucho.
En el caso concreto de la serie de Taylor del seno, las derivadas enésimas están acotadas (son cosenos y senos, que están entre -1 y 1, no pueden crecer mucho) mientras que se divide por un factorial, así que con polinomios de grado bajo (ej: 3 ó 5) te acercas bastante... Aún así, en puntos alejados tendrás más error. Si te fijas en la fórmula del hindú tiene raíces (ceros) donde se anula el seno (0 y PI si es en radianes ó 0 y 180 si es en grados), es decir, no tienes nada de error en los extremos a pesar de tener el mayor alejamiento. Vas a tener error en puntos intermedios, claro, porque no es exacta, pero podríamos decir que el error está equilibrado, hay varios puntos sin nada de error. Esto es diferente en la serie de Taylor porque si es exacta en un punto, en otro punto alejado (los extremos serían el máximo alejamiento) normalmente tienes un error grande.
Aunque es cierto que una operación en aritmética de coma flotante tarde más que una operación con enteros, me parece que la clave no es esa y que en el vídeo no se explica muy bien del todo.
El caso es que la operación a calcular es 1/√x , como dijo #7
Y esa operación se puede escribir como la potencia x^(-1/2)
Y resulta que los números en coma flotante tienen relación con las potencias... en este caso en base 2, aunque también hay variantes en base 10.
Los flotantes son de esta forma: (-1)^s * c * b^q
donde s es el signo, c es el "coeficiente" o "significante" (o "mantisa"), b es la base y q el exponente.
Ejemplo en base 10: -2.5 * 10^14 sería signo = 1; c = 25; b=10 (base 10); q = 13
Ejemplo en base 2 (binario): +0.25 sería +(1/4) = +(2^-2) --> s=0; c = 1; b=2; q = -2
En la Wikipedia lo explica:
en.wikipedia.org/wiki/Fast_inverse_square_root#Algorithm
1. Alias the argument x to an integer as a way to compute an approximation of log2(x)
Si el número x es un float ... y especialmente si es positivo la representación binaria de ese
número codifica primero el exponente.
De esa forma, el "convertirlo" o "tomarlo" como un entero es una aproximación al logaritmo en base 2.
En el ejemplo : 0.25 = 2^(-2) y lo que codifica primero el formato de coma flotante es ese "-2", el exponente.
2. Use this approximation to compute an approximation of log2(1⁄√x)= −1/2 log2(x)
Lo que hacemos con ese exponente es dividirlo entre 2 y luego restarlo...
(por ejemplo, dividir entre 2 un entero es un desplazamiento de un bit a la derecha: >> 1)
Tanto esa "división" como la resta son operaciones con enteros, sí.
Pero la verdadera gracia es que eso es el logaritmo del recíproco de la raíz cuadrada.
¡¡¡Justo lo que buscamos calcular!!!
Ejemplo:
si teníamos x=0.25 y el exponente era -2 al dividir entre 2 queda -1 y al restar...
ej: 0-(-1) queda exponente +1
La raíz cuadrada de 0.25 es 0.5 y el recíproco de 0.5 es 2.
Efectivamente, el exponente es +1 porque 2^(+1) = 2
Otro ejemplo. Si fuese x=1024 = 2^10 el exponente es 10. Dividido entre 2 es 5. --> -5
La raíz cuadrada de 1024 es 32 y 1⁄√x = 1/32 = 2^(-5) así que el exponente calculado es correcto.
El significante (mantisa, coeficiente) no importa tanto, sobre todo cuando el formato en coma flotante
es formato normalizado... es decir, números que no son muy pequeños.
En el… » ver todo el comentario
Por ejemplo, en una aplicación de contabilidad o de diseño / maniobra de un cohete prefieres precisión... En ambas está en juego una cantidad de dinero y puedes sacrificar minutos u horas para evitar perder ese dinero.
Obviamente, en el caso del que habla este meneo se trata de ocio, un videojuego... en el que tardar más tiempo en los cálculos arruina la experiencia de juego o al menos implica que el juego no funcionará bien en ciertos ordenadores, reduciendo el mercado potencial de ese juego. En este caso, que haya pequeños fallos de precisión es algo mucho más asumible que dividir la velocidad del juego por 4 o por 10.
Además, en un contexto de diversión / ocio / arte los errores inesperados dan un factor sorpresa o de ser diferente / especial / único que muchas veces lejos de considerarse un defecto puede llegar a ser un aspecto positivo.
Como el chiste:
- ¡Jaimito! Responda rápido… ¿cuánto es 2 multiplicado por 2?
- ¡CINCO!
- ¿¡Cómo que cinco Jaimito!? ¡SON CUATRO!
- Señorita, usted pidió velocidad, no precisión.
#2 Casualmente en el código fuente publicado aparece el WTF en un comentario del código.
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
Cuenta más o menos lo que escribí en #46 aunque con algún detalle sobre programación como los punteros y conversión de tipos en C ... y más detalle sobre lo que representa la constante mágica, así como detalles del método de Newton para este caso particular (no en general como el vídeo del meneo).
cc #42