## 2018年11月26日月曜日

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

コード(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:
if answer ** 2 < x:
else:
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)
```

```\$ ./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
\$
```