IchigoJamでXorshift(疑似乱数) マシン語 vs BASIC

前回の記事では、こどもパソコン IchigoJamのマシン語で
疑似乱数生成アルゴリズムのXorshiftを実装し、それを用いて換字式暗号を実装した。
しかし、執筆時点でのIchigoJam web by jig.jpではマシン語がうまく動かず、正しい結果が得られない。
そこで、Xorshiftをマシン語を使わずに実装しなおした。
そして、マシン語版との速度の比較と換字式暗号のプログラムへの組み込みを行った。

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

Xorshift

Xorshiftとは、排他的論理和・シフト演算・代入のみを用いる擬似乱数生成アルゴリズムである。
今回は、以下のWikipediaに載っているXorshiftの実装をもとに移植を行った。

uint32_t xor128(void) { 
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123; 
  uint32_t t;
 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
}

#IchigoJam BASICでの実装

Xorshiftでは32ビットの変数を扱う。
マシン語では32ビットのレジスタを使えるが、BASICの変数は16ビットしかない。
しかし、幸いXorshiftで用いる排他的論理和・シフト演算・代入のいずれも分割しての処理がしやすい処理である。
以下に今回の実装を示す。

10 'Xorshift (BASIC)
20 LET[0],#CD15,#075B,#55E5,#159A,#3BB5,#1F12,#1333,#0549
30 FOR I=1 TO 20
40 T=[0]^([0]<<11):U=[1]^([1]<<11|[0]>>5&#7FF)
50 [0]=[2]:[1]=[3]
60 [2]=[4]:[3]=[5]
70 [4]=[6]:[5]=[7]
80 V=[6]^([7]>>3&#1FFF)^T^(U<<8|T>>8&#FF):W=[7]^U^(U>>8&#FF)
90 [6]=V:[7]=W
100 ?V&#7FFF
110 NEXT

20行目で状態をWikipediaと同じ値に初期化しており、40行目から90行目までが実装の本体である。
実行すると、前回の記事のマシン語版と同様、以下の出力が得られるはずである。

17898
5862
18858
176
606
16710
5187
3884
11608
25961
12756
28197
21232
24297
22900
31957
19508
26134
16716
27526

マシン語版とBASIC版の速度の比較

マシン語版とBASIC版のXorshiftの実行速度を比較するため、

• 空行 ('のみ)
• マシン語版のXorshift
• BASIC版のXorshift

それぞれをFOR文で1000回実行し、実行時間を計測する以下のプログラムを書いた。

10 'Xorshift (ﾏｼﾝｺﾞ VS BASIC)
20 POKE#700,#3F,#A3,#18,#68,#C1,#02,#48,#40
30 POKE#708,#59,#68,#19,#60,#99,#68,#59,#60
40 POKE#710,#D9,#68,#99,#60,#D9,#68,#CA,#0C
50 POKE#718,#51,#40,#02,#0A,#48,#40,#50,#40
60 POKE#720,#D8,#60,#7F,#21,#09,#02,#FF,#31
70 POKE#728,#08,#40,#70,#47
80 CLT
90 S=TICK()
100 FOR I=1 TO 1000
110 '
120 NEXT
130 E=TICK()
140 ?"ｸｳﾃﾝ :";E-S
150 POKE#800,#15,#CD,#5B,#07,#E5,#55,#9A,#15
160 POKE#808,#B5,#3B,#12,#1F,#33,#13,#49,#05
170 S=TICK()
180 FOR I=1 TO 1000
190 X=USR(#700,0)
200 NEXT
210 E=TICK()
220 ?"ﾏｼﾝｺﾞ:";E-S;",X=";X
230 LET[0],#CD15,#075B,#55E5,#159A,#3BB5,#1F12,#1333,#0549
240 S=TICK()
250 FOR I=1 TO 1000
260 T=[0]^([0]<<11):U=[1]^([1]<<11|[0]>>5&#7FF):[0]=[2]:[1]=[3]:[2]=[4]:[3]=[5]:[4]=[6]:[5]=[7]:V=[6]^([7]>>3&#1FFF)^T^(U<<8|T>>8&#FF):W=[7]^U^(U>>8&#FF):[6]=V:[7]=W:X=V&#7FFF
270 NEXT
280 E=TICK()
290 ?"BASIC:";E-S;",X=";X

実行すると、以下のようにそれぞれの処理時間がTICK()の差(1/60秒)で出力される。
また、1000回目に生成された乱数の値も出力し、計算結果が一致していることが確認できる。

ｸｳﾃﾝ :154
ﾏｼﾝｺﾞ:279,X=12027
BASIC:1465,X=12027

これを用い、手元の環境で実行した結果は以下のようになった。
「1.4.3web」はIchigoJam web by jig.jp、ほかは実機である。
実機ではTICK()は1秒あたり60進むのに対し、執筆時点においてweb版では1秒あたり約12しか進まないようである。
また、前述の通り執筆時点においてweb版におけるマシン語版の実行結果は間違っているが、参考として示す。

バージョン	1.0.0	1.3.1	1.4.1	1.4.3web
VER()	10017	13106	14114	14323
空行の実行時間	154	78	77	251
マシン語版の実行時間	279	163	160	500
BASIC版の実行時間	1465	975	944	3501

これをもとに、FOR文を除いたXorshiftのみ1回の計算時間[ms]は以下のように計算できる。

バージョン	1.0.0	1.3.1	1.4.1	1.4.3web
マシン語版	2.083	1.417	1.383	20.750
BASIC版	21.850	14.950	14.450	270.833
BASIC版÷マシン語版	10.490	10.550	10.448	13.052

web版では差が広がっているものの、今回実験した実機ではいずれも10倍程度の差となった。

換字式暗号のプログラムへの組み込み

今回実装したBASIC版Xorshiftのプログラムを、前回の記事で実装した換字式暗号のプログラムに組み込んだ。

10 ' ｶﾝｼﾞｼｷ ｱﾝｺﾞｳ (BASIC)
20 GOTO 80
30 T=[30]^([30]<<11):U=[31]^([31]<<11|[30]>>5&#7FF):FORJ=30TO35:[J]=[J+2]:NEXT:V=[36]^([37]>>3&#1FFF)^T^(U<<8|T>>8&#FF):W=[37]^U^(U>>8&#FF):[36]=V:[37]=W:X=V&#7FFF:RETURN
40 L=0:CLK
50 K=INKEY():IF K=8 IF L=0 GOTO 50 ELSE ?CHR$(8);:L=L-1:GOTO 50
60 IF K=10 IF L=0 GOTO 50 ELSE ?CHR$(10);:RETURN
70 IF K<D OR U<K OR L=M GOTO 50 ELSE ?CHR$(K);:[40+L]=K:L=L+1:GOTO 50
80 ?"ｶﾝｼﾞｼｷ ｱﾝｺﾞｳ"
90 ?"ｱｲｺﾄﾊﾞ (16ﾓｼﾞ ﾏﾃﾞ):"
100 D=#21:U=#7E:M=16:GOSUB 40
110 IF L<16 FORI=LTO15:[40+I]=0:NEXT
120 FORI=0TO7:[30+I]=[40+I*2]|[40+I*2+1]<<8:NEXT
130 FORI=1TO16:GOSUB 30:NEXT
140 FORI=0TO25:[I]=I:NEXT
150 FORI=0TO25:GOSUB 30:P=X%(26-I):T=[I]:[I]=[I+P]:[I+P]=T:NEXT
160 ?"ｱﾝｺﾞｳｶ(0)? ﾌｸｺﾞｳ(1)?"
170 X=INKEY():IF X<#30 OR #31<X GOTO 170
180 ?X-#30:IF X=#30 GOTO 210
190 FORI=0TO25:[40+I]=[I]:NEXT
200 FORI=0TO25:[[40+I]]=I:NEXT
210 IF X=#30 ?"ﾋﾗﾌﾞﾝ"; ELSE ?"ｱﾝｺﾞｳﾌﾞﾝ";
220 ?" (31ﾓｼﾞ ﾏﾃﾞ):"
230 D=#41:U=#5A:M=31:GOSUB 40
240 IF X=#30 ?"ｱﾝｺﾞｳﾌﾞﾝ:" ELSE ?"ﾋﾗﾌﾞﾝ:"
250 FORI=0TOL-1:?CHR$(#41+[[40+I]-#41]);:NEXT:?""

実行結果は前回の記事と同様になるので、省略する。
ただし、マシン語を使っていないので、
執筆時点のIchigoJam web by jig.jp (プログラムを埋め込んだリンク) でも正常な実行結果が得られる。
ただし動作は遅く、合言葉を入れてから次の選択肢が出るまで23秒くらい待たされた。

結論

擬似乱数生成アルゴリズムのXorshiftをIchigoJamでマシン語を使わずに実装できた。
動作はマシン語より10倍程度遅くなったものの、IchigoJam web by jig.jpでも正しい実行結果が得られるようになった。