Funzione inversa per funzione di aumento monotono, OverflowError per log10()

Question

Per un compito, è stato chiesto di creare una funzione che restituisca una funzione inversa. Il problema di base era creare una funzione radice quadrata da una funzione quadrata. Ho trovato una soluzione usando la ricerca binaria e un'altra soluzione usando il metodo di Newton. La mia soluzione sembra funzionare bene per cube-root e square-root ma non per log10. Qui sono le mie soluzioni:

#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 

Indipendentemente dal metodo utilizzato, quando arrivo all'ingresso n = 10000 per log10() nella funzione di test del professore, ottengo questo errore: (eccezione: quando la funzione metodo di mio newton viene utilizzato, log10() è lontana, che tale metodo ricerca binaria è relativamente accurato fino al raggiungimento della soglia d'ingresso, in entrambi i casi, entrambe le soluzioni gettare questo errore quando 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') 

Qui è il test Funzione:

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 ****')) 

Questi è come il test è messa a punto:

#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() 

Le altre soluzioni postato sembrano non avere problemi durante l'esecuzione il set completo di ingressi di prova (ho cercato di non guardare le soluzioni postato). Qualche informazione su questo errore?

---

Sembra come se il consenso è la dimensione del numero, tuttavia, il codice del mio professore sembra funzionare bene per tutti i casi:

#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() 

RISULTATI:

 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

Questo è in realtà un problema nella comprensione della matematica invece del programma. L'algoritmo va bene, ma la condizione iniziale fornita non lo è.

si definisce inverse(f, delta) in questo modo:

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

in modo da indovinare il risultato di 1000 = 10 x è 500.0, ma sicuramente 10 è troppo grande. L'ipotesi iniziale dovrebbe essere considerata valida per f, non scelta per l'inverso di f.

ho suggerito che si inizializza con un'ipotesi di 1, vale a dire sostituire quella linea con

guess = 1 

e dovrebbe funzionare bene.

---

BTW, condizione iniziale del binario di ricerca è anche sbagliato, perché si assume la soluzione è compreso tra 0 e y:

low, high = 0, float(y) 

questo è vero per i vostri casi di test, ma è facile costruisci esempi di contro es log 0,1 (= -1), √ 0,36 (= 0,6), ecc (metodo del tuo professore find_bounds risolve il problema √ 0,36, ma ancora non in grado di gestire il registro 0,1 problema.)

Answer 2

Se si utilizza Python 2.x, e long sono tipi distinti e lo OverflowError può risultare solo per ints (qv, Built-in Exceptions). Prova in modo esplicito usando longs (usando la funzione integrata long() sui valori interi o aggiungendo L ai valori letterali numerici).

Edit: Ovviamente, come Paul Seeb e KennyTM hanno sottolineato nelle loro risposte superiori, questo non è un rimedio per un difetto algoritmico.

Answer 3

Ho tracciato il tuo errore ma fondamentalmente si riduce al fatto che 10 ** 10000000 provoca un overflow in python. un rapido controllo utilizzando la libreria matematica

math.pow(10,10000000) 

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

ho fatto una piccola ricerca per voi e pensano che questa

Handling big numbers in code

Devi o ri-valutare il motivo per cui è necessario calcolare un numero così elevato (e modificare il codice di conseguenza :: suggerito) o iniziare a cercare soluzioni di gestione dei numeri ancora più grandi.

Si potrebbe modificare la funzione inversa per controllare se determinati ingressi causerà il fallimento (provare economico) che potrebbe anche risolvere alcuni problemi con la divisione zero se le funzioni arent monotona crescente, ed evitare quelle regioni o

voi potrebbe rispecchiare un numero di punti nell'area "interessante" su y = x e utilizzare uno schema di interpolazione attraverso questi punti per creare la funzione "inversa" (eremitaggio, serie taylor, ecc.).