開平法
開平法（かいへいほう、extraction of square root）とは、正の数の平方根の小数表示を求めていくアルゴリズムである。開平や開平算、開平計算とも。平方根を求めることを開平するという。開法の一種。
Contents
開平法の原理
与えられた正の数の正の平方根の小数表示を求めるために、ここではまず漸化式を立てて、一般的な求値法を求める。そして、求値の明確化のために、開平法と呼ばれる筆算の原理を導出する。以下は十進法表示の場合だが、他の位取り記数法でも同様な計算で求められる。ここで述べるのと基本的には同じ方法で、立方根を求める開立法や、もっと一般に n 乗根を求めることも可能である。
問題の定式化
与えられた √x (x > 0) に対し、10k の位 ak (k ≤ n) を求める：
- [math]\begin{align} \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 \end{align}[/math]
x の首位を an とする。つまり、n は √x < 10k+1 を満たす最小の k とする。また便宜上 ak = 0 (k > n) とする。
√x の 10m の位より上（かみ）の位 pm は分かっているとし、10m の位 am を求めるとする。すなわち
- [math]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}[/math]
とおく。
am は 10m+1pm + 10mam ≤ √x を満たす最大の am、すなわち
- (20pm + am)am ≤ 10−2mx − 100pm2 … (1)
を満たす最大の am である。これを見つける。
- am の値は 0 から 9 までの 10 通りなので、順に試していけば am は求まる。
- m = n のとき、pn = 0 より
- an2 ≤ 10−2nx
- m < n のとき、
- 20pmam ≤ (20pm + am)am ≤ 10−2mx − 100pm2
pm ≠ 0 より
- [math]a_m \le \frac{10^{-2m} x-100{p_m}^2}{20p_m}[/math]
- 右辺の計算値により、am の値の見当を付けることができる。
これにより am が求まれば、
- pm−1 = 10pm + am
の値が分かるから、
- (20pm−1 + am−1)am−1 ≤ 10−2(m−1)x − 100pm−12
を満たす最大の am−1 を見つければよい。
このようにして、帰納的に ak (k ≤ n) の値が求まる。
漸化式の簡略化
不等式(1) を簡略化する。「20」を基数 10 と合わせるため 10 × 2 とする。そのため
- qm = 2pm
- ym = 10−2mx − 100pm2
とおくと、不等式(1) は
- (10qm + am)am ≤ ym … (1')
である。
- qm = 2pm
- = 2(10pm+1 + am+1)
- = 10qm+1 + 2am+1 … (2)
(1') を満たす最大の am を求めるために、ym の整数部分 zm を、zm+1 から求める。
rm = (10qm + am)am とおくと、
- ym = 10−2mx − 100pm2
- = 100{10−2(m+1)x − (10pm+1 + am+1)2}
- = 100{10−2(m+1)x − 100pm+12} − 100(20pm+1 + am+1)am+1
- = 100ym+1 − 100rm+1
100ym+1 = 10−2mx − 10000pm+12 の整数部分は、x の 10i の位を xi とすると、100zm+1 + 10x2m+1 + x2m に等しい。したがって、
- zm = (100zm+1 + 10x2m+1 + x2m) − 100rm+1
- = 100(zm+1 − rm+1) + 10x2m+1 + x2m … (3)
(2), (3) から、(1') を満たす最大の am を求めていく。
筆算による効率化
pm から不等式(1') を満たす最大の am を求めていくには、筆算による帰納的計算が明確である。
| am | ||
| √ … … x2m+1 x2m | ||
| zm+1 | ||
| rm+1 ↓ ↓ | ||
| qm am zm+1 − rm+1 x2m+1 x2m | ||
| am (10qm + am)am | ||
| qm−1 zm − rm |
- zm = 100(zm+1 − rm+1) + 10x2m+1 + x2m から rm = (10qm + am)am を引き、負とならない最大の am を求める。（主算）
- 次の am−1 を求めるために、qm−1 = (10qm + am) + am を求めておく。（副算）
具体的な計算方法
例として、ここでは x = 5630738.132 の正の平方根 √x の小数表示を求める。初期値は、
- x6 = 5, x5 = 6, x4 = 3, x3 = 0, x2 = 7, x1 = 3, x0 = 8, x−1 = 1, x−2 = 3, x−3 = 2, xi = 0 (i < −3)
漸化式による求値
- 106 ≤ x < 108 より、n = 3
まずは a3 を求める。
- z4 = 0
- r4 = 0
- p3 = 0 より q3 = 0
- z3 = 100(z4 − r4) + 10x7 + x6 = 100 × (0 − 0) + 5 = 5
- r3 = (10q3 + a3)a3 = a32
- a32 ≤ 5 を満たす最大の a3 は、a3 = 2 である。
次に、a2 を求める。
- q2 = (10q3 + a3) + a3 = 2 + 2 = 4
- z2 = 100(z3 − r3) + 10x5 + x4 = 100 × (5 − 4) + 63 = 163
- r2 = (10q2 + a2)a2 = (40 + a2)a2
- (40 + a2)a2 ≤ 163 を満たす最大の a2 は、a2 = 3 である。
a1 を求める。
- q1 = (10q2 + a2) + a2 = 43 + 3 = 46
- z1 = 100(z2 − r2) + 10x3 + x2 = 100 × (163 − 129) + 7 = 3407
- r1 = (10q1 + a1)a1 = (460 + a1)a1
- (460 + a1)a1 ≤ 3407 を満たす最大の a1 は、a1 = 7 である。
同様の計算を繰り返すと、各項の値は次の表のようになる。
| m | 10x2m+1 + x2m | zm | qm | rm | am |
|---|---|---|---|---|---|
| 3 | 05 | 5 | 0 | 4 | 2 |
| 2 | 63 | 163 | 4 | 4 | 3 |
| 1 | 07 | 3407 | 46 | 129 | 7 |
| 0 | 38 | 13838 | 474 | 3269 | 2 |
| −1 | 13 | 435413 | 4744 | 9484 | 9 |
| −2 | 20 | 837220 | 47458 | 427041 | 1 |
| −3 | 00 | 36263900 | 474582 | 474581 | 7 |
| −4 | 00 | 304311100 | 4745834 | 284750076 | 6 |
| −5 | 00 | 1956102400 | 47458352 | 1898334096 | 4 |
| ︙ | ︙ | ︙ | ︙ | ︙ | ︙ |
am の値から
- √5630738.132 = 2372.91764…
である。
筆算による求値
am の値は、先述の筆算による方法（開平法）によりさらに簡単に計算できる。
- 本節は、これまでに登場した漸化式の原理により筆算の手順を説明するが、筆算の手順だけを知りたいのであれば、漸化式による説明の箇所を読み飛ばしても差し支えない
x = 5630738.132 の正の平方根 √x の小数表示を求める。
まず、x の値を、小数点から2桁ずつ「ブロック」に分けて書く。
| √5 63 07 38. 13 2 |
- 各ブロックは、zm = 100(zm+1 − rm+1) + 10x2m+1 + x2m の下線部に該当する。
左側に縦2つ等しい値を書き、積が左端のブロック (5) を超えない最大の値 (2) を見つける。ブロック (5) の上に見つけた値 (2) を書く。左の筆算を立て、下に和の計算結果 (4) を書く。ブロック (5) の下に、左の筆算の、和でなく積の計算結果（この場合は和と同じ 4）を書く。筆算を立て、差の計算結果 (1) をその下に書く。
| 2 | ||
| 2 √5 63 07 38. 13 2 | ||
| 積が5以下の最大値→2 4←左の筆算の積 | ||
| 和→4 1←差 |
- z4 = r4 = 0 より z3 = 10x8 + x7 = 5。q3 = 0 より、(0 + a3)a3 ≤ 5 を満たす最大の a3 は a3 = 2。この時 r3 = 2 × 2 = 4。次の計算のために、z3 − r3 = 5 − 4 = 1, q2 = 2 + 2 = 4 を計算しておく。
差の計算結果 (1) の右隣りに、上のブロック (63) を下ろす。左の筆算の末位に縦2つ等しい値を書き、積が下ろしてできた数 (163) を超えない最大の値 (3) を見つける。ブロック (63) の上に見つけた値 (3) を書く。左の筆算を立て、下に和の計算結果 (46) を書く。下ろしてできた数 (163) の下に、左の筆算の積の計算結果 (129) を書く。筆算を立て、差の計算結果 (34) をその下に書く。
| 2 3 | ||
| 2 √5 63 07 38. 13 2 | ||
| 2 4 ↓ ブロックを下ろす | ||
| 43 1 63 | ||
| 積が163以下の最大値→ 3 1 29←左の筆算の積 | ||
| 和→46 34←差 |
- z2 = 100(z3 − r3) + 10x5 + x4 = 163。(40 + a2)a2 ≤ 163 を満たす最大の a2 は a2 = 3。この時 r2 = 43 × 3 = 129。次の計算のために、z2 − r2 = 163 − 129 = 34, q1 = 43 + 3 = 46 を計算しておく。
同様の計算を（m = −5 まで）行うと、次のようになる。
| 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 |
これより
- √5630738.132 = 2372.91764…
である。
検算してみると、
- 2372.917642 = 5630738.1262231696
- 2372.917652 = 5630738.1736815225
となり
- 2372.91764 < √5630738.132 < 2372.91765
が確かに成り立つ。
珠算による開平法
珠算による開平法として次の方法がある。
- 倍根法
- 半九九法
根の定位
根の定位の仕方は次のようになる。
- 平方が整数のとき：平方の一の位から左へ2桁ずつ区分して、その区分できた回数が、根の桁数となる。
- 平方が帯小数のとき：平方の一の位から左へ2桁ずつ区分して、その区分できた回数が、根の整数の桁数となる。
- 平方が小数のとき：平方の 0 を2桁ずつ区分して、その区分できた回数が、根の小数点以下の 0 の桁数となる。
倍根法
例：√4225 = 65
半九九法
例：√4225 = 65