Xorshift

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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 << 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テスト英語版をパスしている。

周期の特定[編集]

シード値を128bitの二元横ベクトル、現在の状態から次状態への二元遷移行列をと置くと、Xorshiftアルゴリズムにより生成される乱数列はと表される。詳しい証明は省略するが[2]、行列のOrderがで表される時、かつその時に限り、任意の0でないに対しは全て異なる値となる。

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

脚注[編集]

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

参考文献[編集]