IchigoJam BASIC でマシン語を使わずに mod 3079 の掛け算をする方法と、マシン語を使った場合との比較

先日の記事
IchigoJam で調光照明？ #BASIC - Qiita
では、IchigoJam のマシン語を用いて、mod 3079 での掛け算を行った。
しかし、効率は悪いが、mod 3079 での掛け算はマシン語を使わなくても行うことができる。
今回は、その方法を紹介する。

※IchigoJamはjig.jpの登録商標です。

IchigoJam BASIC で mod 3079 での掛け算を行う方法

0 以上 3079 未満の整数 $a$ および $b$ の積を 3079 で割った余りを求めたい。
このとき、普通に $a \times b$ を計算してしまうと、最大で $3078^2 = 9,474,084$ になる可能性があり、IchigoJam BASIC で扱える上限の 32,767 をオーバーしてしまう。
そこで、この上限をオーバーしない範囲に分割して計算を行う。

$32768 / 3079 = 10.64 \cdots$ なので、3079 未満の非負整数を 8 倍 (3 ビット左シフト) しても上限を越えない。
そこで、3 ビットずつに分割し、

a = a_0 8^0 + a_1 8^1 + a_2 8^2 + a_3 8^3 + a_4 8^4

とおく。($a_0, \ldots, a_4$ は 0 以上 7 以下の整数)
すると、

\begin{eqnarray*}
a \times b &=& (a_0 8^0 + a_1 8^1 + a_2 8^2 + a_3 8^3 + a_4 8^4) b \\
&=& a_0 (8^0 b) + a_1 (8^1 b) + a_2 (8^2 b) + a_3 (8^3 b) + a_4 (8^4 b)
\end{eqnarray*}

となる。
このことから、

1. 答えを 0 に初期化する
2. 答えに「$a$ の下位 3 ビットと $b$ を掛けたもの」を足す
3. $a$ を 3 ビット右シフトする (次の 3 ビットを、下位 3 ビットに持ってくる)
4. $b$ に 8 を掛ける
5. 2～4 を繰り返す

という手順で、オーバーフローを避けて $a \times b \mod 3079$ の値を求めることができる。
(掛け算や足し算は ${} \mod 3079$ で行う)

これを実装すると、以下のようになる。

10 M=3079
20 INPUT A
30 INPUT B
40 R=0
50 FOR I=1 TO 5
60 R=(A&7*B+R)%M
70 A=A>>3
80 B=B<<3%M
90 NEXT
100 PRINT R

マシン語を使った場合との比較

プログラム

前回の記事のプログラムを応用し、マシン語と速度を比較するため、以下のプログラムを用意した。

10 ' mod 3079 ﾍﾞﾝﾁ
20 LET[0],12215,-8182,#8593,16389,#D603,19813,1331,709,#D603,20037,25907,709,#8082,8712,530,6281,12748,#894A,17232,#8B09,#B500,18328,17928,#BD00
30 F=1793:M=3079:CLS
40 CLT:P=1:FORI=1TOM-1
50 DRAW(P-1)%64,(P-1)/64
60 D=F:V=P:P=0:FORJ=1TO5:P=(V&7*D+P)%M:V=V>>3:D=D<<3%M:NEXT
70 NEXT:R=TICK()
80 WAIT60:CLS
90 CLT:P=1:FORI=1TOM-1
100 DRAW(P-1)%64,(P-1)/64
110 P=USR(#800,P)
120 NEXT:S=TICK()
130 WAIT60:CLS
140 ?"BASIC: ";R
150 ?"ﾏｼﾝｺﾞ: ";S

20 行目でマシン語のプログラムを用意し、30 行目で掛ける数と割る数を用意している。
40～80行目が BASIC による計算処理、90～130行目がマシン語による計算処理である。
これらは同じ構造をしており、ほぼ同じ条件になるはずである。
これらの計算処理を行った後、最後にかかった時間を出力して終了する。

マシン語では、第1引数の値に変数 F の値を掛け、変数 M の値で割った余りを求めて返す。

マシン語のソースコード

	IF M0 GOTO @CALC_M0
MODE RV32C
	R11 = R11 + #400
	R12 = [R11 + #4D6]W
	R10 = R10 * R12
	R12 = [R11 + #4E4]W
	R10 = R10 % R12
	RET
MODE M0
@CALC_M0
	R2 = 8
	R2 = R2 << 8
	R1 = R1 + R2
	R1 += #CC
	R2 = [R1 + 5]W
	R0 *= R2
	R1 = [R1 + 12]W
	PUSH {LR}
	GOSUB R3
	R0 = R1
	POP {PC}

実行結果

各機種で1回実行を行ったところ、以下の処理時間 (TICK() 単位) になった。

機種	バージョン	BASIC時間	マシン語時間	BASIC÷マシン語
IchigoJam Q	1.4.3	5706	1001	5.70
IchigoJam R	1.5b	693	121	5.73
IchigoJam P	1.6.0	344	61	5.64

今回実行を行ったどの機種でも、マシン語版に比べてBASIC版は約5.7倍の処理時間となった。

おわりに

IchigoJam BASIC でマシン語を使わなくても mod 3079 の掛け算はできるが、マシン語を使った方がかなり効率よく計算ができることを確認できた。

よく考えたら、3079 から 4 回 3 ビット右シフトを繰り返すと 0 になるので、5 回目のループは完全に無駄なんだよなあ……
でも、動画撮った後に気付いて、撮り直すのは面倒だから、まあこのままでいっか……