python - 有人可以解释以下功能之间的速度差异吗？

Question

第一个函数是一个简单的二进制搜索实现，用于查找数字的平方根：

def sqrt1(x):
    if x < 0:
        raise ValueError(x)
    if x > 0:
        if x < 1:
            root = 1
            while root ** 2 > x:
                root /= 2
            half = root
            while root ** 2 != x:
                half /= 2
                diff = root + half
                if diff == root:
                    return root
                if diff ** 2 <= x:
                    root = diff
            return root
        if x > 1:
            root = 1
            while root ** 2 < x:
                root *= 2
            half = root / 2
            while root ** 2 != x:
                half /= 2
                diff = root - half
                if diff == root:
                    return root
                if diff ** 2 >= x:
                    root = diff
            return root
        return 1
    return 0

第二个函数做同样的事情，但比第一个更简单，速度快 15 倍：

def sqrt2(z):
    assert z > 0
    x, y = z, None
    while x != y:
        y = x
        x = (x + z / x) / 2
    return x

1. 为什么sqrt2比 快那么多sqrt1？
2. 可以sqrt1做成表演更喜欢sqrt2吗？

Answer 1

二进制搜索

算法 1 进行二进制搜索。因此，如果您正在寻找 2 的平方根，您将在每次迭代后得到以下结果：

1.0
1.0
1.25
1.375
1.375
1.40625
1.40625
1.4140625
1.4140625
1.4140625
1.4140625
1.4140625
1.4140625
1.4141845703125
1.4141845703125
1.4141845703125
1.4141998291015625
1.41420745849609375

我们已经运行了 17 次迭代，我们有 6 个正确的数字：1.41421。在另外 17 次迭代之后，我们可能会得到大约 12 个正确的数字。在第 34 次迭代中，我们得到：

1.4142135623260401189327239990234375

这里正确的数字是1.414213562，所以只有10位。

牛顿法

第二种方法是牛顿法，它具有二次收敛性。这意味着每次迭代你得到两倍的数字，所以你会得到：

0 2.0
1 1.5
2 1.4166666666666666666666666666666666666666666666666666666667
5 1.41421568627450980392156862745098039215686274509803921568627
12 1.414213562374689910626295578​​89013491011655962211574404458491
24 1.41421356237309504880168962350253024361498192577619742849829
49 1.41421356237309504880168872420969807856967187537723400156101
60+ 1.41421356237309504880168872420969807856967187537694807317668

左列显示正确数字的数量——注意它是如何呈指数增长的。我在这里截断了输出，因为经过7次迭代，结果对我选择的精度是正确的。（这实际上是使用比 Python 更高的精度数据类型运行的float，它永远不能给你 60 位的精度。）

是否有可能使二进制搜索更快？

不，如果你让它更快，它就不可能再被称为二分搜索了。