python - Python 中的 sqrt 函数奇怪行为

Question

在 Python 中，我编写了一个自定义代码 sqrt(x, delta) 以使用 delta-close 近似计算给定数字的平方根。它使用 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'奇数' 或 1e'偶数' 的数字，但正如我们在示例中看到的那样，事实并非如此。我也尝试使用不同的 delta 而不是 1/1024，但它们表现出类似的行为。

如果能说明导致此行为的幕后情况，我将不胜感激。

Answer 1

float只能表示一个有限的数字集。您的代码最终会出现 start和 end是两个连续的这样的数字。结果，(start + end) / 2必须向下舍入为 start或四舍五入为 end .

如果向下舍入，middle_2 < x .现在，如果 end - start > delta ，你有一个“太低”的无限循环。

如果它被四舍五入，如果 end - start > delta ，你有一个“太高”的无限循环。

您可能应该重新定义 delta作为相对错误而不是绝对错误。