SwissMicros DM42 (HP-42Sの互換機)で、有名な「
ユークリッドの互除法」(Euclidean algorithm)を実装してみる。
ユークリッドの互除法について
ユークリッドの互除法は2つの自然数xとyがあった時に、その
最大公約数 (xとyに共通する最も大きな約数、割り切る数)を求める手順だ。面倒なので、最大公約数を以後GCD (greatest common divisor)と書く。
古代ギリシアの数学者ユークリッド (Euclid)によって記された『原論』(Elements)の中に書かれており、紀元前300年ごろには存在していたというから凄い。
このアルゴリズムでは、以下のように計算を進める:
1. xをyで割った余りをrとする
2. rが0でなければ、x←y、y←rとして1.に戻る
3. rが0ならば、その時のyが元々のxおよびyのGCDである
電卓を叩いて確かめてみる
例として、DM42を使い手動で1785と374のGCDを求めてみる。
使うDM42の機能について:
* MOD → y÷xの余りを計算してxに積む
* LASTX → 直前までxに入っていた内容を保持するL-registerの内容をxに積む
* x≶y → X-registerとY-registerの内容を交換する
1. 1785
2. ENTER
3. 374
4. MOD ⇒ 289 ※余りは0ではない
5. LASTX ⇒ 374 ※直前のxの内容を呼び出した
6. x≶y ⇒ 289 ※xとyの内容を交換
7. MOD ⇒ 85 ※余りは0ではない
8. LASTX ⇒ 289
9. x≶y ⇒ 85
10. MOD ⇒ 34 ※余りは0ではない
11. LASTX ⇒ 85
12. x≶y ⇒ 34
13. MOD ⇒ 17 ※余りは0ではない
14. LASTX ⇒ 34
15. x≶y ⇒ 17
16. MOD ⇒ 0 ※余りが0になった！
17. LASTX ⇒ 17 ※これが1785と374のGCD
MODの結果が0になるまで、ひたすらLASTXしてx≶yしてMODする、を繰り返すだけでGCDが計算できるとわかる。このような単純作業はもちろん機械にやらせるべきだ。
DM42でprogramming
DM42 (HP-42S)に限らず、RPN方式の関数電卓では基本的にキー入力の羅列がそのままprogramになる。ただし、practicalなprogramを記述するには、LBLや条件分岐やjump命令などが必要になる。
DM42のprogramの構造は:
LBL "LABEL"
...
END (或いはRTN)
のようになっている。LBL (label)はprogram (或いはsubroutine)の名前で、様々な手順が続き、最後はRTN (return)或いはENDである。
PRGM (□＋R/S)でprogram modeに入る。
先頭の行番号はDM42が勝手につけてくれるので無視すると、こんな感じに書ける:
LBL "GCD"
LBL 02
MOD
X=0?
GTO 01
LASTX
X<>Y
GTO 02
LBL 01
LASTX
RTN
EXITでprogram modeを抜ける。
programを実行するにはXEQを押す。すると、software menuにprogramで指定したlabel (LBL)が表示されるので、GCDを選ぶ。ただし、今回のprogramはとにかく手順をそのまま書いただけなので、予めY-registerに大きい方の自然数を、X-registerに小さい方の自然数をそれぞれ積んでおく必要がある。
1. 1785 [ENTER]
2. 374
3. XEQ → GCD ⇒ 17
X-registerには17が残っているはずだ。
そして最小公倍数へ
ちなみに、GCDとくればLCM (least common multiple)——最小公倍数も忘れてはならない。2つの正の整数について:
GCD(x,y) LCM(x,y) = xy
という関係が成り立つと知られているので、GCDが分かっていればLCMも計算できる。
LCM(x,y) = xy / GCD(x,y)
1785と374の場合は39270である。
