単調増加関数の逆関数、log10（）のOverflowError

Question

代入のために逆関数を返す関数を作成するよう求められました。基本的な問題は、平方関数から平方根関数を作成することでした。私は、バイナリ検索とニュートンの方法を使った別のソリューションを使ったソリューションを思いついた。私のソリューションは、キューブルートと平方根ではうまく動作するようですが、log10ではうまく動作しないようです。ここに私の解決策は以下のとおりです。教授のテスト機能で）（Iは入力を取得する場合、

#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 = log10のための10000、私はこのエラーを取得：（例外：私のニュートン法の機能を）（log10の、使用される入力閾値に達するまで、このバイナリ・サーチ法は比較的正確であるのに対し、方法オフいずれかの方法で、両方のソリューションは、このエラーをスロー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 

ので、あなたは= 10千^Xの結果は500.0で、しかし確実に10 が大きすぎると思います。最初の推測値は、fに対して有効であることが選択され、逆数はfではありません。

私はあなたが、1の推測で初期化する、すなわち

guess = 1 

でそのラインを交換し、それが正常に動作する必要がありますことを示唆しました。あなたは解決策が0〜Yであると仮定しているため

---

はところで、あなたのバイナリ検索の初期状態は、また間違っている：

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とKennyTMが優れた答えを指摘しているので、これはアルゴリズム上の欠陥に対する救済策ではありません。

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あなたは、このような大規模な数を計算する必要がある理由あなたはどちらかを再評価する必要が

を見つけましたそれに応じてあなたのコードを変更する::提案）、またはいくつかのより大きい数の処理ソリューションを探し始める。

あなたをも関数が単調に増加アレント場合、ゼロ除算といくつかの問題を解決し、それらの領域を避けることができた（ステートメントを試してみてください）特定の入力は、それが失敗する原因になりますかどうかを確認するためにあなたの逆関数を編集したり、

ができy = xについての「興味深い」領域のいくつかの点を鏡映し、それらの点を通る補間スキームを使用して、逆関数（エルミート、テイラー級など）を作成することができる。