開平法

開平法（かいへいほう, extraction of square root）とは、正の数の平方根の小数表示を求めていくアルゴリズムである。開平とも。平方根を求めることを開平するという。開法の一種。

数式による開平法 [編集]

開平法は筆算を用いる方法が効率的でよく使われるが、ここでは原理も含めて数式による求値法を説明する。以下は十進法表記の場合だが、他の位取り記数法でも同様な計算で求められる。ここで述べるのと基本的には同じ方法で、立方根を求める開立法や、もっと一般に n 乗根を求めることも可能である。

単に筆算による手順を知りたいだけの場合は、筆算による開平法の計算例を参照するだけでよい。

帰納的方法 [編集]

x > 0 に対し、√x が次のように表されているとする。

$\sqrt{x} =\sum_{k\le n} 10^k a_k =10^n a_n +10^{n-1} a_{n-1} +\cdots +10^2 a_2 +10a_1 +a_0 +10^{-1} a_{-1} +10^{-2} a_{-2} +\cdots$

ここで、各 a_k は 0 から 9 までの整数とする。

n は十分大きな整数で構わないが、k ≥ n で a_k = 0 が続くだけで意味がないので、n は a_n ≠ 0 すなわち 10²ⁿ ≤ x を満たす最大の整数とする。

ある整数 m があって、a_k (k > m) の値、すなわち

$p_m =\sum_{k=m+1}^n 10^{k-m-1} a_k =10^{n-m-1} a_n +10^{n-m-2} a_{n-1} +\cdots +10a_{m+2} +a_{m+1}$

は分かっているとする。

a_m の満たすべき条件は、

10^m+1p_m + 10^ma_m ≤ √x < 10^m+1p_m + 10^m(a_m + 1)

すなわち

(20p_m + a_m)a_m ≤ 10^−2mx − 100p_m² < {20p_m + (a_m + 1)}(a_m + 1)

である。これを満たす a_m を見つける。

この段階では、a_m の値を地道に探す必要があるが、a_m は 0 から 9 までの整数のいずれかなので、多くても 10 通りの値を考えればよい。

m = n のとき、p_n = 0 より

a_n² ≤ 10⁻²ⁿx

m < n のとき、

20p_ma_m ≤ (20p_m + a_m)a_m ≤ 10^−2mx − 100p_m² < {20p_m + (a_m + 1)}(a_m + 1)

p_m ≠ 0 より

$a_m \le \frac{10^{-2m} x-100{p_m}^2}{20p_m} <\left( 1+\frac{1}{2p_m} \right) (a_m +1)$

右辺の計算値により、a_m のおよその値の見当を付けることができる。

正方形ABCD の面積は 10^−2mx, 青い正方形の面積は 100p_m² で、橙色と桃色の部分の面積の和が (20p_m + a_m)a_m = r_m である。 p_m の値はすでに決まっていて、 a_m をどこまで大きく取れるのかが問題である。

これにより a_m が求まれば、次は、

p_m−1 = 10p_m + a_m

の値が分かるので、

(20p_m−1 + a_m−1)a_m−1 ≤ 10^−2(m−1)x − 100p_m−1²

を満たす最大の a_m−1 を見つければよい。

このようにして、帰納的に a_k (k ≤ n) の値が求まる。

計算の簡略化 [編集]

計算の簡略化のために、

q_m = 2p_m

y_m = 10^−2mx − 100p_m²

r_m = (10q_m + a_m)a_m

とおき、漸化式を立てて求めていくことを考える。

q_m = 10q_m+1 + 2a_m+1

y_m = 10^−2mx − 100p_m² = 100{10^−2(m+1)x − p_m²}

= 100{10^−2(m+1)x − (10p_m+1 + a_m+1)²}

= 100{10^−2(m+1)x − 100p_m+1² − (20p_m+1 + a_m+1)a_m+1}

= 100(y_m+1 − r_m+1)

a_m, r_m を求めたいが、a_m の満たすべき条件は

(10q_m + a_m)a_m ≤ y_m < {10q_m + (a_m + 1)}(a_m + 1)

