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

2番目の関数は同じことを行いますが、最初の関数よりも単純で約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桁のみです。

ニュートン法

2番目の方法は、2次収束を持つニュートン法です。これは、反復ごとに2倍の桁を取得することを意味するため、次のようになります。

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

左の列は正しい桁数を示しています-指数関数的に増加することに注意してください。7回の反復の後、結果は選択した精度に正確であるため、ここで出力を切り取りました。（これは実際にはPythonよりも高精度のデータ型で実行されてfloatいたため、60桁の精度を実現することはできません。）

二分探索をより速くすることは可能ですか？

いいえ。高速化すると、二分探索とは言えなくなります。