整数の平方根を切り捨てで求める
四捨五入の前に、まずは切り捨てで求める方法を復習する。
非負の「ある数」について
- ある数が求めたい平方根より大きいならば、その数の2乗はもとの数より大きい
- ある数が求めたい平方根ならば、その数の2乗はもとの数
- ある数が求めたい平方根未満ならば、その数の2乗はもとの数未満
という性質を利用し、めぐる式二分探索で求めることができる。
求めたい平方根の小数点以下を切り捨てた値は、求めたい平方根以下の最大の整数である。
よって、2乗してもとの数以下になる最大の整数を求めればよい。
2の平方根は約1.41であり、平方根の増え方はもとの数の増え方より遅いので、直感的に2以上の整数の平方根の小数点以下を切り捨てた数はもとの数未満であることがわかる。
def sqrt_floor(n):
if n <= 0:
return 0
if n == 1:
return 1
le = 0 # 平方根以下の数
greater = n # 平方根より大きい数
while le + 1 < greater:
m = le + (greater - le) // 2
if m * m <= n:
le = m
else:
greater = m
return le
動作を試してみる。
for i in range(20):
print("%2d %d" % (i, sqrt_floor(i)))
以下の実行結果が得られた。
0 0
1 1
2 1
3 1
4 2
5 2
6 2
7 2
8 2
9 3
10 3
11 3
12 3
13 3
14 3
15 3
16 4
17 4
18 4
19 4
うまくいっていそうである。
整数の平方根を四捨五入で求める
切り捨てでの求め方を応用して、整数の平方根の小数点以下を四捨五入した値を求める方法を考える。
求める値が $k$ のとき、もとの数の平方根は $k-0.5$ 以上 $(k+1)-0.5$ 未満である。
したがって、もとの数を $n$ とすると、${(k-0.5)}^2 \leq n$ かつ ${((k+1)-0.5)}^2 > n$ となる非負整数 $k$ を求めればよいことがわかる。
${(k-0.5)}^2 \leq n$ の両辺を4倍して変形すると、${(2k-1)}^2 \leq 4n$ となり、整数のみで計算できるようになる。
2の平方根は約1.41なので四捨五入すると1、3の平方根は約1.73なので四捨五入すると2、4の平方根は2である。
平方根の増え方はもとの数の増え方より遅いので、直感的に2以上の整数の平方根の小数点以下を四捨五入した数はもとの数未満であることがわかる。
def sqrt_round(n):
if n <= 0:
return 0
if n == 1:
return 1
le = 0 # 平方根の四捨五入以下の数
greater = n # 平方根の四捨五入より大きい数
while le + 1 < greater:
m = le + (greater - le) // 2
if (2 * m - 1) * (2 * m - 1) <= 4 * n:
le = m
else:
greater = m
return le
動作を試してみる。
import math
for i in range(30):
print("%2d %6.3f %d" % (i, math.sqrt(i), sqrt_round(i)))
以下の実行結果が得られた。
0 0.000 0
1 1.000 1
2 1.414 1
3 1.732 2
4 2.000 2
5 2.236 2
6 2.449 2
7 2.646 3
8 2.828 3
9 3.000 3
10 3.162 3
11 3.317 3
12 3.464 3
13 3.606 4
14 3.742 4
15 3.873 4
16 4.000 4
17 4.123 4
18 4.243 4
19 4.359 4
20 4.472 4
21 4.583 5
22 4.690 5
23 4.796 5
24 4.899 5
25 5.000 5
26 5.099 5
27 5.196 5
28 5.292 5
29 5.385 5
うまくいっていそうである。