である。

左辺は r_m に等しいが、a_m, r_m を探しにくくなるので、この不等式では r_m に置き換えない。

この不等式の左辺は整数なので、条件としては y_m の小数部分は無視してよい。

y_m の整数部分を z_m とすると、z_m は 100(y_m+1 − r_m+1) の整数部分に等しい。

$x=\sum_{i\le j} 10^i x_i \ (0\le x_i \le 9)$

と表されているとすると、100y_m+1 = 10^−2mx − 10000p_m+1² の整数部分は 100z_m+1 + 10x_2m+1 + x_2m である。したがって

z_m = (100z_m+1 + 10x_2m+1 + x_2m) − 100r_m+1

= 100(z_m+1 − r_m+1) + 10x_2m+1 + x_2m

が成り立つ。

a_m を求めるには、y_m を z_m に代えた不等式

(10q_m + a_m)a_m ≤ z_m < {10q_m + (a_m + 1)}(a_m + 1)

で考えればよい。これから

r_m = (10q_m + a_m)a_m

が求まる。

計算例 [編集]

計算例として x = 5630738.132 の平方根を求める。ここで使う式は

$x=\sum_{i\le j} 10^i x_i$
$\sqrt{x} =\sum_{k\le n} 10^k a_k$
q_m = 10q_m+1 + 2a_m+1
z_m = 100(z_m+1 − r_m+1) + 10x_2m+1 + x_2m
(10q_m + a_m)a_m ≤ z_m < {10q_m + (a_m + 1)}(a_m + 1)
r_m = (10q_m + a_m)a_m

初期値として、

x₆ = 5, x₅ = 6, x₄ = 3, x₃ = 0, x₂ = 7, x₁ = 3, x₀ = 8, x₋₁ = 1, x₋₂ = 3, x₋₃ = 2, これら以外の x_j の値は全て 0
10⁶ ≤ x < 10⁸ より、a_n ≠ 0 を満たす最大の n は n = 3
k > 3 のとき a_k = 0
q₃ = 0
y₄ = 0 より z₄ = 0

$\sqrt{x} =\sum_{k\le 3} 10^k a_k =10^3 a_3 +10^2 a_2 +10a_1 +a_0 +10^{-1} a_{-1} +10^{-2} a_{-2} +\cdots$

の各位 a_k (k ≤ 3) を求めていく。

初期値より、q₃ = 0, z₃ = 10x₇ + x₆ = 5

a₃² ≤ z₃ < (a₃ + 1)²

を満たす a₃ を探すと、a₃ = 2 が見つかる。

r₃ = (10q₃ + a₃)a₃ = 4

q₂ = 2a₃ = 4

z₂ = 100(z₃ − r₃) + 10x₅ + x₄ = 163

(10q₂ + a₂)a₂ ≤ z₂ < {10q₂ + (a₂ + 1)}(a₂ + 1)

を満たす a₂ を探すと、a₂ = 3 が見つかる。

r₂ = (10q₂ + a₂)a₂ = 129

q₁ = 10q₂ + 2a₂ = 46

z₁ = 100(z₂ − r₂) + 10x₃ + x₂ = 3407

(10q₁ + a₁)a₁ ≤ z₁ < {10q₁ + (a₁ + 1)}(a₁ + 1)

を満たす a₁ を探すと、a₁ = 7 が見つかる。

同様の計算を繰り返すと、各項の値は次の表のようになる。

m	q_m	z_m	a_m	r_m
3	0	5	2	4
2	4	163	3	129
1	46	3407	7	3269
0	474	13838	2	9484
−1	4744	427041	9	435413
−2	47458	474581	1	837220
−3	474582	33220789	7	36263900
−4	4745834	284750076	6	304311100
−5	47458352	1898334096	4	1956102400
︙	︙	︙	︙	︙

a_m の列から

√5630738.132 = 2372.91764…

である。

筆算による開平法 [編集]

開平法は、筆算を用いるとさらに簡単に計算できる。

筆算を用いた略記 [編集]

r_m と q_m−1 の式を比べると、式の形が似ていることが分かる。

