自作CPU「CalicoCPU」で、フィボナッチ数列の計算と素数判定を行ってみた。
背景
CalicoCPUの紹介記事
ロジックICによる自作CPU「CalicoCPU」 by mikecat | elchika
において、開発の目標の一つとして
フィボナッチ数列や素数判定など、ある程度実用的なプログラムを動かせるようにする
と書いた。
これを実現するため、実際にフィボナッチ数列と素数判定のプログラムを作成した。
仕様 (共通)
今回は、
- ポート0に現在の項の値を出力する
- ポート1のビット0の立ち上がりで、次の項に進む
という仕様にした。
これに対応するため、ポート0に 3-Digit 7seg Board を、ポート1の下位ビットに Pmod BTN を接続して実行する。
フィボナッチ数列の計算
フィボナッチ数列は、最初の2項を 0, 1 とし、後の項は前2項の和とする数列である。
CalicoCPUではレジスタが4個あるので、それぞれ今の値・前の値・作業用・ジャンプ用とすることで、簡単に実装できる。
プログラム
以下のプログラムは、MikeAssembler でアセンブルできる。
target calico
; ポート0を全て出力にする
ADDI A, -1
DRIVE 0, A
; A : 今の値
MOVI A, 0
; B : 前の値
MOVI B, 1
main_loop:
; 今の値をポート0に出力する
OUT 0, A
; ポート1のビット0に0が入力されるのを待機する
MOVI D, wait_zero
wait_zero:
IN C, 1
SHL C, 7
JNZ C, D
; ポート1のビット0に1が入力されるのを待機する
MOVI D, wait_one
wait_one:
IN C, 1
NOT C
SHL C, 7
JNZ C, D
; 次の値を求める
MOV C, A
ADD A, B
MOV B, C
; 繰り返す
MOVI D, main_loop
JNZ D, D
以下は、このプログラムのHEXデータである。
:100000003F16206112E6988783899FEC988A878340
:07001000899F800548E4DF31
:00000001FF
実行結果
素数判定
今回は、8ビット符号なし整数、すなわち0～255の整数について素数判定を行いたい。
2以上の整数は、2以上自身の平方根以下の全ての素数で割り切れなければ素数であることが知られている。
よって、この範囲の整数の素数判定は、16以下の素数である 2, 3, 5, 7, 11, 13 で割ってみるだけでよい。
今回は、以下の手順で素数判定を行う。
- 2, 3, 5, 7, 11, 13 は素数と判定する。(判定した前の数との差分を引き、0になったかどうかで一致したかがわかる)
- これ以外の16未満の整数は素数でないと判定する。(上位4ビットが全て0かどうかで判定する)
- 2, 3, 5, 7, 11, 13 で割り切れるかを判定する。全てで割り切れなければ素数、そうでなければ素数でないと判定する。
2で割り切れるかどうかは、最下位ビットが0かどうかで判定できる。
3～13で割り切れるかどうかは、引き算を繰り返して0になるか、0を飛び越えて負になるかで判定する。
(0になった場合は割り切れる、0を飛び越えて負になった場合は割り切れない)
ただし、CalicoCPU のレジスタは8ビットであり、そのままでは「128以上の数」と「負の数」の区別がつかない。
そこで、引き算を始める前に割った余りが同じ128未満の数に変形する。
すると、今回引く数は全て128未満なので、最上位ビットを見ることで負になったかどうかを判定できる。
具体的には、判定したい数の下位 $k$ ビットの値を $a$、上位 $8-k$ ビットの値を $b$、割る数を $n$ とおくと、
判定したい数は $b\times 2^k + a$ と表せるので、これを $b \times (2^k \bmod n) + a$ に変形する。
- 3 で割る場合
- $2^4 = 3 \times 5 + 1$ なので、下位4ビットに上位4ビットを足した値に変形する。
- 5 で割る場合
- $2^4 = 5 \times 3 + 1$ なので、下位4ビットに上位4ビットを足した値に変形する。
- 7 で割る場合
- $2^3 = 7 \times 1 + 1$ なので、下位3ビットに上位5ビットを足した値に変形する。
- 11 で割る場合
- $2^4 = 11 \times 1 + 5$ なので、下位4ビットに上位4ビットの5倍を足した値に変形する。
- 13 で割る場合
- $2^4 = 13 \times 1 + 3$ なので、下位4ビットに上位4ビットの3倍を足した値に変形する。
プログラム
以下のプログラムは、MikeAssembler でアセンブルできる。
target calico
; ポート0を全て出力にする
ADDI A, -1
DRIVE 0, A
; A : 今の値
MOVI A, 0
main_loop:
ADDI A, 1
; Aレジスタの値が素数か判定し、素数でなければmain_loopに飛ばして次の値の判定に進む
MOVI D, prime_found
MOV B, A
; 2は素数
ADDI B, -2
MOVI C, not_2
JNZ B, C
JNZ D, D
not_2:
; 3は素数
ADDI B, -1
MOVI C, not_3
JNZ B, C
JNZ D, D
not_3:
; 5は素数
ADDI B, -2
MOVI C, not_5
JNZ B, C
JNZ D, D
not_5:
; 7は素数
ADDI B, -2
MOVI3 C, not_7
JNZ B, C
JNZ D, D
not_7:
; 11は素数
ADDI B, -4
MOVI C, not_11
JNZ B, C
JNZ D, D
not_11:
; 13は素数
ADDI B, -2
MOVI3 C, not_13
JNZ B, C
JNZ D, D
not_13:
MOVI D, main_loop
; その他の16未満の数は素数ではない
MOVI B, 0xf0
AND B, A
MOVI C, not_under_16
JNZ B, C
JNZ D, D
not_under_16:
; 2以外の偶数は素数ではない
MOVI B, 1
AND B, A
MOVI C, not_even
JNZ B, C
JNZ D, D
not_even:
; 3以外の3の倍数は素数ではない
; 8ビットのうち、上位4ビットを下位4ビットに足す
MOV B, A
SHR B, 4
MOVI C, 0xf
AND C, A
ADD B, C
; 3を引いていく
divide_3_loop:
ADDI B, -3
MOVI C, mult_3_not_zero
MOVI D, main_loop
JNZ B, C
JNZ D, D
mult_3_not_zero:
MOVI C, 0x80
AND C, B
MOVI D, not_mult_3
JNZ C, D
MOVI C, divide_3_loop
JNZ C, C
not_mult_3:
; 5以外の5の倍数は素数ではない
; 8ビットのうち、上位4ビットを下位4ビットに足す
MOV B, A
SHR B, 4
MOVI C, 0xf
AND C, A
ADD B, C
; 5を引いていく
divide_5_loop:
ADDI B, -5
MOVI C, mult_5_not_zero
MOVI D, main_loop
JNZ B, C
JNZ D, D
mult_5_not_zero:
MOVI C, 0x80
AND C, B
MOVI D, not_mult_5
JNZ C, D
MOVI C, divide_5_loop
JNZ C, C
not_mult_5:
; 7以外の7の倍数は素数ではない
; 8ビットのうち、上位5ビットを下位3ビットに足す
MOV B, A
SHR B, 3
MOVI C, 7
AND C, A
ADD B, C
; 7を引いていく
divide_7_loop:
ADDI B, -7
MOVI C, mult_7_not_zero
JNZ B, C
MOVI D, main_loop
JNZ D, D
mult_7_not_zero:
MOVI C, 0x80
AND C, B
MOVI D, not_mult_7
JNZ C, D
MOVI C, divide_7_loop
JNZ C, C
not_mult_7:
; 11以外の11の倍数は素数ではない
; 8ビットのうち、上位4ビットの5倍を下位4ビットに足す
MOV B, A
SHR B, 4
MOV C, B
SHL C, 2
ADD B, C
MOVI C, 0xf
AND C, A
ADD B, C
; 11を引いていく
divide_11_loop:
ADDI B, -5
ADDI B, -6
MOVI C, mult_11_not_zero
JNZ B, C
MOVI D, main_loop
JNZ D, D
mult_11_not_zero:
MOVI C, 0x80
AND C, B
MOVI D, not_mult_11
JNZ C, D
MOVI C, divide_11_loop
JNZ C, C
not_mult_11:
; 13以外の13の倍数は素数ではない
; 8ビットのうち、上位4ビットの3倍を下位4ビットに足す
MOV B, A
SHR B, 4
MOV C, B
SHL C, 1
ADD B, C
MOVI C, 0xf
AND C, A
ADD B, C
; 13を引いていく
divide_13_loop:
ADDI B, -6
ADDI B, -7
MOVI C, mult_13_not_zero
JNZ B, C
MOVI D, main_loop
JNZ D, D
mult_13_not_zero:
MOVI C, 0x80
AND C, B
MOVI D, not_mult_13
JNZ C, D
MOVI C, divide_13_loop
JNZ C, C
not_mult_13:
prime_found:
; 素数なので、ポート0に出力する
OUT 0, A
; ポート1のビット0に0が入力されるのを待機する
MOVI3 D, wait_zero
wait_zero:
IN C, 1
SHL C, 7
JNZ C, D
; ポート1のビット0に1が入力されるのを待機する
MOVI3 D, wait_one
wait_one:
IN C, 1
NOT C
SHL C, 7
JNZ C, D
; 繰り返す
MOVI D, main_loop
JNZ D, D
以下は、このプログラムのHEXデータである。
:100000003F162031ECC7F3407EAC5BDF7FAAB75BC5
:10001000DF7EAB895BDF7EA783005BDF7CA287B2DC
:100020005BDF7EAA83005BDFE36F474246A387B2B4
:100030005BDF614246A487BA5BDF404F4FAF828AE5
:10004000497DA587B8E35BDFA887868AE5C7F49F6B
:10005000A487B19B404F4FAF828A497BA687B2E30A
:100060005BDFA887868AE7C7FE9FA687BB9B404FBA
:100070004BA7828A4979A0B88B5BE3DFA887868A81
:10008000E9C7F89FA787B59B404F4F848349AF824C
:100090008A497B7AAA87BA5BE3DFA887868AEAC7A0
:1000A000F69FA987B29B404F4F848949AF828A4906
:1000B0007A79AC87B85BE3DFA887868AECC7F39FC1
:1000C000AB879B12ECC7F7988783899FE3C7CE98CD
:0700D0008A8783899FE3DFAB
:00000001FF