【エ】ORANGE pico でXorshiftによる乱数生成

2023年10月24日 21:37

#クリエイターフェス 4日目、テーマは「エ」である。

Xorshift

Xorshift は、xor演算とシフト演算 (とデータ転送) のみを用いた疑似乱数生成アルゴリズムである。
今回は、これを ORANGE pico で実装した。
Xorshiftにはいくつかのバリエーションがあるが、今回は32ビットの変数を4個用いる xor128 を実装した。

シフトの仕様の確認

右シフトには、論理シフト (最上位ビットを0で埋める) と算術シフト (最上位ビットをもとの最上位ビットで埋める) がある。
Xorshiftで用いるのは論理シフトである。
算術シフトや論理シフトについては、たとえば以下のサイトでも解説されている。

では、ORANGE pico におけるシフト演算の仕様を確認してみよう。

(-2) >> 1 の結果が -1 になったので、これは算術シフトである。
公式のコマンド一覧の演算子 >> の説明には「論理右シフト」と書かれているが、これは嘘であるということが判明した。
>>> 演算子は使えず、論理右シフトを行う演算子は見当たらない。

また、<< 演算子は公式のコマンド一覧の説明通り論理左シフトを行うようである。

Xorshiftの実装

以下が今回の ORANGE pico におけるXorshiftの実装である。

10 x=123456789:y=362436069:z=521288629:w=88675123
20 for i=1 to 20
30 t=x^(x<<11)
40 x=y:y=z:z=w
50 w=(w^(w>>19 & &H1FFF))^(t^(t>>8 & &HFFFFFF))
60 print w & &H7FFF
70 next

ORANGE pico では32ビット整数の変数が使えるので、変数をそのまま状態に使用することができる。
右シフトは算術シフトの演算子しか無さそうであったが、論理AND演算を用いることで上位のビットを0にし、論理シフトの結果を得ることができる。

このコードの50行目で、変数 w に生成された乱数の値が格納される。
今回は、検証がしやすいよう、自分が以前書いた記事
IchigoJamでXorshift(疑似乱数) マシン語 vs BASIC #BASIC - Qiita
での仕様に合わせ、乱数の下位15ビットのみを出力するようにした。

実際に実行してみると、以下の結果が得られた。

先述の記事と同じ出力が得られ、正しく計算できていそうであることがわかる。

ベンチマーク

プログラムを少し改変し、以下の仕様を加えた。

for文を用いて10,000回実行する
for文だけでの実行もしてみる

10 clt
20 s=tick()
30 for i=1 to 10000
40 '
50 next
60 e=tick()
70 print "ｸｳﾃﾝ :";e-s
80 x=123456789:y=362436069:z=521288629:w=88675123
90 s=tick()
100 for i=1 to 10000
110 t=x^(x<<11):x=y:y=z:z=w:w=(w^(w>>19 & &H1FFF))^(t^(t>>8 & &HFFFFFF)):a=w & &H7FFF
120 next
130 e=tick()
140 print "BASIC:";e-s;",x=";a

これをビデオ出力 (コンポジット信号) ありの状態で実行すると、以下の結果が得られた。

ｸｳﾃﾝ :17
BASIC:234,x=17930

さらに、ビデオ出力なし (video 0 コマンド実行後) の状態で実行すると、以下の結果が得られた。

ｸｳﾃﾝ :12
BASIC:166,x=17930

今回時間計測に使用した tick() 関数は、1/60秒で「1」進む時刻を返す。
よって、Xorshiftのみ1回の計算時間は、ビデオ出力ありのとき約0.36ms、ビデオ出力なしのとき約0.26msであるといえる。

ライセンス

今回のプログラムと解説 (「Xorshift」節の内容) は、CC BY 4.0 でライセンスする。