自作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

CalicoCPUでフィボナッチ数列の計算・素数判定

背景

仕様 (共通)

フィボナッチ数列の計算

プログラム

実行結果

素数判定

プログラム

実行結果