martes, 25 de enero de 2011

Buscar la raiz cuadrada mas rapida, con Ruby

Se vienen los examenes y uno de ellos es el de Analisis Numerico, y como estoy usando mucho la raiz cuadrada en un proyecto en el que estoy, me decidi a buscar una raiz cuadrada mas rapida que la que trae el propio framework ;)

La verdad, es que por default, las librerias matematicas calculan la raiz cuadrada con una muy buena precision, pero pueden surgir casos en los que esa precision es innecesaria (por ejemplo, si se trunca el resultado de la raiz cuadrada, es decir, tirar a la basura los decimales que se calculo) y lo que si es importante es poder efectuar los calculos rapido

Sea cual sea el lenguaje en e que se va a programar, ruby esta bueno para probar los algoritmos muy facilmente, en este caso se utiliza el metodo de Newton-Raphson para calcular la raiz cuadrada de un numero


# x**2 - a = 0

# calcula la raiz cuadrada y se le puede especificar la precision, es decir
# la cota superior del error del resultado
def Math.my_sqrt(a, precision)

x = 1
oldx=1

iter = 0
# newton raphson
while 1
oldx = x
x = x - ( x**2 - a ) / ( 2 * x)
break if (oldx-x).abs < precision
end

x
end

def show( code )
print "#{code} => #{eval(code)}\n"
end

show "Math.my_sqrt(2.0, 0.5)"
show "Math.my_sqrt(2.0, 0.05)"
show "Math.my_sqrt(2.0, 0.005)"
show "Math.my_sqrt(2.0, 0.0005)"

show "Math.sqrt(2.0)"



Salida del programa


Math.my_sqrt(2.0, 0.5) => 1.41666666666667
Math.my_sqrt(2.0, 0.05) => 1.41421568627451
Math.my_sqrt(2.0, 0.005) => 1.41421568627451
Math.my_sqrt(2.0, 0.0005) => 1.41421356237469
Math.sqrt(2.0) => 1.4142135623731


Enlaces:

Metodo de Newton explicado en la Wikipedia
Explicacion del metodo de newton usado para calcular la raiz cuadrada de un numero