2009年8月3日月曜日

4ビットマイコンで素数を求めてみた

このブログ記事をはてなブックマークに追加

最近、大人の科学マガジン4ビットマイコン(GMC-4)が付いていると聞いて早速購入してみたのだが、ここまで面白いものだとは思わなかった。本物のコンピュータが付いて2,500円というのもの非常にリーズナブルだ。自分は純粋に楽しめたが、教育用に使うのも良さそうだ。雑誌自体はかなり薄い作りだが、内容はとても興味深いものだった。コンピュータの歴史から、ハードの仕組み、インタビュー、4ビットマイコンの説明など。読んでいるだけでワクワクする。

付録の4ビットマイコンにはGMC-4という名前が付いているが、これはGakken Micro Computerの略なんだそうだ。メモリはかなり貧弱で、プログラムメモリで00~4F番地まで、データメモリで50~5F番地までしかない。しかも、それぞれの番地は4ビットしか情報量を持たない。つまり1バイトを8ビットとすると、プログラムメモリで40バイト、データメモリで8バイトしかない。また、レジスタは補助レジスタをあわせて8種類あるが、同時に扱えるレジスタはAレジスタとYレジスタしかない。しかし、これだけの制約があると逆に挑戦してやろうと思ってしまうから不思議だ。

そこで、今回は素数を求めるプログラムを作ってみることにした。最初に考えた方法は、求めた素数をメモリに保存し、その素数を使って新たな素数を求めていくものだった。しかし、当然のように除算命令などないし、メモリが貧弱のため、求めた素数を取り置くのも難しい。そこで、求めた素数は使わずに、素数候補の数値を奇数で割っていき、その奇数が素数候補となるまで割り切れなければ素数とした。ここでは「割る」と書いたが、プログラム上では素数候補から奇数を引いていき、0になれば割り切れるとしている。このようにして求めた素数は数字LEDにそれぞれ一秒間表示される。今回は3~15(F)までの素数を求めた。それほど難しいプログラムであるわけでもないのに、数字LEDに3, 5, 7, b(11), d(13)と順次表示されるのを確認したときには妙に嬉しくなった。

久々のハンドアセンブルであったが、非常に楽しいものだった。当時もこのようにして夢中になったことを思い出した。もっとも、今回の4ビットマイコンは当時のZ80と比べてもかなり貧弱な環境だったが。素数を求めるプログラムもプログラムメモリ領域ぎりぎりの40バイトを全部使った。もう少し効率よく書けるかもしれないけど、プログラムの入力だけでも結構な手間なので取り敢えずこのままで。

最後に、今回作成したプログラムを掲載しておく。

00 TIA 8 ; Aレジスタ(Ar)に3を代入. 素数候補用. 01 <3> 3 02 TIY A ; Yレジスタ(Yr)に0を代入. 03 <0> 0 04 AM 4 ; 50番地のメモリ(M[0])にArを代入. 素数を入れておく. LABEL1: 05 AO 1 ; LEDに素数を表示. 06 TIA 8 ; ウェイトを1秒に設定. 07 <9> 9 08 CAL E 09 TIMR C ; ウェイト. 0A MA 5 ; ArにM[0]を代入. Arに素数を入れ直す. LABEL2: 0B AIA 9 ; Arに2を足す. 素数は奇数のみ. 0C <2> 2 0D AM 4 ; M[0]にArを代入. 新たな素数. 0E CIA C ; ArがF(15)か? 0F <F> F 10 JUMP F ; ArがF(15)でないなら LABEL3 に飛ぶ. 11 <1> 1 12 <6> 6 13 JUMP F ; ArがF(15)なら END に飛ぶ. 14 <4> 4 15 <D> D LABEL3 16 TIA 8 ; Arに3を代入. 素数チェック用の数値の初期値. 奇数. 17 <3> 3 LABEL4 18 TIY A ; Yrに1を代入. 19 <1> 1 1A AM 4 ; M[1]にArを代入. 素数チェック用数値. 1B TIY A ; Yrに0を代入. 1C <0> 0 1D MA 5 ; ArにM[0]を代入. 素数候補. 1E TIY A ; Yrに1を代入. 1F <1> 1 20 M- 7 ; Arに M[1] - Ar を代入. 21 JUMP F ; Arが負の数なら LABEL5 に飛ぶ. 素数ではない. 22 <2> 2 23 <A> A 24 TIY A ; Yrに0を代入. 25 <0> 0 26 MA 5 ; M[0]にArを代入. 素数候補をArに戻す. 27 JUMP F ; Arが正の数なら LABEL1 に飛ぶ. 素数が見つかった. 28 <0> 0 29 <5> 5 LABEL5: 2A TIY A ; Yrに0を代入. 2B <0> 0 2C MA 5 ; ArにM[0]を代入. 素数候補をArに戻す. 2D TIY A ; Yrに1を代入. 2E <1> 1 LABEL6: 2F M- 7 ; Arに M[1] - Ar を代入. 30 JUMP F ; Arが負の数なら LABEL7 に飛ぶ. 31 <3> 3 32 <E> E 33 CIA C ; Arが0か? 34 <0> 0 35 JUMP F ; Arが0でないなら LABEL8 に飛ぶ. 36 <4> 4 37 <6> 6 38 TIY A ; Yrに0を代入. 39 <0> 0 3A MA 5 ; ArにM[0]を代入. 素数候補をArに戻す. 3B JUMP F ; LABEL2 3C <0> 0 3D <B> B LABEL7: 3E CAL E 3F CMPL 4 ; Arをビット反転. 40 AIA 9 ; Arに1を足す. 負の数を正の数に変換. 2の補数. 41 <1> 1 42 KA 0 ; 実行フラグを1にするため. 43 JUMP F ; LABEL6 に飛ぶ. 44 <2> 2 45 <F> F LABEL8: 46 MA 5 ; ArにM[1]を代入. 素数チェック用の数値をArに戻す. 47 AIA 9 ; Arに2を足す. 次の素数チェック用の数値. 48 <2> 2 49 KA 0 ; 実行フラグを1にするため. 4A JUMP F ; LABEL4 に飛ぶ. 4B <1> 1 4C <8> 8 END: 4D JUMP F ; 終了後は無限ループ. 4E <4> 4 4F <D> D

0 コメント: