Xorshift

Xorshiftは疑似乱数列生成法の1つである。George Marsaglia（w:George Marsaglia）が2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速である2003年の論文執筆時点で、1800MHzのPCで毎秒2.2億個の擬似乱数を生成できた。

などの特徴がある。

 実装例 
Xorshiftアルゴリズム Marsaglia, 2003 のCによる実装例Cでは "^" は排他的論理和を、"<<" と ">>" はビットシフトを表す。:

#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. */

このアルゴリズムの周期はそれぞれ で、をパスしている。

64ビット整数を効率よく扱える計算機では、xor,shift操作の組を3つから2つにして計算負荷を減らしても、周期はに保たれる。 但し、周期が保たれる組み合わせは(7,9)と(9,7)のみである。
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の二元横ベクトル、現在の状態から次状態への二元遷移行列をと置くと、Xorshiftアルゴリズムにより生成される乱数列はと表される。詳しい証明は省略するが、行列のOrderがで表される時、かつその時に限り、任意の0でないに対しは全て異なる値となる。

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

完全なテストとしては、期待する周期の約数についてを示せば良い。例えば、 bitのビット列に対する操作がx ^= x << a;
x ^= x >> b;
x ^= x << c;
return x;である場合、である。但し、及びである。

の場合、及びを調べれば十分である。

の場合、がの倍数であるということに注意すると、及びを調べれば十分である。

別の例としてはt = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); に対してはのように立式し、について同様に解く。各変数が32 bitだとすれば, 64 bitだとすればであり、対応するは以下の表のようになる。
0x0000ffff0x00000280fffffd7f0x0000000000042f00fffffffffffbd0ff0x000000000000000000d3eafc3af14600ffffffffffffffffff2c1503c50eb9ff0x00ff00ff0x0000ffff0000ffff0x00000280fffffd7f00000280fffffd7f0x000000000000013540775b48cc32ba00fffffffffffffecabf88a4b733cd45ff0x0f0f0f0f0x00663d80ff99c27f0x00003d30f19cd100ffffc2cf0e632eff0x0000000000042f00fffffffffffbd0ff0000000000042f00fffffffffffbd0ff0x333333330x00ff00ff00ff00ff0x0000ffff0000ffff0000ffff0000ffff0x00000280fffffd7f00000280fffffd7f00000280fffffd7f00000280fffffd7f0x555555550x0f0f0f0f0f0f0f0f0x00663d80ff99c27f00663d80ff99c27f0x00003d30f19cd100ffffc2cf0e632eff00003d30f19cd100ffffc2cf0e632eff0x33333333333333330x00ff00ff00ff00ff00ff00ff00ff00ff0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0x55555555555555550x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0x00663d80ff99c27f00663d80ff99c27f00663d80ff99c27f00663d80ff99c27f0x333333333333333333333333333333330x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff0x555555555555555555555555555555550x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0x33333333333333333333333333333333333333333333333333333333333333330x5555555555555555555555555555555555555555555555555555555555555555

 脚注 

 参考文献 

Category:乱数
Category:数学に関する記事