開平法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

問題の定式化[編集]

x > 0 に対し、√x の 10k

の位を ak とする (kn):
\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

n は 10n

≤ √x < 10n+1

、すなわち x ≥ 102n

を満たす最大の整数とする。また便宜上 ak = 0 (k > n) とする。

x の 10m

の位より上(かみ)の位、すなわち
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}

は分かっているとする。

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

am は 10m (10pm + am) ≤ √x を満たす最大の am、すなわち

(20pm + am)am ≤ 10−2m

x − 100pm2 …(1) を満たす最大の am である。これを見つける。

この段階では、am の値を地道に探す必要があるが、am は 0 から 9 までの整数のいずれかなので、多くても 10 通りの値を考えればよい。
m = n のとき、pn = 0 より
an2
≤ 10−2n

x

m < n のとき、
20pmam ≤ (20pm + am)am ≤ 10−2m

x − 100pm2

pm ≠ 0 より

a_m \le \frac{10^{-2m} x-100{p_m}^2}{20p_m}
右辺の計算値により、am の値の見当を付けることができる。

これにより am が求まれば、

pm−1 = 10pm + am

の値が分かるから、

(20pm−1 + am−1)am−1 ≤ 10−2(m−1)

x − 100pm−12

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

このようにして、帰納的に ak (kn) の値が求まる。

漸化式による求値[編集]

不等式(1) を簡略化する。「20」は基数 10 と合わせるため 10 × 2 と見た方がよい。そこで、

qm = 2pm
rm = (10qm + am)am
ym = 10−2m

x − 100pm2

とおくと、(1) は

