Funkcja odwrotna dla funkcji monotonicznej zwiększania, OverflowError dla log10()

Question

W celu przypisania, poproszono nas o utworzenie funkcji, która zwraca funkcję odwrotną. Podstawowym problemem było utworzenie pierwiastka kwadratowego z funkcji kwadratowej. Wymyśliłem rozwiązanie za pomocą wyszukiwania binarnego i innego rozwiązania wykorzystującego metodę Newtona. Moje rozwiązanie wydaje się działać dobrze dla modułu-root i pierwiastka kwadratowego, ale nie dla log10. Oto moje rozwiązania:

#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 

Niezależnie, która metoda jest stosowana, kiedy się do wejścia n = 10000 dla log10() w funkcji testowej profesora, otrzymuję ten błąd: (wyjątek: gdy funkcja metoda mojego newtona stosuje się, log10() jest daleko, a metoda ta binarnie wyszukiwania jest względnie dokładne aż do osiągnięcia progu wejściu, albo inaczej, oba roztwory rzut tego błędu, gdy 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') 

jest tu testy funkcja:

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

To jest jak test jest konfiguracja:

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

Pozostałe rozwiązania wysłane wydają się mieć żadnych problemów z systemem pełnego zestawu wejść testowych (Mam starał się nie patrzeć na zamieszczonych rozwiązań). Wszelkie wgląd w ten błąd?

---

Wydaje się, że konsensus jest wielkości liczby, jednak kod mój profesor wydaje się działać dobrze dla wszystkich przypadków:

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

WYNIKI:

 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

To jest rzeczywiście problem w rozumieniu matematyki zamiast programu. Algorytm jest w porządku, ale dostarczony warunek początkowy nie jest.

zdefiniować inverse(f, delta) tak:

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

więc odgadnąć wynik 1000 = 10 ^x jest 500,0, ale na pewno 10 jest zbyt duża. Początkowe domysły powinny być ważne dla f, nie wybrane dla odwrotności f.

I zasugerował, że należy zainicjować z przypuszczeniem 1, tj zastąpić tę linię z

guess = 1 

i powinno działać dobrze.

---

BTW, początkowy stan binarnym wyszukiwania jest też źle, bo zakładamy, że rozwiązaniem jest między 0 i y:

low, high = 0, float(y) 

to prawda dla przypadków testowych, ale jest to łatwe do skonstruuj przykłady liczników np log 0,1 (= 1), √ 0,36 (= 0,6) i inne (find_bounds metoda, profesora nie rozwiązuje problemu √ 0,36, ale nie obsługuje dzienniku 0,1 problemu).

Answer 2

Jeśli używasz Python 2.x, int i long są różne typy, a OverflowError może tylko wynik dla ints (qv, Built-in Exceptions). Zamiast tego spróbuj jawnie użyć longs (używając wbudowanej funkcji long() na swoich wartościach całkowitych lub dołączając L do literałów numerycznych).

Edycja: Oczywiście, jak zauważyli Paul Seeb i KennyTM w swoich lepszych odpowiedziach, nie jest to lekarstwem na defekt algorytmiczny.

Answer 3

Wykreślam twój błąd, ale w zasadzie sprowadza się to do faktu, że 10 ** 10000000 powoduje przepełnienie w pytonie. szybkie sprawdzenie przy użyciu biblioteki matematyczne

math.pow(10,10000000) 

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

Zrobiłem trochę badań dla Ciebie i znaleźć ten

Handling big numbers in code

Trzeba albo ponownej oceny, dlaczego trzeba obliczyć tak dużej liczby (i zmień odpowiednio swój kod :: sugerowany) lub zacznij szukać jeszcze większej liczby rozwiązań do obsługi numerów.

Można edytować funkcję odwrotną do sprawdzenia, czy pewne wejścia spowoduje to niepowodzenie (spróbuj oświadczenie), który może również rozwiązać niektóre problemy z zerowym podziału jeżeli funkcje arent monotonicznie rośnie, a unikać tych regionów lub

cię może odzwierciedlać liczbę punktów w "interesującym" obszarze wokół y = x i używać schematu interpolacji przez te punkty, aby utworzyć funkcję "odwrotną" (hermita, seria Taylora, itd.).