Divide【Turing Complete編】
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
Divideステージ
Divideステージのゴールは、除算（割り算）を実現することです。
除算では、2つの整数を割って、商（quotient）と余り（remainder）を求めます。
例えば、分数の7/2を考えてみます。2で割ると、1余ります。すなわち商が2、余りが1です。
ついでに除数（divisor）と被除数（diviend）という2つの用語を定義しておきます。除数は割る数、被除数は割られる数のです。上記の例でいえば、7/2＝7÷2であり、2が除数、7が被除数になります。
本ステージでは、入力端子を通じて最初に分子の数、次に分母の数が与えられます。最初に商、次に余りを出力できればゴールとなります。
Level Screen
Level Screenには、求めるべき分数、そして商と余りが表示されます。
Divideステージを解く
1：除算の実現方針を検討する
除算回路は複雑になるために実装するのは難しく、低価格デバイスにはほとんど見かけません。
ここではソフトウェアで解決することにします。除算アルゴリズムはいくつかありますが、ここではもっともシンプルなアルゴリズムを採用します。
被除数が除数以上であれば、被除数から除数を引くのを繰り返します。その引いた数をカウントしておき、最終的なカウント値が商、引かれて残った数が余りになります。
このアルゴリズムを擬似プログラムで表現すると、次のようになります。
quotient = 0;
while (dividend >= divisor) {
dividend = dividend - divisor;
quotient = quotient + 1;
}
※もっともシンプルな乗算アルゴリズムは次々に足していく方法でしたが、上記の除算アルゴリズムはその逆操作になります。次々に引いていくわけです。ただし、乗算結果は常に倍数ですが、除算の場合は与えられた数が割りきれるとは限らず余りの存在を考慮しなければなりません。
引き算によって除算するアルゴリズムをデジタル回路で実現することもできます。
カウンター、レジスター、減算器から構築できます。
機会があればコンテンツとして追加したいです。
『プログラム学習によるディジタル制御』P.215-216には、この種の回路とシフトレジスターを用いた回路が簡単に紹介されています。
このアルゴリズムは割る回数が多いほど計算に時間がかかりますが、本ステージのテストをパスする程度であれば十分でしょう。
2：シミュレーターの現状を把握する
左上の「Instructions」アイコンを押します。以前はInstructionsのマニュアルを表示したり、上の8ビットをON・OFFすることで対応する命令が表示されたりしましたが、本ステージからは出ません。逆に命令を自作して、それをマニュアルに追加する仕様になっています。
※後のステージで命令を再定義するので、ここではこれ以上考えずに飛ばします。
次に、Programコンポーネントの「Edit memory」アイコンを押して、アセンブリーエディターを起動します。左側に定義済みのアセンブリーコードが表示されるはずですが、何もないか、過去に定義したコードが表示されているかのどちらかでしょう。
いずれにしても気にする必要はありません。今回のプログラムは比較的単純なので、ハンドアセンブルしてマシン語でプログラムを実装することにします。
※後でコードを定義したら、別解としてコードを使ったプログラムを紹介します。
3：プログラムを設計する
今回のアルゴリズムでは使う変数は少ないため、RAMを使わずにレジストリーだけで完結できます。
LEGアーキテクチャーで使えるオペコードについては、RAMステージの攻略ページで確認してください。実際にハンドアセンブルする際には、ページを参照しながらマシン語（の10進数）を確かめていきます。
https://akademeia.info/?p=31166| No. | アドレス | 1バイト目 | 2バイト目 | 3バイト目 | 4バイト目 | 処理内容 |
|---|---|---|---|---|---|---|
| 1 | 00h | 0000 0101b（=5d） ※XOR | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | REG 3を商の計算結果（カウンター）とする。 事前にゼロクリアする。 |
| 2 | 04h | 0000 0101b（=5d） ※XOR | 0000 0100b（＝4d） ※REG 4 | 0000 0100b（＝4d） ※REG 4 | 0000 0100b（＝4d） ※REG 4 | 比較用の定数ゼロをREG 4に用意する。 ※Conditionモードの命令は即値が使えないので、定数をレジスターに保存しておく必要がある。 |
| 3 | 08h | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0111b（＝7d） ※入力端子 | 0000 0000b（＝0d） ※即値 | 0000 0001b（＝1d） ※REG 1 | 入力端子からくるバイトデータをREG 1に保存する。 ※ADD命令で代用している。 |
| 4 | 0Ch | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0111b（＝7d） ※入力端子 | 0000 0000b（＝0d） ※即値 | 0000 0010b（＝2d） ※REG 2 | 入力端子からくるバイトデータをREG 2に保存する。 |
| 5 | 10h | 0010 0010b（＝34d） ※IF_LESS | 0000 0001b（＝1d） ※REG 1 | 0000 0010b（＝2d） ※REG 2 | 0010 0000b（＝32d） ※ジャンプ先のアドレス | REG 1がREG 2より小さければ、No.9（アドレス20h）にジャンプする。 |
| 6 | 14h | 0000 0001b（=1d） ※SUB | 0000 0001b（＝1d） ※REG 1 | 0000 0010b（＝2d） ※REG 2 | 0000 0001b（＝1d） ※REG 1 | REG 1←REG 1－REG2 |
| 7 | 18h | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0011b（＝3d） ※REG 3 | 0000 0001b（＝1d） ※即値 | 0000 0011b（＝3d） ※REG 3 | REG 3をインクリメントする。 |
| 8 | 1Ch | 0010 0001b（＝33d） ※IF_NOT_EUQAL | 0000 0011b（＝3d） ※REG 3 | 0000 0100b（＝4d） ※REG 4 | 0001 0000b（＝16d） ※ジャンプ先のアドレス | 無条件でNo.5（アドレス10h）にジャンプする。 無条件ジャンプの命令はまだないので、REG 3がゼロ（REG 4にセット済み）でないならジャンプするようにした。 ※ここに到達した時点でREG 3は絶対ゼロではないため。 |
| 9 | 20h | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0011b（＝3d） ※REG 3 | 0000 0000b（＝0d） ※即値 | 0000 0111b（＝7d） ※出力端子 | REG 3（商）を出力する。 ※ADD命令で代用している。 |
| 10 | 24h | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0001b（＝1d） ※REG 1 | 0000 0000b（＝0d） ※即値 | 0000 0111b（＝7d） ※出力端子 | REG1（余り）を出力する。 |
4：プログラムを実装する
1つの4バイト命令をハンドアセンブルすると4つの10進数値が得られます。アセンブリーエディターにそれらを羅列していき、プログラムを完成させます。一部コードの区切りがわかりやすいようにコメントを入れています。
# 命令1
5
3
3
3
# 命令2
5
4
4
4
# 命令3
64
7
0
1
# 命令4
64
7
0
2
# 命令5
34
1
2
32
# 命令6
1
1
2
1
# 命令7
64
3
1
3
# 命令8
33
3
4
16
# 命令9
64
3
0
7
# 命令10
64
1
0
7
5：テストする
テスト（テストパターンは128）にパスすると、ステージクリアになります。
アセンブリー言語でプログラムを実装する【別解】
命令コードを定義済み向けの解答になります。命令コードについては、AI Showdownステージで定義しました。
ADDi INPUT 0 REG1
ADDi INPUT 0 REG2
XOR REG0 REG0 REG0
ADDi REG1 0 REG4
ADDi REG2 0 REG3
label loop
IF_LESS REG4 REG3 end
SUB REG4 REG3 REG4
ADDi REG0 1 REG0
IF_EQ REG0 REG0 loop
label end
ADDi REG0 0 REG3
ADDi REG3 0 OUTPUT
ADDi REG4 0 OUTPUT
サブルーチン版
本ステージではサブルーチン回路がないのでサブルーチンを使えません。
しかし、サブルーチンの仕組みが実装されていれば、次のサブルーチンを使えます。
ただし、レジスターに余裕がない場合、レジスター内のデータ破壊が困る場合には、若干調整する必要があります。
# 除算サブルーチン.
# REG 1【入力】：被除数
# REG 2【入力】：除数
# REG 3【出力】：商
# REG 4【出力】：余り
# REG 0：計算のために使う（破壊）.
label divide
XOR REG0 REG0 REG0
ADDi REG1 0 REG4
ADDi REG2 0 REG3
label loop
IF_LESS REG4 REG3 end
SUB REG4 REG3 REG4
ADDi REG0 1 REG0
IF_EQ REG0 REG0 loop
label end
ADDi REG0 0 REG3
RET _ _ _