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

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

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

# Xorshift

Xorshiftとは、排他的論理和・シフト演算・代入のみを用いる[擬似乱数](https://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0)生成アルゴリズムである。
今回は、以下の[Wikipediaに載っているXorshiftの実装](https://ja.wikipedia.org/w/index.php?title=Xorshift&oldid=79799391)をもとに移植を行った。

```c
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行目までが実装の本体である。
実行すると、[前回の記事](https://qiita.com/mikecat_mixc/items/8d4825b92aeb088ea66a)のマシン語版と同様、以下の出力が得られるはずである。

```
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](https://fukuno.jig.jp/app/IchigoJam/)、ほかは実機である。
実機では`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|

![実行時間のグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/868a84ee-c1cd-7cee-67ba-66278db716d0.png)

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

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

今回実装したBASIC版Xorshiftのプログラムを、[前回の記事](https://qiita.com/mikecat_mixc/items/8d4825b92aeb088ea66a)で実装した換字式暗号のプログラムに組み込んだ。

```
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](https://fukuno.jig.jp/app/IchigoJam/#10%20%27%20%EF%BD%B6%EF%BE%9D%EF%BD%BC%EF%BE%9E%EF%BD%BC%EF%BD%B7%20%EF%BD%B1%EF%BE%9D%EF%BD%BA%EF%BE%9E%EF%BD%B3%20%28BASIC%29%0A20%20GOTO%2080%0A30%20T%3D%5B30%5D%5E%28%5B30%5D%3C%3C11%29%3AU%3D%5B31%5D%5E%28%5B31%5D%3C%3C11%7C%5B30%5D%3E%3E5%26%237FF%29%3AFORJ%3D30TO35%3A%5BJ%5D%3D%5BJ%2B2%5D%3ANEXT%3AV%3D%5B36%5D%5E%28%5B37%5D%3E%3E3%26%231FFF%29%5ET%5E%28U%3C%3C8%7CT%3E%3E8%26%23FF%29%3AW%3D%5B37%5D%5EU%5E%28U%3E%3E8%26%23FF%29%3A%5B36%5D%3DV%3A%5B37%5D%3DW%3AX%3DV%26%237FFF%3ARETURN%0A40%20L%3D0%3ACLK%0A50%20K%3DINKEY%28%29%3AIF%20K%3D8%20IF%20L%3D0%20GOTO%2050%20ELSE%20%3FCHR%24%288%29%3B%3AL%3DL-1%3AGOTO%2050%0A60%20IF%20K%3D10%20IF%20L%3D0%20GOTO%2050%20ELSE%20%3FCHR%24%2810%29%3B%3ARETURN%0A70%20IF%20K%3CD%20OR%20U%3CK%20OR%20L%3DM%20GOTO%2050%20ELSE%20%3FCHR%24%28K%29%3B%3A%5B40%2BL%5D%3DK%3AL%3DL%2B1%3AGOTO%2050%0A80%20%3F%22%EF%BD%B6%EF%BE%9D%EF%BD%BC%EF%BE%9E%EF%BD%BC%EF%BD%B7%20%EF%BD%B1%EF%BE%9D%EF%BD%BA%EF%BE%9E%EF%BD%B3%22%0A90%20%3F%22%EF%BD%B1%EF%BD%B2%EF%BD%BA%EF%BE%84%EF%BE%8A%EF%BE%9E%20%2816%EF%BE%93%EF%BD%BC%EF%BE%9E%20%EF%BE%8F%EF%BE%83%EF%BE%9E%29%3A%22%0A100%20D%3D%2321%3AU%3D%237E%3AM%3D16%3AGOSUB%2040%0A110%20IF%20L%3C16%20FORI%3DLTO15%3A%5B40%2BI%5D%3D0%3ANEXT%0A120%20FORI%3D0TO7%3A%5B30%2BI%5D%3D%5B40%2BI%2A2%5D%7C%5B40%2BI%2A2%2B1%5D%3C%3C8%3ANEXT%0A130%20FORI%3D1TO16%3AGOSUB%2030%3ANEXT%0A140%20FORI%3D0TO25%3A%5BI%5D%3DI%3ANEXT%0A150%20FORI%3D0TO25%3AGOSUB%2030%3AP%3DX%25%2826-I%29%3AT%3D%5BI%5D%3A%5BI%5D%3D%5BI%2BP%5D%3A%5BI%2BP%5D%3DT%3ANEXT%0A160%20%3F%22%EF%BD%B1%EF%BE%9D%EF%BD%BA%EF%BE%9E%EF%BD%B3%EF%BD%B6%280%29%3F%20%EF%BE%8C%EF%BD%B8%EF%BD%BA%EF%BE%9E%EF%BD%B3%281%29%3F%22%0A170%20X%3DINKEY%28%29%3AIF%20X%3C%2330%20OR%20%2331%3CX%20GOTO%20170%0A180%20%3FX-%2330%3AIF%20X%3D%2330%20GOTO%20210%0A190%20FORI%3D0TO25%3A%5B40%2BI%5D%3D%5BI%5D%3ANEXT%0A200%20FORI%3D0TO25%3A%5B%5B40%2BI%5D%5D%3DI%3ANEXT%0A210%20IF%20X%3D%2330%20%3F%22%EF%BE%8B%EF%BE%97%EF%BE%8C%EF%BE%9E%EF%BE%9D%22%3B%20ELSE%20%3F%22%EF%BD%B1%EF%BE%9D%EF%BD%BA%EF%BE%9E%EF%BD%B3%EF%BE%8C%EF%BE%9E%EF%BE%9D%22%3B%0A220%20%3F%22%20%2831%EF%BE%93%EF%BD%BC%EF%BE%9E%20%EF%BE%8F%EF%BE%83%EF%BE%9E%29%3A%22%0A230%20D%3D%2341%3AU%3D%235A%3AM%3D31%3AGOSUB%2040%0A240%20IF%20X%3D%2330%20%3F%22%EF%BD%B1%EF%BE%9D%EF%BD%BA%EF%BE%9E%EF%BD%B3%EF%BE%8C%EF%BE%9E%EF%BE%9D%3A%22%20ELSE%20%3F%22%EF%BE%8B%EF%BE%97%EF%BE%8C%EF%BE%9E%EF%BE%9D%3A%22%0A250%20FORI%3D0TOL-1%3A%3FCHR%24%28%2341%2B%5B%5B40%2BI%5D-%2341%5D%29%3B%3ANEXT%3A%3F%22%22%0A) (プログラムを埋め込んだリンク) でも正常な実行結果が得られる。
ただし動作は遅く、合言葉を入れてから次の選択肢が出るまで23秒くらい待たされた。

# 結論

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