Aproximar raíces cuadradas para lograr un mejor rendimiento + Cristalab

Ayuda del foro + Buscar + Grupos de Usuarios + Registrarse + Perfil + Entre para ver sus mensajes privados + Login

Aproximar raíces cuadradas para lograr un mejor rendimiento

Foros de discusión -> Tips, ¡Envía tus trucos aquí!

Mensaje

Autor

Publicado: Vie Jul 06, 2007 1:14 am

Citar

A veces, especialmente en los videojuegos, necesitamos calcular distancias (por lo que necesitamos raíces cuadradas). La distancia al objetivo, al suelo, la distancia de penetración (para corregirla), etc...

El problema es que a veces, sea por el motivo que sea, terminamos acumulando raíces, ralentizando el programa inútilmente.

Como solución es muy útil aproximar las raíces, en este caso, propongo una forma bastante simple (hay varias):

Código :

raizNewton = function (numero:Number, iteraciones:Number, valorInicial:Number):Number {
   for (var i = 0; i < iteraciones; i++) {
      valorInicial = (valorInicial + numero / valorInicial) / 2;
   }
   return valorInicial;
};

(El nombre se lo puse en honor a quien la propuso)

¿Cómo funciona? No es demasiado complicado, geométricamente equivale a crear un cuadrado de área igual al número al que le queremos calcular la raíz y "hacerlo más cuadrado". Es decir, aumentamos el lado más grande y agrandamos el más chico hasta que sean iguales. En ese momento sus lados van a ser iguales a la raíz cuadrada del número deseado (por algo se llama raíz cuadrada Guiño

)

Igualmente, un problema del algoritmo es que requiere que el valor inicial sea similar a la raíz.

Para ejemplificarlo, muestro distintos valores que va devolviendo la función:

Código :


trace (Math.sqrt(32)); //Output: 5.65685424949238
//
trace (raizNewton(32, 1, 3)); //Output: 6.83333333333333
trace (raizNewton(32, 2, 3)); //Output: 5.75813008130081
//
trace (raizNewton(32, 1, 4)); //Output: 6
trace (raizNewton(32, 2, 4)); //Output: 5.66666666666667
//
trace (raizNewton(32, 1, 5)); //Output: 5.7
trace (raizNewton(32, 2, 5)); //Output: 5.65701754385965
//
trace (raizNewton(32, 1, 6)); //Output: 5.66666666666667
trace (raizNewton(32, 2, 6)); //Output: 5.65686274509804
//
trace (raizNewton(32, 4, 6)); //Output: 5.65685424949238

Noten que con una buena aproximación inicial (6) y 2 iteraciones, se consiguen 4 decimales correctos (con 1 iteración conseguimos 2). Mucho más de lo necesario. Finalmente, con sólo 4 iteraciones conseguimos un valor tan bueno como el de la función Math.sqrt();

Ahora bien, la utilidad de esto es que podemos decidir cuánta precisión pretendemos, en prácticamente todos los casos, aproximar con 1 o 2 decimales es suficientemente bueno (es más, hasta excesivamente bueno), y si, además, empleamos el último valor de la raíz como aproximación inicial, fotograma a fotograma va a ser más preciso. Mi consejo es no usar más de 1 o 2 iteraciones si podemos prescindir de la precisión en uno que otro fotograma (aunque podemos calcular la raíz inicialmente para tener un buen valor inicial).

Ésto resulta especialmente útil, ya que usando 1 o 2 iteraciones puede llegar a ser de 2 a 3 veces más rápido emplear este algoritmo que la función nativa (depende mucho del tamaño del número)

Por último, aclaro que es bastante fácil hacer ésto a mano (hasta mentalmente, dependiendo del valor) y que es un buen modo de calcular una raíz cuadrada si no se tiene una calculadora cerca.

HernanRivas

clabLevel: 2528

1 Tutoriales
22 Tips

	Foros de discusión -> Tips, ¡Envía tus trucos aquí!	Todas las horas son GMT
Página 1 de 1