Foro de elhacker.net

¡Hola a todos!

Hemos preparado un reto para entre todos proponer implementaciones eficientes de la raíz cuadrada inversa. Todo parte de una implementación bastante ingeniosa de esta operación en el código de Quake III a finales de los años 90. ¡Cualquier aportación será bienvenida!

http://solucionesproblemas.com/content/m-curiosidades-universidad/c-curiosidades/c-curiosidades-universidad/raiz-cuadrada-inversa-rapida

Mmmmm,

Estuve revisando el link y cuenta la historia del asunto, es la verdad muy interesante.

Pero luego te muestra un código fuente que implementa el algoritmo de raíz cuadrada rápida, pero no entiendo que ¡¡Wtf!! es lo que hace ....  :huh:

Hola yoel_alejandro,

Muchas gracias por tomarte el tiempo de leerlo. Ciertamente el comentario " // what the fuck?" en el código que incluyó alguno de los compañeros del programador original, indica que se trata de la implementación de un razonamiento complejo y difícil de entender si no se explica.

Por suerte, más allá de unos cuantos detalles, hay una idea central en este cálculo que explica su eficiencia, y es la siguiente relación log(x^a) = a log(x), siendo log un logaritmo en cualquier base. En este caso, como intentamos calcular la raíz cuadrada inversa de un número (x^(-1/2)), el valor de a utilizado es -1/2.

Además, por la especificación de los números en coma flotante, considerar un float como long (sin hacer cast) es una aproximación del logaritmo en base 2 de ese float, y viceversa. Con lo cual, para pasar de un número a su logaritmo y del logaritmo al número original, basta simplemente con pasar de considerar un tipo de variable como otro tipo diferente (float y long en este caso).

En resumen, el código (repito que pasando por alto los detalles) lo que hace con el número x es:

• Calcular el logaritmo en base 2 del número considerando el float original como long, obteniendo log(x).
• Calcular el logaritmo en base 2 de la raíz cuadrada inversa de ese mismo número, lo que supone gracias a las propiedades de los logaritmos, multiplicar el logaritmo por -1/2, obteniendo log(x^(-1/2)).
• Deshacernos del logaritmo mediante la operación inversa a la primera, es decir, considerando el float como long, obteniendo x^(-1/2).

Espero que este resumen ayude a entender mejor la implementación de la raíz cuadrada inversa rápida.

¡Un saludo!

¡¡ Interesante !! Eso sí que no lo sabía. Que considerar el float como long produce el logaritmo natural, y lo puesto supongo que produce el exp. Y lo demás ya es sencillo, como sabemos

x^(-1/2) = exp( -1/2 * log(x) )


Tengo que pensar en alguna palicación que se me ocurra utlizando este algoritmo.

Yo particularmente lo que conocía es la fórmula iterativa "de Newton", para calcular la raíz cuadrada de un número "a":

x_(n+1) = (1/2) * ( x_n  + a/x_n )

donde, en la medida que "n" se hace más grande, el valor x_n tiende a sqrt(a).

Hola de nuevo yoel_alejandro,

Bueno en realidad considerar un float como long no equivale al logaritmo natural, fui demasiado directo en mi explicación y me salté algunos detalles importantes, aunque más allá de los detalles lo que dices es cierto.

De hecho, todos los logaritmos que aparecen en mi explicación anterior son logaritmos en base 2. Aprovecho para explicar un poco más en detalle esta extraña relación entre formatos de datos y logaritmos.

La representación de los bits de un número float es la siguiente:

s e7 e6 e5 e4 e3 e2 e1 e0 m22 m21 m20 m19 m18 m17 m16 m15 m14 m13 m12 m11 m10 m9 m8 m7 m6 m5 m4 m2 m2 m1 m0

s es el bit de signo
e son 8 bits del exponente
m son los 23 bits de la mantisa

Y el número representado por dichos bits es: (1+m)*2^e si s = 0 ó -(1+m)*2^e si s=1

Por lo tanto, si este número lo pasamos a considerar como int y dividimos el resultado por 2^23, nos quedará s e7 e6 e5 e4 e3 e2 e1 e0, que es el exponente de la potencia de 2 anterior, y por lo tanto una aproximación del logaritmo en base 2 del número anterior. Para mejorar el cálculo del logaritmo en base 2 del número anterior, bastaría con añadir a este resultado el logaritmo en base 2 de (1+m).

En el algoritmo de la raíz cuadrada rápida no se implementan todos estos pasos, ya que no todos son necesarios al tener que calcular tanto el logaritmo como su inverso.

Espero que estas aclaraciones sigan siendo útiles.

Un saludo.

Acabamos de añadir un nuevo método rápido para calcular la raíz cuadrada inversa. Se trata de la alternativa más rápida que hemos probado hasta ahora pero no la más precisa.

http://solucionesproblemas.com/content/es/m-curiosidades-universidad/c-curiosidades/c-curiosidades-universidad/raiz-cuadrada-inversa-rapida

¡Seguimos esperando vuestra ayuda!