Xorshift

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

実装例

Xorshiftアルゴリズム^[2]のCによる実装例^[3]:

#include <stdint.h>

struct xorshift32_state {
  uint32_t a;
};

/* The state word must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
	/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
	uint32_t x = state->a;
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state->a = x;
}

struct xorshift64_state {
  uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state->a = x;
}

struct xorshift128_state {
  uint32_t x[4];
};

/* The state array must be initialized to not be all zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t t  = state->x[3];
    
    uint32_t s  = state->x[0];  /* Perform a contrived 32-bit shift. */
	state->x[3] = state->x[2];
	state->x[2] = state->x[1];
	state->x[1] = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->x[0] = t ^ s ^ (s >> 19);
}

/* The Xorshift128 algorithm can be reworded to use a pair of uint64_t state,
   or for systems with such support, a uint128_t state. */

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

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

struct xorshift64_state {
  uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 7;
	x ^= x >> 9;
	return state->a = x;
}

周期の特定

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

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

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

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

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

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

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

別の例としては

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

に対しては${\displaystyle ({\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}$のように立式し、${\displaystyle 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だとすれば${\displaystyle n=128}$, 64 bitだとすれば${\displaystyle n=256}$であり、対応する${\displaystyle d}$は以下の表のようになる。

${\displaystyle n}$	${\displaystyle 32}$	${\displaystyle 64}$	${\displaystyle 128}$	${\displaystyle 256}$
${\displaystyle 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

脚注

1. 2003年の論文執筆時点で、1800MHzのPCで毎秒2.2億個の擬似乱数を生成できた。
2. Marsaglia, 2003
3. Cでは "^" は排他的論理和を、"<<" と ">>" はビットシフトを表す。
4. 和田維作. “良い乱数・悪い乱数”. 2023年8月28日閲覧。 但し、周期が保たれる組み合わせは(7,9)と(9,7)のみである。

参考文献

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