Función inversa para la función monótonamente creciente, OverflowError para log10()

Question

Para una asignación, se nos pidió que creáramos una función que devuelva una función inversa. El problema básico era crear una función de raíz cuadrada a partir de una función cuadrada. Se me ocurrió una solución usando búsqueda binaria y otra solución usando el método de Newton. Mi solución parece funcionar bien para raíz de cubo y raíz cuadrada, pero no para log10. Aquí están mis soluciones:

#Binary Search 
def inverse1(f, delta=1e-8): 
    """Given a function y = f(x) that is a monotonically increasing function on 
    non-negative numbers, return the function x = f_1(y) that is an approximate 
    inverse, picking the closest value to the inverse, within delta.""" 
    def f_1(y): 
     low, high = 0, float(y) 
     last, mid = 0, high/2 
     while abs(mid-last) > delta: 
      if f(mid) < y: 
       low = mid 
      else: 
       high = mid 
      last, mid = mid, (low + high)/2 
     return mid 
    return f_1 

#Newton's Method 
def inverse(f, delta=1e-5): 
    """Given a function y = f(x) that is a monotonically increasing function on 
    non-negative numbers, return the function x = f_1(y) that is an approximate 
    inverse, picking the closest value to the inverse, within delta.""" 
    def derivative(func): return lambda y: (func(y+delta) - func(y))/delta 
    def root(y): return lambda x: f(x) - y 
    def newton(y, iters=15): 
     guess = float(y)/2 
     rootfunc = root(y) 
     derifunc = derivative(rootfunc) 
     for _ in range(iters): 
      guess = guess - (rootfunc(guess)/derifunc(guess)) 
     return guess 
    return newton 

Independientemente del método que se utilice, cuando llegue a la entrada n = 10000 para log10() en la función de prueba del profesor, me sale este error: (Excepción: cuando la función método de mi newton se utiliza, log10() es manera, mientras que este método binario-búsqueda es relativamente precisa hasta que se alcanza el umbral de entrada, de cualquier manera, ambas soluciones tire este error cuando n = 10000)

2: sqrt =  1.4142136 ( 1.4142136 actual); 0.0000 diff; ok 
    2: log =  0.3010300 ( 0.3010300 actual); 0.0000 diff; ok 
    2: cbrt =  1.2599211 ( 1.2599210 actual); 0.0000 diff; ok 
    4: sqrt =  2.0000000 ( 2.0000000 actual); 0.0000 diff; ok 
    4: log =  0.6020600 ( 0.6020600 actual); 0.0000 diff; ok 
    4: cbrt =  1.5874011 ( 1.5874011 actual); 0.0000 diff; ok 
    6: sqrt =  2.4494897 ( 2.4494897 actual); 0.0000 diff; ok 
    6: log =  0.7781513 ( 0.7781513 actual); 0.0000 diff; ok 
    6: cbrt =  1.8171206 ( 1.8171206 actual); 0.0000 diff; ok 
    8: sqrt =  2.8284271 ( 2.8284271 actual); 0.0000 diff; ok 
    8: log =  0.9030900 ( 0.9030900 actual); 0.0000 diff; ok 
    8: cbrt =  2.0000000 ( 2.0000000 actual); 0.0000 diff; ok 
    10: sqrt =  3.1622777 ( 3.1622777 actual); 0.0000 diff; ok 
    10: log =  1.0000000 ( 1.0000000 actual); 0.0000 diff; ok 
    10: cbrt =  2.1544347 ( 2.1544347 actual); 0.0000 diff; ok 
    99: sqrt =  9.9498744 ( 9.9498744 actual); 0.0000 diff; ok 
    99: log =  1.9956352 ( 1.9956352 actual); 0.0000 diff; ok 
    99: cbrt =  4.6260650 ( 4.6260650 actual); 0.0000 diff; ok 
100: sqrt = 10.0000000 ( 10.0000000 actual); 0.0000 diff; ok 
100: log =  2.0000000 ( 2.0000000 actual); 0.0000 diff; ok 
100: cbrt =  4.6415888 ( 4.6415888 actual); 0.0000 diff; ok 
101: sqrt = 10.0498756 ( 10.0498756 actual); 0.0000 diff; ok 
101: log =  2.0043214 ( 2.0043214 actual); 0.0000 diff; ok 
101: cbrt =  4.6570095 ( 4.6570095 actual); 0.0000 diff; ok 
1000: sqrt = 31.6227766 ( 31.6227766 actual); 0.0000 diff; ok 
Traceback (most recent call last): 
    File "/CS212/Unit3HW.py", line 296, in <module> 
    print test() 
    File "/CS212/Unit3HW.py", line 286, in test 
    test1(n, 'log', log10(n), math.log10(n)) 
    File "/CS212/Unit3HW.py", line 237, in f_1 
    if f(mid) < y: 
    File "/CS212/Unit3HW.py", line 270, in power10 
    def power10(x): return 10**x 
