Algorithm - Python - 平方根もカッコイイ(無限ループの回避、探索範囲の注意点、浮動小数点数と浮動小数点算術、連続領域の二分法、離散二分探索)

問題解決の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章(平方根もカッコイイ)、練習問題(問題1)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def bisection_search_for_square_root(x: float, epsilon: float = 0.01):
    if x < 0:
        print('Sorry, imaginary nubers are out of scope!')
        return

    num_guesses = 0
    if x < 1:
        low = x
        high = 1
    else:
        low = 0.0
        high = x
    answer = (low + high) / 2.0
    while abs(answer ** 2 - x) >= epsilon:
        print(answer)
        if answer ** 2 < x:
            low = answer
        else:
            high = answer
        answer = (low + high) / 2.0
        num_guesses += 1

    print(f'num_guesse = {num_guesses}')
    print(f'{answer} is close to square root of {x}')


if __name__ == '__main__':
    # import doctest
    # doctest.testmod()
    for epsilon in range(10):
        bisection_search_for_square_root(0.25, 10**-epsilon)

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

$ ./sample1.py
num_guesse = 0
0.625 is close to square root of 0.25
0.625
num_guesse = 1
0.4375 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
num_guesse = 4
0.5078125 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
num_guesse = 7
0.4990234375 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
0.4990234375
0.50048828125
0.499755859375
0.5001220703125
num_guesse = 11
0.49993896484375 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
0.4990234375
0.50048828125
0.499755859375
0.5001220703125
0.49993896484375
0.500030517578125
0.4999847412109375
num_guesse = 14
0.5000076293945312 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
0.4990234375
0.50048828125
0.499755859375
0.5001220703125
0.49993896484375
0.500030517578125
0.4999847412109375
0.5000076293945312
0.4999961853027344
0.5000019073486328
num_guesse = 17
0.4999990463256836 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
0.4990234375
0.50048828125
0.499755859375
0.5001220703125
0.49993896484375
0.500030517578125
0.4999847412109375
0.5000076293945312
0.4999961853027344
0.5000019073486328
0.4999990463256836
0.5000004768371582
0.4999997615814209
0.5000001192092896
num_guesse = 21
0.4999999403953552 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
0.4990234375
0.50048828125
0.499755859375
0.5001220703125
0.49993896484375
0.500030517578125
0.4999847412109375
0.5000076293945312
0.4999961853027344
0.5000019073486328
0.4999990463256836
0.5000004768371582
0.4999997615814209
0.5000001192092896
0.4999999403953552
0.5000000298023224
0.4999999850988388
num_guesse = 24
0.5000000074505806 is close to square root of 0.25
0.625
0.4375
0.53125
0.484375
0.5078125
0.49609375
0.501953125
0.4990234375
0.50048828125
0.499755859375
0.5001220703125
0.49993896484375
0.500030517578125
0.4999847412109375
0.5000076293945312
0.4999961853027344
0.5000019073486328
0.4999990463256836
0.5000004768371582
0.4999997615814209
0.5000001192092896
0.4999999403953552
0.5000000298023224
0.4999999850988388
0.5000000074505806
0.4999999962747097
0.5000000018626451
num_guesse = 27
0.4999999990686774 is close to square root of 0.25
$