Xorshift
Xorshiftは疑似乱数列生成法の1つである。George Marsagliaが2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速である[1]などの特徴がある。
実装例[編集]
uint32_t xor(void) {
static uint32_t y = 2463534242;
y = y ^ (y << 13); y = y ^ (y >> 17);
return y = y ^ (y << 5);
}
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));
}
このアルゴリズムの周期はそれぞれ で、Diehardテストをパスしている。
64ビット整数を効率よく扱える計算機では、xor,shift操作の組を3つから2つにして計算負荷を減らしても、周期はに保たれる。[1]
uint64_t xor64(void) {
static uint64_t x = 88172645463325252ULL;
x = x ^ (x << 7);
return x = x ^ (x >> 9);
}
周期の特定[編集]
シード値を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) .