ユークリッド互除法

ま、最大公約数を出す計算です。知ってる人にはどうってことない話なんでしょうが、この計算のアルゴリズムのForth版が、あまりに簡単過ぎて鼻水が垂れそうになったので、一応、紹介しとこうかなとおもいました。理屈を説明する方がずっと面倒なので、まずコードを書いときます。二つの数値の最大公約数を得るワード"GCM"の定義です。

: GCM  ( n1 n2 -- gcm )  BEGIN tuck mod dup NUNTIL drop  ;

おしまい。どうぢゃ、われぇ、どっからでも、かかってこんかい！(何弁？ (||_ _ ) ええと、内容は6つのワードでできています。単純ですねえ。

コードの動作から説明しますと、BEGIN-NUNTILループを使っています。これはBEGIN-UNTILループと対になるもので、"NUNTIL"のところで、スタックの一番上の値を消費して、それが"0"(FALSE)ならループを抜け、そうでないなら"BEGIN"の直後に戻ってもう一回コードを実行します。

"tuck"はスタック操作ワードで、スタックの一番上の値をコピーした上で、上から三番目の位置にそれを押し込みます。つまり、

TUCK ( x1 x2 -- x2 x1 x2 )

ということですね。

次の"mod"は、スタックの値の二つを取って、割り算の余りを残します。つまり、

MOD ( n1 n2 -- u )  \ uはn1をn2で割ったときの余り

ということです。

上の余りが0になるまで同じことを繰り返します。"NUNTIL"がスタック値を消費するので、それように"dup"で余りの値をもうひとつ複製しておきます。そして、0になったらループを抜けます。残っている0を"drop"で落として終わりです。手順から考えて、残る値は、余りが0になる一つ手前の余りということがわかります。

ユークリッド互除法

では、しょうがないので、ユークリッド互除法について、それが何で最大公約数になるのか説明します。正確なことを知りたい方は初等数論の教科書でもご覧下さい。
計算の仕方は、まあ、まさに上のコードと同じことをするわけですが、数式風に書いてみます。aとbに計算を適用するとして、a > bと仮定しましょう。
上のコードでは入力値の大小を問題にしていませんが、a < bのときには、最初の試行で順番が入れ替わります。まあ、少し考えれば簡単にわかります。
一応、どっちも正とします。すると、どんな組み合わせでも、

a = q₀×b + r₁ ここで 0 ≦ r₁ < b

と書けて、この書き方は一種類であることがわかります。数値の大小関係を考えれば直観的には明らかですね。証明略です。
で、(a,b)の組を、今度は、(b,r₁)の組に替えて、同じ式を考えます。つまり、bをr1で割った余りr2を考えるわけです。

b = q₁×r₁ + r₂ ... 0 ≦ r₂ < r₁

そして、次は(r₁,r₂)の組に... というようにこれを続けていく。

r₁ = q₂×r₂ + r₃
r₂ = q₃×r₃ + r₄
....
r_k-1 = q_k×r_k + r_k+1
.....
すると、この数式の系列はどこかで必ず、

r_n-1 = q_n×r_n ... どの数値も正

というところに行き着く。つまり、余りがどこかで0になる(いってみれば、r_n+1=0ですね、ここでは)。このとき、r_nがaとbの最大公約数になっている、というのが、ユークリッド互除法です。

ご存知の方は別として、初めてきくと「そううまくいくかよ」という感じですね。いくんです。

まず、どっかで余りが0になるという点。初めの方に書いた余り系列の関係をみると、

(b >) r₁ > r₂ > r₃ > .. > r_k-1 > r_k > ...

と、必ず減少していかなければならないことがわかります。ところが、余りには0以上の整数という縛りがありますし、最初のbは有限の数値ですから、必ずどこかで0になるはずなわけです。有理数とか実数とか稠密な数ではそうも行きませんが、整数では必ずそれがいえるのですね。

そして、r_nが最大公約数になるという点。ます、公約数であることですが、最後の式の形から、r_nはr_n-1を割り切る、つまり、r_n-1の約数であることがわかります。逆に言うと、r_n-1はr_nの倍数です。ここで一つ遡った式を考えましょう。

r_n-2 = q_n-1×r_n-1 + r_n

すると、右辺のr_n-1もr_nも、ともにr_nの倍数なわけですから、左辺のr_n-2もr_nの倍数、つまり、r_nはr_n-2の約数でもあるわけです。こういう風に、どんどん遡っていけますので、式の系列の始めの方には、a,bとも左辺であったことがあるわけで、こうして、r_nがa,bの公約数であることがわかるわけです。

次に、「最大」という点。例えば、ええと、Cがa,bの公約数だったとしますね。つまり、aもbもCの倍数と。すると、最初の式

a = q₀×b + r₁
を
a - q₀×b = r₁
と変形すれば、 r1もCの倍数でなければならないことが、丸わかりですね。左辺のaもbもCの倍数なので、左辺全体がCの倍数、ということは、それと等しい右辺r₁は当然Cの倍数でしょう。

またこれをどんどん、今度は式の系列の進行方向に続けていくと、 r_nもCの倍数でなければならないことになります。つまり、 r_nはCで割り切れなければいけないのです。だから、 r_nは最大公約数なのです。だって、 r_nはどんな公約数ででも割り切れなきゃいけないんですよ。だから、最大公約数ででも割り切れなきゃいけないはずです。 r_nが最大公約数より小さいってなら、自分より大きい数じゃあ割り切れるはずないですね。最大公約数が r_nより小さいなら、 r_nだって公約数なんだから最大といえないじゃないですか。だから両者は等しいんです。

これで、最大公約数なるものの存在まで証明しちゃったわけですね。

今回は初等数学教室みたいだったですね。むむむ。

オマケ

おまけですが、任意の個数(無限はダメよ)の組の最大公約数を計算するコードも書いておきましょう。順々に適用していくだけですから、単純です。最大公約数を取りたい数値を並べ、最後(トップスタック)に項数を表す数値を置く、という形式にしときました。

: mGCM  ( n1 n2 ... nk k -- gcm )
 1- FOR BEGIN tuck mod dup NUNTIL drop NEXT  ;

ま、これだけなんですがね。

---

トップページへ
< 目次へ

---