Xorshift

Xorshiftは疑似乱数列生成法の1つである。George Marsagliaが2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速である
などの特徴がある。
実装例.
XorshiftアルゴリズムのCによる実装例:
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. */
このアルゴリズムの周期はそれぞれformula_1 で、をパスしている。
64ビット整数を効率よく扱える計算機では、xor,shift操作の組を3つから2つにして計算負荷を減らしても、周期はformula_2に保たれる。
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の二元横ベクトルformula_3、現在の状態から次状態への二元遷移行列をformula_4と置くと、Xorshiftアルゴリズムにより生成される乱数列はformula_5と表される。詳しい証明は省略するが、行列formula_4のOrderがformula_7で表される時、かつその時に限り、任意の0でないformula_3に対しformula_9は全て異なる値となる。
予備的なテストとしては、今周期formula_10についてformula_7となることを期待しているため、期待するformula_12がformula_13を満たす最小のformula_12であるかを調べる、というものがある。これはformula_4をformula_12回二乗すれば良いため、乱数列を調べるのと比較すると十分に速く調べられる。
完全なテストとしては、期待する周期formula_10の約数formula_18についてformula_19を示せば良い。例えば、formula_12 bitのビット列formula_21に対する操作が
x ^= x « a;
x ^= x » b;
x ^= x « c;
return x;
である場合、formula_22である。但し、formula_23及びformula_24である。
formula_25の場合、formula_26及びformula_27を調べれば十分である。
formula_28の場合、formula_2がformula_30の倍数であるということに注意すると、formula_31及びformula_32を調べれば十分である。
別の例としては
t = x ^ (x « 11);
x = y; y = z; z = w;
return w = (w ^ (w » 19)) ^ (t ^ (t » 8)); 
に対してはformula_33のように立式し、formula_34について同様に解く。各変数が32 bitだとすればformula_35, 64 bitだとすればformula_36であり、対応するformula_18は以下の表のようになる。