3

Python でカスタム コード sqrt(x, delta) を作成し、デルタ近似で特定の数値の平方根を計算しました。while ループと二分探索のようなアルゴリズムを使用します。
コード： 

from __future__ import division

def sqrt(x, delta):
    start = 0
    end = x
    while (end-start) > delta:
        middle = (start + end) / 2
        middle_2 = middle * middle
        if middle_2 < x:
            start = middle
            print "too low"
        elif middle_2 > x:
            end = middle
            print "too high"
        else:
            return middle
    result = (start + end) / 2
    return result


基本的に動作し、かなり高速ですが、無限whileループに陥る場合があります。
例:

sqrt(1e27, 1/1024) => works fine (returns 'too low's and 'too high's, then returns correct result)
sqrt(1e28, 1/1024) => works fine
sqrt(1e29, 1/1024) => never-ending loop, it keeps printing 'too low' forever
sqrt(1e30, 1/1024) => works fine
sqrt(1e31, 1/1024) => 'too low' forever
sqrt(1e32, 1/1024) => works fine
sqrt(1e33, 1/1024) => works fine (also surprising after the problem with 1e29 and 1e31)
sqrt(1e34, 1/1024) => works fine
sqrt(1e35, 1/1024) => 'too low' forever
sqrt(1e36, 1/1024) => works fine
sqrt(1e37, 1/1024) => 'too high' forever (too high this time!)
sqrt(1e38, 1/1024) => works fine
sqrt(1e39, 1/1024) => works fine (surprising again..)
... 1e40-1e45 ... they all work fine
sqrt(1e46, 1/1024) => 'too low' forever (surprisingly it occurs now with 1e'even number')
...
sqrt(1e200, 1/1024) => works fine
sqrt(1e201, 1/1024) => works fine
...
sqrt(1e299, 1/1024) => 'too low' forever
sqrt(1e300, 1/1024) => 'too high' forever
...
sqrt(1e304, 1/1024) => 'too high' forever
sqrt(1e305, 1/1024) => works fine
... 305-308 ... they allwork fine
sqrt(1e309, 1/1024) => inf (reached some 'infinite' limit?)

最初は、1e20 などの制限を超える数字だと思っていましたが、その後、それらでも機能しました。また、これは 1e'odd' または 1e'even' の数字だと思っていましたが、例でわかるように、そうではありませんでした。1/1024 の代わりに別のデルタを使用して試してみましたが、同様の動作を示しました。

この動作を引き起こす舞台裏で何が起こっているのかを説明していただければ幸いです。

4

1 に答える 1

4

float数の有限集合しか表現できません。あなたのコードは、startとendが 2 つの連続したそのような数字になる状況になります。その結果、(start + end) / 2は に切り下げるか、切り上げる必要がありstartますend。

切り捨ての場合はmiddle_2 < x. の場合end - start > delta、「低すぎる」無限ループになります。

切り上げられた場合、および の場合end - start > delta、「高すぎる」無限ループが発生しています。

おそらくdelta、絶対誤差ではなく相対誤差として再定義する必要があります。

于 2012-12-15T21:46:16.200 に答える