2011-09-12

XORshift乱数

XORshiftとは

XORshiftは、random number generator(乱数生成器, RNG)の一つ。周期が十分長く、演算も簡単なので生成速度も速いのが特徴。

コード

wikipediaや論文に載っているのは、周期が2^128-1のもの。
C/C++では、「^」はビットXOR、「>>」はビットシフトを表し、実際それぐらいしか使ってないぐらいシンプル。

// 注意: longではなくint(32bit)にすべき
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));
}

ところで、初期化はどうやるのか気になったので調べてみたら、論文には

The seed set for xor128 is four 32-bit integers x,y,z,w not all 0, ...

って書いてあって、適当に当てはめてもいいみたいだけど、以下のページでよさげな初期化の仕方が紹介されてた。
http://ogawa-sankinkoutai.seesaa.net/article/108848981.html

unsigned long seed128[4]; //x,y,z,wとして利用
void seed(unsigned int s){    
    for(int i=1; i<=4; i++){
        seed128[i-1] = s = 1812433253U * (s^(s>>30)) + i;
    }
}
unsigned long xor128(){
  unsigned long t;
  t=(seed128[0]^(seed128[0]<<11));
  seed128[0]=seed128[1];
  seed128[1]=seed128[2];
  seed128[2]=seed128[3];
  return seed128[3]=(seed128[3]^(seed128[3]>>19))^(t^(t>>8));
}

遊びでちょっと使う分には上のコードでwの値を変えるのでよさそう。。

参考ページ

2011-09-12

言語モデルの評価尺度

自然言語処理

エントロピー、パープレキシティ

言語Lにおいて、単語列 $w_1^n=w_1w_2...w_n$ の生起確率が $P(w_1^n)$ のとき、1単語あたりのエントロピーは、
$H(L)=-\sum_{w_1^n}{\frac{1}{n}P(w_1^n)logP(w_1^n)}$
になる。
ある単語について、平均して $2^{H(L)}$ 個の単語が次につながりうることを表す。
この $PP=2^{H(L)}$ はパープレキシティと呼ばれる。