Xorshift

Xorshiftは疑似乱数列生成法の1つである。George Marsagliaが2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速であるなどの特徴がある。

実装例

XorshiftアルゴリズムのCによる実装例:

uint32_t xor(void) {
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 15);
}

uint32_t xor64(void) {
  static uint64_t x = 88172645463325252ULL;
  x = x ^ (x << 13); x = x ^ (x >> 7);
  return x = x ^ (x << 17);
}

uint32_t xor96(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  uint32_t t;

  t = (x ^ (x << 3)) ^ (y ^ (y >> 19)) ^ (z ^ (z << 6));
  x = y; y = z;
  return z = t;
}

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)); 
}

このアルゴリズムの周期はそれぞれ$2^{32}-1,2^{64}-1,2^{96}-1,2^{128}-1$ で、Diehardテストをパスしている。

64ビット整数を効率よく扱える計算機では、xor,shift操作の組を3つから2つにして計算負荷を減らしても、周期は$2^{64}-1$に保たれる。[1]

uint64_t xor64(void) {
  static uint64_t x = 88172645463325252ULL;
  x = x ^ (x << 7);
  return x = x ^ (x >> 9);
}

周期の特定

シード値を128bitの二元横ベクトル$\beta$、現在の状態から次状態への二元遷移行列を$T$と置くと、Xorshiftアルゴリズムにより生成される乱数列は$\beta ,\beta T,\beta T^{2},\dots$と表される。詳しい証明は省略するが、行列$T$のOrderが$k=2^{n}-1$で表される時、かつその時に限り、任意の0でない$\beta$に対し$\beta ,\beta T,\beta T^{2},\dots ,\beta T^{k-1}$は全て異なる値となる。

予備的なテストとしては、今周期$k$について$k=2^{n}-1$となることを期待しているため、期待する$n$が$T^{2^{n}}=T$を満たす最小の$n$であるかを調べる、というものがある。これは$T$を$n$回二乗すれば良いため、乱数列を調べるのと比較すると十分に速く調べられる。

完全なテストとしては、期待する周期$k$の約数$d$について$T^{d}\neq I\iff k\neq d$を示せば良い。例えば、$n$ bitのビット列$x$に対する操作が

x ^= x << a;
x ^= x >> b;
x ^= x << c;
return x;

である場合、$T=(I+L^{a})(I+R^{b})(I+L^{c})$である。但し、$L_{i,j}^{a}={\begin{cases}1&i=j+a\\0&{\text{otherwise}}\end{cases}}$及び$R_{i,j}^{a}={\begin{cases}1&i=j-a\\0&{\text{otherwise}}\end{cases}}$である。

$n=32$の場合、$T^{d}\neq I\Longleftarrow d={\begin{cases}65535\\16711935\\252645135\\858993459\\1431655765\end{cases}}$及び$T^{2^{32}}=T$を調べれば十分である。

$n=64$の場合、$2^{64}-1$が$641$の倍数であるということに注意すると、$T^{d}\neq I\Longleftarrow d={\begin{cases}2753074036095\\281470681808895\\28778071877862015\\71777214294589695\\1085102592571150095\\3689348814741910323\\6148914691236517205\end{cases}}$及び$T^{2^{64}}=T$を調べれば十分である。

別の例としては

t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));

に対しては$({\begin{smallmatrix}x_{n+1}&y_{n+1}&z_{n+1}&w_{n+1}\end{smallmatrix}})=({\begin{smallmatrix}x_{n}&y_{n}&z_{n}&w_{n}\end{smallmatrix}})\cdot T$のように立式し、$T=\left({\begin{smallmatrix}O&O&O&(I+L^{11})(I+R^{8})\\I&O&O&O\\O&I&O&O\\O&O&I&(I+R^{19})\\\end{smallmatrix}}\right)$について同様に解く。各変数が32 bitだとすれば$n=128$, 64 bitだとすれば$n=256$であり、対応する$d$は以下の表のようになる。

$n$	$32$	$64$	$128$	$256$
$d$	0x0000ffff	0x00000280fffffd7f	0x0000000000042f00fffffffffffbd0ff	0x000000000000000000d3eafc3af14600ffffffffffffffffff2c1503c50eb9ff
	0x00ff00ff	0x0000ffff0000ffff	0x00000280fffffd7f00000280fffffd7f	0x000000000000013540775b48cc32ba00fffffffffffffecabf88a4b733cd45ff
	0x0f0f0f0f	0x00663d80ff99c27f	0x00003d30f19cd100ffffc2cf0e632eff	0x0000000000042f00fffffffffffbd0ff0000000000042f00fffffffffffbd0ff
	0x33333333	0x00ff00ff00ff00ff	0x0000ffff0000ffff0000ffff0000ffff	0x00000280fffffd7f00000280fffffd7f00000280fffffd7f00000280fffffd7f
	0x55555555	0x0f0f0f0f0f0f0f0f	0x00663d80ff99c27f00663d80ff99c27f	0x00003d30f19cd100ffffc2cf0e632eff00003d30f19cd100ffffc2cf0e632eff
		0x3333333333333333	0x00ff00ff00ff00ff00ff00ff00ff00ff	0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff
		0x5555555555555555	0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f	0x00663d80ff99c27f00663d80ff99c27f00663d80ff99c27f00663d80ff99c27f
			0x33333333333333333333333333333333	0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff
			0x55555555555555555555555555555555	0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
				0x3333333333333333333333333333333333333333333333333333333333333333
				0x5555555555555555555555555555555555555555555555555555555555555555

参考文献

• Marsaglia (2003年7月). “Xorshift RNGs”. Journal of Statistical Software Vol. 8 (Issue  14). http://www.jstatsoft.org/v08/i14/paper.