OverflowError: (34, 'Result too large') 

Aquí es la prueba función:

def test(): 
    import math 
    nums = [2,4,6,8,10,99,100,101,1000,10000, 20000, 40000, 100000000] 
    for n in nums: 
     test1(n, 'sqrt', sqrt(n), math.sqrt(n)) 
     test1(n, 'log', log10(n), math.log10(n)) 
     test1(n, 'cbrt', cbrt(n), n**(1./3.)) 


def test1(n, name, value, expected): 
    diff = abs(value - expected) 
    print '%6g: %s = %13.7f (%13.7f actual); %.4f diff; %s' %(
     n, name, value, expected, diff, 
     ('ok' if diff < .002 else '**** BAD ****')) 

0 Estos

es como la prueba es de configuración:

#Using inverse() or inverse1() depending on desired method 
def power10(x): return 10**x 
def square(x): return x*x 
log10 = inverse(power10) 
def cube(x): return x*x*x 
sqrt = inverse(square) 
cbrt = inverse(cube) 
print test() 

Las otras soluciones publicadas parecen no tener problemas al ejecutar el conjunto completo de entradas de prueba (He tratado de no mirar con las soluciones publicadas). ¿Alguna idea de este error?

---

Parece como si el consenso es el tamaño de la serie, sin embargo, el código de mi profesor parece funcionar muy bien para todos los casos:

#Prof's code: 
def inverse2(f, delta=1/1024.): 
    def f_1(y): 
     lo, hi = find_bounds(f, y) 
     return binary_search(f, y, lo, hi, delta) 
    return f_1 

def find_bounds(f, y): 
    x = 1 
    while f(x) < y: 
     x = x * 2 
    lo = 0 if (x ==1) else x/2 
    return lo, x 

def binary_search(f, y, lo, hi, delta): 
    while lo <= hi: 
     x = (lo + hi)/2 
     if f(x) < y: 
      lo = x + delta 
     elif f(x) > y: 
      hi = x - delta 
     else: 
      return x; 
    return hi if (f(hi) - y < y - f(lo)) else lo 

log10 = inverse2(power10) 
sqrt = inverse2(square) 
cbrt = inverse2(cube) 

print test() 

RESULTADOS:

 2: sqrt =  1.4134903 ( 1.4142136 actual); 0.0007 diff; ok 
    2: log =  0.3000984 ( 0.3010300 actual); 0.0009 diff; ok 
    2: cbrt =  1.2590427 ( 1.2599210 actual); 0.0009 diff; ok 
    4: sqrt =  2.0009756 ( 2.0000000 actual); 0.0010 diff; ok 
    4: log =  0.6011734 ( 0.6020600 actual); 0.0009 diff; ok 
    4: cbrt =  1.5865107 ( 1.5874011 actual); 0.0009 diff; ok 
    6: sqrt =  2.4486818 ( 2.4494897 actual); 0.0008 diff; ok 
    6: log =  0.7790794 ( 0.7781513 actual); 0.0009 diff; ok 
    6: cbrt =  1.8162270 ( 1.8171206 actual); 0.0009 diff; ok 
    8: sqrt =  2.8289337 ( 2.8284271 actual); 0.0005 diff; ok 
    8: log =  0.9022484 ( 0.9030900 actual); 0.0008 diff; ok 
    8: cbrt =  2.0009756 ( 2.0000000 actual); 0.0010 diff; ok 
    10: sqrt =  3.1632442 ( 3.1622777 actual); 0.0010 diff; ok 
    10: log =  1.0009756 ( 1.0000000 actual); 0.0010 diff; ok 
    10: cbrt =  2.1534719 ( 2.1544347 actual); 0.0010 diff; ok 
    99: sqrt =  9.9506714 ( 9.9498744 actual); 0.0008 diff; ok 
    99: log =  1.9951124 ( 1.9956352 actual); 0.0005 diff; ok 
    99: cbrt =  4.6253061 ( 4.6260650 actual); 0.0008 diff; ok 
    100: sqrt = 10.0004883 ( 10.0000000 actual); 0.0005 diff; ok 
    100: log =  2.0009756 ( 2.0000000 actual); 0.0010 diff; ok 
    100: cbrt =  4.6409388 ( 4.6415888 actual); 0.0007 diff; ok 
    101: sqrt = 10.0493288 ( 10.0498756 actual); 0.0005 diff; ok 
    101: log =  2.0048876 ( 2.0043214 actual); 0.0006 diff; ok 
    101: cbrt =  4.6575475 ( 4.6570095 actual); 0.0005 diff; ok 
    1000: sqrt = 31.6220242 ( 31.6227766 actual); 0.0008 diff; ok 
    1000: log =  3.0000000 ( 3.0000000 actual); 0.0000 diff; ok 
    1000: cbrt = 10.0004883 ( 10.0000000 actual); 0.0005 diff; ok 
