Algorithm - Python - 平方根もカッコイイ(3次方程式の解(根)の近似値、浮動小数点数と浮動小数点算術、連続領域の二分法、離散二分探索)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の7章(平方根もカッコイイ)、練習問題(問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def bisection_search(epsilon: float = 0.01):
    num_guesses = 0
    low = -10
    high = 10
    x = (low + high) / 2.0
    while abs(x ** 3 + x ** 2 - 11) >= epsilon:
        print(x)
        if x < 0:
            low = x
        elif x ** 3 + x ** 2 - 11 < 0:
            low = x
        else:
            high = x
        x = (low + high) / 2.0
        num_guesses += 1

    print(f'num_guesse = {num_guesses}')
    print(f'Answer is {x}')


if __name__ == '__main__':
    for epsilon in range(10):
        bisection_search(10**-epsilon)

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample3.py
0.0
5.0
2.5
1.25
num_guesse = 4
Answer is 1.875
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
num_guesse = 9
Answer is 1.93359375
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
num_guesse = 12
Answer is 1.93603515625
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
num_guesse = 15
Answer is 1.93572998046875
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
1.93572998046875
1.935577392578125
1.9356536865234375
1.9356918334960938
num_guesse = 19
Answer is 1.9357109069824219
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
1.93572998046875
1.935577392578125
1.9356536865234375
1.9356918334960938
1.9357109069824219
1.9357013702392578
1.9357061386108398
num_guesse = 22
Answer is 1.9357085227966309
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
1.93572998046875
1.935577392578125
1.9356536865234375
1.9356918334960938
1.9357109069824219
1.9357013702392578
1.9357061386108398
1.9357085227966309
1.9357073307037354
1.935707926750183
num_guesse = 25
Answer is 1.935708224773407
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
1.93572998046875
1.935577392578125
1.9356536865234375
1.9356918334960938
1.9357109069824219
1.9357013702392578
1.9357061386108398
1.9357085227966309
1.9357073307037354
1.935707926750183
1.935708224773407
1.935708373785019
1.935708299279213
1.93570826202631
1.9357082433998585
num_guesse = 30
Answer is 1.9357082340866327
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
1.93572998046875
1.935577392578125
1.9356536865234375
1.9356918334960938
1.9357109069824219
1.9357013702392578
1.9357061386108398
1.9357085227966309
1.9357073307037354
1.935707926750183
1.935708224773407
1.935708373785019
1.935708299279213
1.93570826202631
1.9357082433998585
1.9357082340866327
1.9357082294300199
1.9357082317583263
num_guesse = 33
Answer is 1.9357082329224795
0.0
5.0
2.5
1.25
1.875
2.1875
2.03125
1.953125
1.9140625
1.93359375
1.943359375
1.9384765625
1.93603515625
1.934814453125
1.9354248046875
1.93572998046875
1.935577392578125
1.9356536865234375
1.9356918334960938
1.9357109069824219
1.9357013702392578
1.9357061386108398
1.9357085227966309
1.9357073307037354
1.935707926750183
1.935708224773407
1.935708373785019
1.935708299279213
1.93570826202631
1.9357082433998585
1.9357082340866327
1.9357082294300199
1.9357082317583263
num_guesse = 33
Answer is 1.9357082329224795
$