SwissMicros DM42で簡単なprogramを組んでみる

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である。