xorshift乱数ジェネレータ

高速で簡単

周期は2^128-1と十分
実装は以下のように簡素
そんでもって速いらしい

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)); 
}

乱数の種は x,y,z,w を適当に設定するみたい
これは/dev/urandomあたりから引っ張ってくればいいかな

テスト

自宅のatomネットブックで速度チェックしてみる
IOでのオーバーヘッドを減らすため
ある程度まとめて計算してみた

#include <stdint.h>
#include <stdio.h>
#define N 1024

static uint32_t _data[N];

static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;

uint32_t xor128(void) {
  uint32_t t;

  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

void xor128seed(uint32_t seed[])
{
  x = seed[0];
  y = seed[1];
  z = seed[2];
  w = seed[3];
}

void main()
{
  int i;
  FILE* fp;

  fp = fopen("/dev/urandom","r");
  fgets((void*)_data,sizeof(uint32_t) * 4, fp);
  fclose(fp);
  xor128seed(_data);

  while(1)
  {
    for(i=0;i<N;++i)
    {
      _data[i] = xor128();
    }
    fwrite(_data, sizeof(uint32_t), N, stdout);
  }
}

これをコンパイル

$ gcc xorshift.c

結果

速度チェックのためdd経由で/dev/nullに出力
適当にCtrl+Cで停止させた

$ ./a.out | dd of=/dev/null bs=1M
^C0+49840 記録始め
0+49839 記録終わり
204533760 バイト (205 MB) コピー終了, 2.01939 s, 101 MB/s

101MB/s ！
/dev/urandomの１０倍
前にやったMTの２倍だね