單調遞增函數的反函數，log10（）的溢出錯誤

Question

對於一個賦值，我們被要求創建一個返回反函數的函數。基本問題是從平方函數創建平方根函數。我想出了一個使用二分查找的解決方案和另一個使用牛頓方法的解決方案。我的解決方案似乎適用於立方根和平方根，但不適用於log10。這裏是我的解決方案：

#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 

無論使用哪種方法，當我到達輸入N = 10000在教授的測試功能LOG10（），我得到這個錯誤：（例外：當我的牛頓法功能使用時，日誌10（）是遙遠，而該二進制搜索方法是相對準確的，直到達到輸入閾值時，無論哪種方式，這兩種解決方案拋出此錯誤當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') 

下面是測試功能：

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

這些是測試是如何設置：

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

發佈的其他解決方案似乎都運行全套測試輸入（我儘量不看發佈的解決方案）沒有任何問題。任何洞察到這個錯誤？

---

這好像共識是數字的大小，但是，我的教授的代碼似乎工作得很好，對所有情況：

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

結果：

 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

這實際上是您理解數學而不是程序的問題。算法很好，但提供的初始條件不是。

你定義inverse(f, delta)這樣的：

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

所以你猜的1000結果= 10 ^X爲500.0，但肯定10 太大。最初的猜測應該選擇爲f有效，而不是f的倒數。

我建議你初始化爲1的猜測，即具有

guess = 1 

替換該行，它應該工作的罰款。

---

順便說一句，您的二進制搜索的初始條件也是錯誤的，因爲你認爲解決的辦法是介於0和ÿ：

low, high = 0, float(y) 

這是你的測試用例真實的，但它很容易構造計數器例子登錄 0.1（= -1），√ 0.36（= 0.6）等。（你的教授的find_bounds方法確實解決了√ 0.36的問題，但仍然不會處理日誌 0.1的問題。）

Answer 2

如果您使用的是Python 2.x，則int和long是不同的類型，而OverflowError只能產生ints（qv，Built-in Exceptions）。嘗試明確地使用longs來代替（通過對整數值使用long()內置函數，或將L附加到數字文字）。

編輯：顯然，正如Paul Seeb和Kenny在他們的優秀答案中指出的那樣，這對算法缺陷沒有任何補救措施。

Answer 3

我跟蹤了你的錯誤，但它基本上歸結爲10 ** 10000000導致python溢出的事實。使用數學庫

math.pow(10,10000000) 

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

快速檢查我做了一些研究工作，你發現這個

Handling big numbers in code

你需要或者重新評估爲什麼你需要計算數量如此龐大的（並相應地更改你的代碼::建議）或者開始尋找更大的數字處理解決方案。

你可以編輯自己的反函數來檢查，如果某些輸入會導致失敗（try語句），這也可以解決一些問題，除數爲零，如果功能的arent單調遞增，並避免那些區域或

你可以反映y = x「有趣」區域中的多個點，並通過這些點使用插值方案創建「反向」函數（hermite's，泰勒級數等）。