r_m = (10q_m + a_m)a_m
q_m−1 = 10q_m + 2a_m = (10q_m + a_m) + a_m

r_m と q_m−1 は 10q_m + a_m と a_m のそれぞれかけ算と足し算である。

例えば、q₋₁ = 4744, a₋₁ = 9 ならば、

47449	47449
× 9	+ 9
r₋₁ = 427041	q₋₂ = 47458

と計算できる。

この2つの筆算を1つにまとめて

47449
9
r₋₁ = 427041 q₋₂ = 47458

と書き、r₋₁ の値は、z₋₂ の計算に用いるので他の所へ書く。

さらに、q_m−1 は q_m を左に1桁ずらして 2a_m を加えた値である。

例えば q₃ = 0, a₃ = 2, a₂ = 3, a₁ = 7, a₀ = 2 ならば、

2
2	←a₃ を縦に2つ並べる
43
3	←a₂ を右端に縦に2つ並べる
467
7	←a₁ を右端に縦に2つ並べる
4742
2	←a₀ を右端に縦に2つ並べる
4744

このように、a_m を縦2つに並べ足し算を行う作業を一連の筆算として繰り返すことで、記述を簡略化できる。

計算例 [編集]

本節では、先述の漸化式を踏まえて筆算による開平法の説明をするが、筆算の手順を知るだけであれば漸化式による説明を飛ばしても差し支えなく、これまでの節を読む必要もない。

計算例として x = 5630738.132 の平方根を求める。

まず、x の値を書き、小数点から2桁ずつに区切る。

√5 63 07 38. 13 2

分けて得られた2桁（1桁）の数をブロックと呼ぶことにする。

これは、漸化式

z_m = 100(z_m+1 − r_m+1) + 10x_2m+1 + x_2m

の最後の2項を末位に付加しやすくするために分けている。

2乗しても（左端のブロックの）5 を超えない最大の整数を探すと 2 であるので、他の所に 2 を縦に2つ並べて書く。それらを足し算の筆算として計算し、その下に計算結果の 4 を書く。この筆算を、足し算ではなくかけ算とした場合の計算結果（この場合は足し算と同じ 4）を 5 の下に書く。引き算の筆算を行い、計算結果の 1 をその下に書く。

2	2
√5 63 07 38. 13 2	2←かけ算が5以下の最大整数
4←右の筆算のかけ算の計算結果	4←足し算の計算結果
1←引き算の計算結果

z₃ = 5 で、それを基に a₃ = 2 を探した。それから r₃ = 4 を計算し、左側の筆算に書き、引き算を行った。さらに q₂ = 4 を計算し、右側の筆算に記述した。

次のブロックを下ろし、右の筆算の右端の縦2つに等しい数を書くとき、かけ算が 163 を超えない最大の数を探すと 3 である。63 のブロックの上に 3 と書き、右の筆算に 3 を縦に2つ並べる。さらに、右の筆算のかけ算と足し算の結果を、左右の筆算に書き加え、左の筆算では引き算を行う。

2 3	2
√5 63 07 38. 13 2	2
4 ↓ 次のブロックを下ろす	43
1 63	3←かけ算が163以下の最大整数
1 29←右の筆算のかけ算の計算結果	46←足し算の計算結果
34←引き算の計算結果

z₂ = 163 で、それを基に a₂ = 3 を探した。それから r₂ = 129 を計算し、左側の筆算に書き、引き算を行った。さらに q₁ = 46 を計算し、右側の筆算に記述した。

同様の計算を繰り返すと、

2 3 7 2. 9 1 7 6 4	2
√5 63 07 38. 13 20 00 00 00	2
4	43
1 63	3
1 29	467
34 07	7
32 69	4742
1 38 38	2
94 84	47449
43 54 13	9
42 70 41	474581
83 72 20	1
47 45 81	4745827
36 26 39 00	7
33 22 07 89	47458346
3 04 31 11 00	6
2 84 75 00 76	474583524
19 56 10 24 00	4
18 98 33 40 96	474583528
57 76 83 04