Sim's blog

先日、twitterでのやりとりを介してxorshift乱数発生アルゴリズムのことを知りました。非常に簡単な処理(xorとshiftだけ)で周期の長い擬似乱数を生成できるアルゴリズムです。詳しくはwikipediaのxorshiftで。
例になっているのは全て1ワードが32bitのものでした。8bitマイコンとかでも使いやすいように1ワードが8bitのバージョンを作れないかと思って試してみました。
乱数検定はしていませんが、周期だけは確認しています。

(1) 周期が255 (= 2^8 - 1)

アルゴリズム
uint8_t x;
x ^= x >> A;
x ^= x << B;
x ^= x >> C;
return x;

シードはxの初期値です。AとBとCは定数で、全探索してみたところ24組が周期255になることが分かりました。

1 : 1 1 2 (A B Cの順)
2 : 1 1 3
3 : 1 7 3
4 : 1 7 6
5 : 1 7 7
6 : 2 1 1
7 : 2 5 5
8 : 3 1 1
9 : 3 1 5
10 : 3 5 4
11 : 3 5 5
12 : 3 5 7
13 : 3 7 1
14 : 4 5 3
15 : 5 1 3
16 : 5 3 6
17 : 5 3 7
18 : 5 5 2
19 : 5 5 3
20 : 6 3 5
21 : 6 7 1
22 : 7 3 5
23 : 7 5 3
24 : 7 7 1

(2) 周期が16777215 (= 2^24 - 1)

アルゴリズム
uint8_t x, y, z, t;
t = x ^ x << a;
x = y;
y = z;
z ^= z >> c ^ t ^ t >> b;
return z;

シードはx, y, zの初期値です。周期が16777215になるのは1通りでした。

1 : 1 5 3 (A B Cの順)

(3) 周期が2147483647 (= 2^31 - 1)

アルゴリズム
t = x ^ x << a;
x = y;
y = z;
z = w;
w ^= w >> c ^ t ^ t >> b;
return w;


次は周期が2^32 - 1と思って探したのですが、見つかりませんでした。そのかわり、約半分の2^31 - 1のものが見つかりました。今までの例は0以外の全ての値を取るので、シードとしてどの値から始めても同じ周期になりますが、今回のはちょうど半分しか回っていないので、初期値によっては周期が2^31-1にならない可能性があるのではないかと思います。その意味でも周期が2^32 - 1のものが見つからなかったのは残念です。
周期が2147483647となるA B Cの組は13通りありました。

1 : 1 1 6
2 : 1 1 7
3 : 1 2 7
4 : 1 4 7
5 : 1 6 7
6 : 3 1 6
7 : 3 2 1
8 : 3 5 1
9 : 4 3 1
10 : 5 1 5
11 : 6 1 3
12 : 6 5 2
13 : 7 2 1

おわりに

乱数検定とかしてないので、どのくらい良い乱数かは分かりませんが、周期だけは長いです。

参考文献

G. Marsaglia, “Xorshift RNGs,”Journal of Statistical Software, 8(14), July 2003.
(http://www.jstatsoft.org/v08/i14/paper)