MOD計算

先日,MODを計算する機会があった. MODとは合同算術,すなわちModular Arithmeticの略で,剰余を持つ除法のこと. この場合,余り計算を指す. 例えば5mod2は,5/2の結果が商2余1であるので答えは1. この y mod x なる計算を行う必要があった. yの値が16807と大きな数であったのでHP15Cで計算できると便利だと思ったが,この計算機にはmodキーが無い. そこで,modをプログラムすることとした. y mod x の計算方法は次の通りである.

$$ y\ mod\ x = y - x\times \lfloor \frac{y}{x} \rfloor$$

1. まずy/xを計算する. これをaとする. ここでaは実数である.
2. aの小数点以下を切り捨てる. ここでaは整数となる.
3. a*xを計算し,yからa*xを減ずる. これをrとする.
4. rが y mod x の解となる.

$\lfloor x \rfloor$は床函数で,$x$が少数を含む実数ならば小数を文字通り床へと下ろす. 整数を1段づつ上がる階段と捉えると,段の間に位置する実数をその段上へと下ろすイメージである. 切り捨てというと,小数点以下n桁目より切り捨てることを意味するが,この床函数は小数点以下1桁目を切り捨てることを意味するので,床函数は切り捨ての特殊な場合と言えよう. 例えば$\lfloor \pi \rfloor = 3$という具合である.

レジスタを用いたMOD計算

さて,この計算をプログラムするにあたり,まず思いついた方法はレジスタを2つ用いるやりかたであった. 以下に 7 mod 2 での15Cのスタック遷移とプログラム例を載せる.

(  x  y z t) [キー]        説明
(  2  7 0 0) [P/R, LBL A] ラベルAとしてプログラム開始.
(  2  7 0 0) [CLEAR REG]  全レジスタクリア.
(  2  7 0 0) [STO 1]      スタック先頭をレジスタ1にコピー.
(  7  2 0 0) [X≷Y]        スタックXとYの内容を交換.
(  7  2 0 0) [STO 2]      スタック先頭をレジスタ2にコピー.
(  2  7 0 0) [X≷Y]        スタックXとYの内容を交換.
(3.5  0 0 0) [DIV]        除算÷
(  3  0 0 0) [INT]        整数へ変換.
(  2  3 0 0) [RCL 1]      レジスタ1の内容をスタック先頭へ復帰.
(  6  0 0 0) [MUL]        乗算×
( -6  0 0 0) [CHS]        符号を変える.
(  7 -6 0 0) [RCL 2]      レジスタ2の内容をスタック先頭へ復帰.
(  1  0 0 0) [ADD]        加算＋
(  1  0 0 0) [CLEAR REG]  全レジスタクリア.
(  1  0 0 0) [RTN]        リターン.
(  1  0 0 0) [P/R]        プログラム終了.

プログラムを試す. 映像30秒~のように上手く計算出来た.

スタックのみを用いたMOD計算

しかし,上手く行くと欲が出る. 15Cのスタックは4つ有るので,レジスタを用いずにスタックだけで計算出来る筈だからだ. スタック内を少しこね回すだけで,レジスタを使うことなく余り計算を行えるようになる. 以下にそのスタック遷移とプログラム例を載せる.

(  x y z t) [キー]        説明
(  2 7 0 0) [P/R, LBL A] ラベルAとしてプログラム開始.
(  2 2 7 0) [ENTER]      入力終わり(スタック先頭をコピー).
(  2 7 0 2) [R↓]         スタック全体を下へ移動.
(  7 2 0 2) [X≷Y]        スタックXとYの内容を交換.
(  2 7 2 0) [R↑]         スタック全体を上へ移動.
(  7 2 2 0) [X≷Y]        スタックXとYの内容を交換.
(  7 7 2 2) [ENTER]      入力終わり.
(  2 7 7 2) [R↑]         スタック全体を上へ移動.
(3.5 7 2 2) [DIV]        除算÷
(  3 7 2 2) [INT]        整数へ変換.
(  2 3 7 2) [R↑]         スタック全体を上へ移動.
(  6 7 2 2) [MUL]        乗算×
( -6 7 2 2) [CHS]        符号を変える.
(  1 2 2 2) [ADD]        加算＋
(  1 2 2 2) [RTN]        リターン.
(  1 2 2 2) [P/R]        プログラム終了.

このプログラムを試すと, 計算終了後(32秒あたり),Xスタックに解である余り1が,また34秒~に見えるように他3つのスタックY,Z,T全てに y mod x 中の値xが代入された状態となる. このプログラムならレジスタを他の用途で使っていても気楽に計算出来る. 上手くプログラムすればもう少し手数を減らせるのだろうか. まぁ上手く動いているから気にしない.

439582129191023036 https://www.storange.jp/2013/07/mod.html https://www.storange.jp/2013/07/mod.html MOD計算 2013-07-30T21:17:00+09:00 https://www.storange.jp/2013/07/mod.html Hideyuki Tabata Hideyuki Tabata 200 200 72 72