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. */
このアルゴリズムの周期はそれぞれ で、Diehardテスト(英語版)をパスしている。
64ビット整数を効率よく扱える計算機では、xor,shift操作の組を3つから2つにして計算負荷を減らしても、周期はに保たれる。[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の二元横ベクトル、現在の状態から次状態への二元遷移行列をと置くと、Xorshiftアルゴリズムにより生成される乱数列はと表される。詳しい証明は省略するが[2]、行列の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だとすればであり、対応するは以下の表のようになる。
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 (July 2003). “Xorshift RNGs”. Journal of Statistical Software Vol. 8 (Issue 14). http://www.jstatsoft.org/v08/i14/paper.
- 表示
- 編集