Mostrando entradas con la etiqueta numerico. Mostrar todas las entradas
Mostrando entradas con la etiqueta numerico. Mostrar todas las entradas

domingo, 1 de abril de 2012

Menos precision por favor

Estoy cursando numerico en fiuba y se dio la necesidad de probar varios algoritmos en distintos grados de precision (el ejemplo mas claro de esto, es el tipo de datos double y float de C)
, como todo rubyfan decidi hacerlo en ruby, pero ruby solo tiene un tipo de dato de punto flotante, llamado Float, que wrappea el double nativo de C

El truco, como en otros lenguajes con solo una precision de punto flotante, es emularlo; es decir, truncarlo a la precision deseada despues de cada operacion. Ruby tiene soluciones interesantes para hacer este tipo de cosas.

El decorator


En un principio, usamos un patron llamado decorator, con la idea de modificar el comportamiento del float:

Nuestro FloatDecorator repite cada operacion en el objeto "decorado", pero al retornar el resultado lo trunca y lo decora tambien asi mantiene el comportamiento

Asi, la raiz cuadrada de dos 2**0.5 da 1.41 y no 1.4142135623730951






La manera mas rubyway de implementar un decorator es usando method_missing En este caso se implementaria asi:
class FloatPrecisionDecorator
  def initialize(inner, factor)
    @factor = factor
    @inner = inner.to_f
  end

  def method_missing(m,*x)
    # todas las operaciones sobre el numero se ejecutan sobre el float verdadero
    # y se obtiene el verdadero resultado con precision completa del Float original
    verdadero_resultado = @inner.send(m,*x)
    # se reduce la precision, multiplicando por el factor, redondeando y volviendo a dividir
    reduced = (verdadero_resultado.to_f * @factor).round.to_f / @factor
    FloatPrecisionDecorator.new(reduced, @factor)
  end
end

# esto da un FloatPrecisionDecorator con un 1.41, adentro, no un 1.4142135623730951
p FloatPrecisionDecorator.new(2,100)**0.5

Inspect


Pero cuando se hace el print por salida estandar, aparece algo asi:

#..floatprecisiondecorator:0x8cd63f8 factor="10," inner="1.4"...

¿ No seria mejor que simplemente mostrara el 1.41 ? Para eso hay que sobrecargar el metodo inspect

class FloatPrecisionDecorator
  def inspect
    # para que llame al inspect del float decorado
    @inner.inspect
  end
end

# ahora si va a mostra simplemente 1.41
p FloatPrecisionDecorator.new(2,100)**0.5

Numeric


Es mejor si se puede hacer asi:


4.0.to_reduced_precision(:decimals => 2)

4.0.to_rp(:decimals => 2)

Para eso lo mejor es agregarle el metodo a la clase numeric:

class Numeric
  def self.reduce_precision(number, factor)
    (number.to_f * factor).round.to_f / factor
  end

  def to_single_precision(options)
    unless options[:factor]
      options[:factor] = (options[:base]||10) ** (options[:decimals]||10)
    end

    factor = options[:factor]

    FloatPrecisionDecorator.new(Numeric.reduce_precision(to_f, factor), factor)
  end
end

Coerce



Puede surgir que se tenga que sumar un numero de precision reducida a un float, pero el metodo + de la clase Float de ruby no tiene forma de saber como sumar el numero que implementamos nosotros. Esos casos ruby lo contempla con el metodo coerce, que habilita conmutar los numeros en una operacion matematica, asi:
class FloatPrecisionDecorator
  def coerce(other)
    return self, other
  end
end

inifinite?, nan? y demas


Si se hace a nuestro numero


p 2.to_sp(:decimals => 10).infinite?


Va a devolver 0.0, cuando se supone que el metodo inifnite debe devolver true o false, esto ocurre porque inifnite? tambien llama a method_missing y este trata de truncar y wrappear lo que sea, lo mejor en estos casos es evitar modificar objetos que no sean numeros. Habra que modificar method_missing:

class FloatPrecisionDecorator
  def method_missing(m,*x)
    # todas las operaciones sobre el numero se ejecutan sobre el float verdadero
    # y se obtiene el verdadero resultado con precision completa del Float original
    verdadero_resultado = @inner.send(m,*x)

    # si es numeric, truncar y wrappear
    if Numeric === verdadero_resultado
      # se reduce la precision, multiplicando por el factor, redondeando y volviendo a dividir
      reduced = (verdadero_resultado.to_f * @factor).round.to_f / @factor
      FloatPrecisionDecorator.new(reduced, @factor)
    else
      # si no, devolve el resultado como es
      verdadero_resultado
    end
  end
end

Codigo completo





class Numeric
  def self.reduce_precision(number, factor)
    (number.to_f * factor).round.to_f / factor
  end

  def to_single_precision(options)
    unless options[:factor]
      options[:factor] = (options[:base]||10) ** (options[:decimals]||10)
    end

    factor = options[:factor]

    FloatPrecisionDecorator.new(Numeric.reduce_precision(to_f, factor), factor)
  end
end

class FloatPrecisionDecorator
  def initialize(inner, factor)
    @factor = factor
    @inner = inner.to_f
  end

  def method_missing(m,*x)
    # todas las operaciones sobre el numero se ejecutan sobre el float verdadero
    # y se obtiene el verdadero resultado con precision completa del Float original
    verdadero_resultado = @inner.send(m,*x)

    # si es numeric, truncar y wrappear
    if Numeric === verdadero_resultado
      # se reduce la precision, multiplicando por el factor, redondeando y volviendo a dividir
      reduced = (verdadero_resultado.to_f * @factor).round.to_f / @factor
      FloatPrecisionDecorator.new(reduced, @factor)
    else
      # si no, devolve el resultado como es
      verdadero_resultado
    end
  end

  def coerce(other)
    return self, other
  end

  def inspect
    # para que llame al inspect del float decorado
    @inner.inspect
  end
end

p FloatPrecisionDecorator.new(2,10).infinite?



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