1/sqrt(x)


Editado por Pirilón: Bueno, cómo veo que ya habeis leido la entradita, os daré alguna pista de lo que es esto.

Como bién supone Roberto, esta es una función que te devuelve uno partido por la raiz cuadrada del parámetro, sin usar nada más que sumas, restas, multiplicaciones y el operador ">>" (mover un bit a la derecha).

Por otro lado, César está equivocado pensando que esto es código mío. Gracias, pero esto no se me hubiese ocurrido a mí en la vida.

Y ahora el porqué. He puesto esto aquí por que es una joya de la programación universal. Esta función forma parte del código de Quake III (no, no la ha escrito John Carmack) y su importancia es que sirve para normalizar vectores.

Para sacar el módulo al cuadrado de un vector sólo se necesitan multiplicaciones y sumas (x*x + y*y + z*z). Pero luego tienes que dividir los componentes del vector por la raíz cuadrada del módulo. Esto es muy caro, por que tienes que utilizar la parte de punto flotante del procesador para sacar la raiz cuadrada y para dividir.

Para evitar ese problema escribieron esta función, que es extremadamente ingeniosa. Lo voy a dejar así un par de días más, y luego os digo cómo funciona. Total, son sólo cinco líneas de código, eso no os puede llevar más de un par de días de estrujaros el cráneo para saber lo que hace :-)

Editado por Rober: hacedme el favor de traducir las sentencias. Mamo abé:

float xhalf = 0.5f*x; digo yo que la "f" es para significar que es un float. Vale: xhalf la mitad de x (como era de esperar).
int i = *(int*)&x; esto está más claro: el entero i es igual por (*) entero por (int*) and (&) x. Osea, "el entero i es igual por entero por and x" (léase en voz alta). Está muy claro. Lo voy a dejar en que i es la parte entera de x y a ver qué pasa. Más Javi: Ya sabeis que en C el operador "*" no es multiplicación, sino "puntero a", y el operador "&" significa "dirección de", osea, son complementarios.

i = 0x5f3759df - (i >> 1); vaya por Dios, ahora que ya sabíamos lo que vale i, resulta que lo cambiamos. Bueno, yo he supuesto que 0x quiere decir "cero coma..." y lo demás es un número en hexadecimal y la f final es que es flotante o es parte del decimal pero me da lo mismo más o menos. Me sale 0,3719.... Mover un bit a la derecha es dividir por dos truncando. Así que tendríamos 0,3719 menos la mitad truncada de la parte entera de x, todo eso en un entero otra vez. Vale. Si x es mayor que 2, aquí sale un negativo como la copa de un pino y nos acercamos al concepto del complementario que puse en los comentarios, pero me pierdo un poco.
x = *(float*)&i; según lo visto antes esto parece decir que x es lo que valía i, pero flotabilizado otra vez ¿?
x = x*(1.5f-xhalf*x*x); chupao, x es x por 1.5 y todo eso. Bueno, resumiendo: que vuelco en x un montón de cosas así que no me cuadra nada.

¡¡Ah!! lo del "&" va a ser un puntero, hombre, que intuyo yo que algo feo pasa al hacer esas conversiones directamente al valor en memoria o algo peor, pero sin saber realmente lo que significan las sentecias estoy perdidito. A ver si tenemos más consideración con la genta mayor ¡¡ traducción al cristiano ya !!

Editado por Oztralian:
De mi afirmación me reitero, evidentemente no di por supuesto que Pirilón fuera el autor de dicha maravilla, pero no es la primera vez que alguien se tiene que buscar la vida porque una herramienta de desarrollo devuelve un valor irreal, y yo he sido testigo de ello.
Pero volviendo al tema que nos ocupa, al que le guste el porqué de dicha fórmula, y sobre todo el origen de la esa constante mágica 0x5f3759df, puede apreciarlo aquí en toda su inmensidad, y su disparidad, ya que el propio autor propone otra constante mágica 0x5f375a86.
Es pues ésta, como bien dice Pirilón una de las últimas obras maestras de la reducción de cálculo, pero para ser puristas, sólo se trata de una buena aproximación

Lo increíble es que siempre es mejor algo creíble, que la propia realidad

Jooooo, le has quitado todo el encanto !

Comentarios

rober ha dicho que…
Voy a necesitar traducción simultánea para esto. Intuyo que se trata de una forma de calcular la raíz cuadrada (inversa) sin usar exponenciales pero no soy capaz de traducir alguna de las líneas. Un pseudo-código, porfa, plis.
oztralian ha dicho que…
Entre el catarro que tengo, el sueño acumulado, y mis rumrumnes ...

veo esto y flipo en colores, aunque supongo, más que Rober, que el pobre Pirilón ha tenido que usar esta solución, gracias al amable servicio de alguna herramienta de desarrollo de M$ que no daría la talla (como es habitual) ...

... Y es que no hay nada, como no tener nada para agudizar el ingenio
rober ha dicho que…
Ya me lo suponía yo. Pues en mis tiempo yo también hice lo mío para calcular una aprox. del coseno(x) en el spectrum: aproximando el coseno desde 0 hasta pi/2 con una parábola, queda:

cos(x)~( (pi/2)^2-x^2 ) / (pi/2)

tomando el ángulo de 0 a 256 queda:

cos(x)~( 65536-x^2 ) / 65536

restar 65536 - algo es fácil porque es hacer el complementario de un double-byte (que eran los registros del chip) y dividir por 65536 igual de fácil porque es poner la cifra como 0,... No recuerdo las instrucciones exactas, pero se ahorraba un montón. Eso sí, los círculos salían pelín ahuevados.
Pirilón ha dicho que…
Bueno, qué, álguien se atreve a decir lo que está pasando ahí?

Entradas populares