有人能解释一下下列功能之间的速度差异吗？

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.41666666666666666666666666666666666666666666666666666666667
5   1.41421568627450980392156862745098039215686274509803921568627
12  1.41421356237468991062629557889013491011655962211574404458491
24  1.41421356237309504880168962350253024361498192577619742849829
49  1.41421356237309504880168872420969807856967187537723400156101
60+ 1.41421356237309504880168872420969807856967187537694807317668

左列显示了正确的位数注意它是如何指数增长的。我在这里切断了输出，因为经过7次迭代后，结果与我选择的精度是正确的。（这实际上是用比Python的float更高精度的数据类型运行的，Python的float不能提供60位精度）

有可能使二进制搜索更快吗？你知道吗

不，如果你再快一点，它就不可能再被称为二进制搜索了。你知道吗