割り算と除算   ― 塩田研一覚書帳 ―

 割り算と除算(除法)はちょっとニュアンスが違うのではないかというお話。

 7 を 2 で割るときに、まず 2 を取り除いて 5 にします。5 から 2 を取り除いて 3。3 から 2 を取り除いて 1。 すると 1 からはもう 2 は取り除けないのでこの 1 が余りになります。 何回 2 を取り除いたかというと 3 回なので商は 3 。 これは、2 を取り除くたびに 2 を 1 ずつに分けると 3 が 2 つできると考えてもいいです。 こう考えるのは「除算」というイメージ。

 これに対して、長さ 7 の棒を真半分のところで断ち割って 3.5 にしようというのが「割り算」のイメージ。 ただし整数の長さでしか割れない棒ですと、真半分と思っても 3 と 4 というように不揃いになってしまいますので、 1 余らせて 3 ずつに揃える、という具合。

 ですから整数では、余りの出る割り算はむしろ「除算」ということになります。 そして、余りが出なければ「除算」でも「割り算」でも同じ結果になるところが面白い、と言ったら宜しいでしょうか。



 最大公約数を求める計算法に「ユークリッドの互除法」というのがあります。 a と b の最大公約数 gcd(a, b) を求めたいとき、a を b で割った余りを r とすると
gcd(a, b) = gcd(b, r)
が成り立つのでこんな計算ができる、というものです:
gcd(861, 679) = gcd(679, 182) = gcd(182, 133) = gcd(133, 49)
= gcd(49, 35) = gcd(35, 14) = gcd(14, 7) = gcd(7, 0) = 7
861 から 679 を取り除くと 182。 679 から 182 を何個か取り除くと 133。 182 から 133 を取り除くと 49   … このように互いに除算を繰り返すと最大公約数にたどり着くという方法です。

 上述のように考えると、これは「互割り算」という呼び方ではおかしくて、 「互除法」という呼び方の方がふさわしいと思います。
ユークリッドの互除法
・入力: a, b
・出力: gcd(a, b):
    
r[0] = a, r[1] = b, n = 0
while ( r[n+1] ≠ 0 ) {
    r[n+2] = ( r[n] を r[n+1] で割った余り )
    n += 1
}
abs(r[n]) を出力

戻る