(10qm + am)amym…(1')

と表される(am, rm を探しにくくなるので、ここでは左辺は rm に置き換えない)。

qm = 2pm
     = 2(10pm+1 + am+1)
     = 10qm+1 + 2am+1…(2)

(1') を満たす最大の am を求めるために、ym の整数部分 zm を求める。

ym = 10−2m

x − 100pm2

     = 100{10−2(m+1)

x − (10pm+1 + am+1)2 }

     = 100{10−2(m+1)

x − 100pm+12

− (20pm+1 + am+1)am+1}
     = 100(ym+1rm+1)
     = 100ym+1 − 100rm+1

100ym+1 = 10−2m x − 10000pm+12

の整数部分は、x の 10i
の位を xi とすると、100zm+1 + 10x2m+1 + x2m に等しい。したがって、
zm = (100zm+1 + 10x2m+1 + x2m) − 100rm+1
     = 100(zm+1rm+1) + 10x2m+1 + x2m…(3)

(1'), (2), (3) から rm = (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
  • p3 = 0 より q3 = 0
  • r4 = 0
  • y4 = 0 より z4 = 0

x の 10k

の位 ak (k ≤ 3) を求めていく。
z3 = 100 × (0 − 0) + 5 = 5
q3 = 0
(0 + a3)a3 ≤ 5

を満たす最大の a3 は、a3 = 2 である。

r3 = 2 × 2 = 4
z2 = 100 × (5 − 4) + 63 = 163
q2 = 2 × 2 = 4
(40 + a2)a2 ≤ 163

を満たす最大の a2 は、a2 = 3 である。

r2 = 43 × 3 = 129
z1 = 100 × (163 − 129) + 7 = 3407
q1 = 40 + 2 × 3 = 46
(460 + a1)a1 ≤ 3407

を満たす最大の a1 は、a1 = 7 である。

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

m qm am zm rm 10x2m−1 + x2m−2
4 0 0 0 0 05
3 0 2 5 4 63
2 4 3 163 129 07
1 46 7 3407 3269 38
0 474 2 13838 9484 13
−1 4744 9 435413 427041 20
−2 47458 1 837220 474581 00
−3 474582 7 36263900 33220789 00
−4 4745834 6 304311100 284750076 00
−5 47458352 4 1956102400 1898334096 00

am の値から

5630738.132 = 2372.91764…

である。

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

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

筆算による効率化[編集]

rmqm−1 は、次のように式の形が似ていることが分かる。

  • rm = (10qm + am)am
  • qm−1 = 10qm + 2am = (10qm + am) + am

rm, qm−1 は 10qm + amam のそれぞれ積と和である。

例えば、m = 2 ならば、

43    43
×    3    +    3
r2 = 129    q1 = 46

と計算できる。

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

43
                          3
r2 = 129    q1 = 46

と書ける。r2 の値は z2 の値から引き、q1 の値は次の z1, r1 の計算に用いるため他の場所へ書く。

z2 = 163            43
r2 = 129              3
34    q1 = 46

100(r2z2) = 3400 に 10x3 + x2 = 7 を加えると z1 に等しい。10q1 = 460 に a1 = 7 を加える。

z2 = 163        43  
r2 = 129          3  
z1 = 3407    467

以降、同様に筆算を繰り返し立てることができる。

163            43
129              3
  3407        467
  3269            7
    13838    4742
      9484          2
      4354    4744

qm−1 の筆算(右)が右に1桁ずつ進むのに対して、rm の筆算(左)が右に2桁ずつ進むから、qm−1 の筆算は左に書いた方がよいことが分かる。

筆算による計算手順[編集]

本節は、これまでの漸化式による原理を基に筆算の手順を説明するが、筆算の手順だけを知りたいのであれば、漸化式による説明の箇所を読み飛ばしても差し支えない。

x = 5630738.132 の正の平方根 √x の小数表示を求める。

まず、x の値を、小数点から2桁ずつ「ブロック」に分けて書く。

5  63  07  38. 13  2
各ブロックは、zm = 100(zm+1rm+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←差
q3 = 0。r4 = y4 = 0 より z3 = 5。(0 + a3)a3 ≤ 5 を満たす a3 の最大値は a3 = 2。この時 r3 = 2 × 2 = 4。次の計算のために、z3r3 = 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(z3r3) + 10x5 + x4 = 163。(40 + a2)a2 ≤ 163 を満たす a2 の最大値は a2 = 3。この時 r2 = 43 × 3 = 129。次の計算のために、z2r2 = 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

が確かに成り立つ。

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

珠算による開平法として次の方法がある。

  • 倍根法
  • 半九九法

根の定位[編集]

根の定位の仕方は次のようになる。

  • 平方が整数のとき:平方の1の位から左へ2桁ずつ区分して、その区分できた回数が、根の桁数となる。
  • 平方が帯小数のとき:平方の1の位から左へ2桁ずつ区分して、その区分できた回数が、根の整数の桁数となる。
  • 平方が小数のとき:平方の小数点以下の0を2桁ずつ区分して、その区分できた回数が、根の小数点以下の0の桁数となる。

倍根法[編集]

例: √4225 = 65

Soroban 4 c.svg Soroban 2.svg Soroban 2.svg Soroban 5 cc.svg
平方の1の位から左へ2桁ずつ区分して、根の桁数が2桁であることを調べる。(根の定位による。)
Soroban 6.svg Soroban 0.svg Soroban 4 c.svg Soroban 2.svg Soroban 2.svg Soroban 5 cc.svg
最後の区分された数42に含まれている平方根6を求めて、初根6を置き、初根6の2乗 (62
= 36) を42から引く。
Soroban 1 c.svg Soroban 2.svg Soroban 0.svg Soroban 0 cc.svg Soroban 6.svg Soroban 0.svg Soroban 0 c.svg Soroban 6.svg Soroban 2.svg Soroban 5 cc.svg
初根6の2倍の12を、左に置き、その12で残りの平方を割って、次根5を初根の隣りに置く。
Soroban 1 c.svg Soroban 2.svg Soroban 0.svg Soroban 0 cc.svg Soroban 6.svg Soroban 5.svg Soroban 0 c.svg Soroban 0.svg Soroban 2.svg Soroban 5 cc.svg
次根5の2乗 (52
= 25) を引く。
Soroban 6.svg Soroban 5.svg Soroban 0 c.svg Soroban 0.svg Soroban 0.svg Soroban 0 cc.svg
平方根は65である。

半九九法[編集]

例: √4225 = 65

Soroban 4 c.svg Soroban 2.svg Soroban 2.svg Soroban 5 cc.svg
平方の1の位から左へ2桁ずつ区分して、根の桁数が2桁であることを調べる。(根の定位による。)
Soroban 6 cc.svg Soroban 0.svg Soroban 0.svg Soroban 4 c.svg Soroban 2.svg Soroban 2.svg Soroban 5 cc.svg
最後の区分された数42に含まれている平方根6を求めて、初根6を置き、初根6の2乗 (62
= 36) を42から引く。
Soroban 6 cc.svg Soroban 0.svg Soroban 0.svg Soroban 0 c.svg Soroban 6.svg Soroban 2.svg Soroban 5 cc.svg
残りの平方625を2で割る。(初根の2乗を引いたあと、いつも残りの平方を2で割る。)
Soroban 6.svg Soroban 0.svg Soroban 3 c.svg Soroban 1.svg Soroban 2.svg Soroban 5 cc.svg
2で割った平方の残りを、初根6で割って次根5を求める。
Soroban 6.svg Soroban 5.svg Soroban 0 c.svg Soroban 1.svg Soroban 2.svg Soroban 5 cc.svg
次根5の半九九12.5を引く。
Soroban 6.svg Soroban 5 cc.svg
平方根は65である。

関連項目[編集]