Xorshift

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

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

実装例[編集]

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

uint32_t xor(void) {
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 15);
}

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

脚注[編集]

  1. ^ 2003年の論文執筆時点で、1800MHzのPCで毎秒2.2億個の擬似乱数を生成できた。
  2. ^ a b Marsaglia, 2003
  3. ^ Cでは "^" は排他的論理和を、"<<" と ">>" はビットシフトを表す。

参考文献[編集]