Xorshift RNGs

by syoyo

G. Marsaglia. Xorshift RNGs. Journal of Statistical Software,
8(14) :1 6, 2003
http://www.jstatsoft.org/v08/i14/xorshift.pdf

George Marsaglia 氏により 2003 年に考案された、xor
とシフトを使うだけの超高速な擬似乱数生成器(Random Number Generator, RNG)です。周期は 2^k-1(k
= 32, 64, 96, 128, 160, 192)。ランダム性のテストにも十分合格するとのこと。たとえば、周期が
2^128-1 の場合のルーチンは以下のようになり、乱数値の計算部分はわずか 1 行である。

unsigned long xor128(){
  static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

Xorshift 法については、擬似乱数研究で有名な Pierre L’Ecuyer 氏によりその理論の解析が行われている。

F. Panneton and P. L’Ecuyer, On the Xorshift Random
Number Generators
, 2004
http://www.iro.umontreal.ca/~lecuyer/papers.html

また、Richard Brent 氏による Xorshift 法による擬似乱数ルーチンのノートと、少なくとも
(2^4096-1)までの周期まで拡張が施された C 言語の実装 xorgen を以下のページから手に入れることができる。

Note on Marsaglia’s xorshift RNGs

http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub218.html

Some Uniform and Normal Random Number Generators
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/random.html

暗号処理に xorshift 法を使う、 xse というのもあります。

http://sandbox.emboss.co.nz/algorithm.php?CipherID=5

ただし、ニュースグループでのやりとりを見るとあまり評判はよくないみたいです。


http://www.derkeiler.com/Newsgroups/sci.crypt/2003-11/1355.html

Advertisements