10000: sqrt = 99.9991455 ( 100.0000000 actual); 0.0009 diff; ok 
10000: log =  4.0009756 ( 4.0000000 actual); 0.0010 diff; ok 
10000: cbrt = 21.5436456 ( 21.5443469 actual); 0.0007 diff; ok 
20000: sqrt = 141.4220798 ( 141.4213562 actual); 0.0007 diff; ok 
20000: log =  4.3019052 ( 4.3010300 actual); 0.0009 diff; ok 
20000: cbrt = 27.1449150 ( 27.1441762 actual); 0.0007 diff; ok 
40000: sqrt = 199.9991455 ( 200.0000000 actual); 0.0009 diff; ok 
40000: log =  4.6028333 ( 4.6020600 actual); 0.0008 diff; ok 
40000: cbrt = 34.2003296 ( 34.1995189 actual); 0.0008 diff; ok 
1e+08: sqrt = 9999.9994545 (10000.0000000 actual); 0.0005 diff; ok 
1e+08: log =  8.0009761 ( 8.0000000 actual); 0.0010 diff; ok 
1e+08: cbrt = 464.1597912 ( 464.1588834 actual); 0.0009 diff; ok 
None 

Answer 1

Esto es realmente un problema en su comprensión de math en lugar del programa. El algoritmo está bien, pero la condición inicial suministrada no.

definiría usted inverse(f, delta) así:

def inverse(f, delta=1e-5): 
    ... 
    def newton(y, iters=15): 
     guess = float(y)/2 
     ... 
    return newton 

por lo que supongo que el resultado de 1000 = 10 x es 500.0, pero con seguridad 10 es demasiado grande. La conjetura inicial debe elegirse en una válida para f, no elegida para el inverso de f.

me sugirió que inicializar con una suposición de 1, es decir, reemplazar esa línea con

guess = 1 

y debería funcionar bien.

---

Por cierto, condición inicial de su búsqueda binaria también es incorrecto, ya que se asume que la solución es entre 0 y y:

low, high = 0, float(y) 

esto es cierto para los casos de prueba, pero es fácil de construir contra ejemplos por ejemplo log 0,1 (= -1), √ 0,36 (= 0,6), etc. (método de su profesor find_bounds hace resolver el √ 0,36 problema, pero todavía no manejará el registro de 0,1 problema.)

Answer 2

Si está utilizando Python 2.x, int y long son tipos distintos, y OverflowError solo puede dar como resultado ints (qv, Built-in Exceptions). Intente usar explícitamente longs en su lugar (ya sea utilizando la función integrada long() en sus valores integrales, o agregando L a los literales numéricos).

Editar: Obviamente, como Paul Seeb y KennyTM han señalado en sus respuestas superiores, esto no es remedio para una falla algorítmica.

Answer 3

Rastreé su error, pero básicamente se debe al hecho de que 10 ** 10000000 causa un desbordamiento en python. una comprobación rápida usando la biblioteca matemática

math.pow(10,10000000) 

Traceback (most recent call last): 
    File "<pyshell#3>", line 1, in <module> 
    math.pow(10,10000000) 
OverflowError: math range error 

lo hice un poco de investigación para usted y encontraron esta

Handling big numbers in code

Es necesario o bien volver a evaluar qué es necesario calcular un número tan grande (y cambie su código según corresponda :: sugerido) o comience a buscar soluciones de manejo de números aún mayores.

Se puede editar su función inversa para comprobar si determinadas entradas provocarán que falle (try), que también podría resolver algunos problemas con la división de cero si las funciones enviaban monótonamente creciente, y evitar aquellas regiones o

se podría reflejar una cantidad de puntos en el área "interesante" sobre y = x y usar un esquema de interpolación a través de esos puntos para crear la función "inversa" (hermite, serie taylor, etc.).