Xorshiftで乱数発生

Xorshiftという乱数発生アルゴリズムがあります。

http://ja.wikipedia.org/wiki/Xorshift

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

32bitの内部変数を4つ持っていて、それをぐるぐる回しながらシフトさせて、Xorをとるという単純なアルゴリズムです。それで、周期が2^128-1というとても優れたものです。

このアルゴリズムはとてもFPGA向けだと思います。

なぜなら、

• XORとSHIFTだけなので、LUTだけで作れる（内蔵乗算器が不要）
• 加算も不要なので、桁上がりがなく、高速
• 乱数が32bit単位で計算されてくる

今まで乱数生成用にLFSRを使っていましたが、LFSRだと1ビットごとにしか結果が出てこないのに対し、XORSHIFTなら32bit単位で出てくるので、とても使いやすいのです。

で、何をしようとしてこのアルゴリズムを使おうとしたかというと、特電SATA-IPコアのテストです。500GBのHDDを乱数で埋め尽くして、それをPCで読み出して読み書き内容の照合をしようとしています。

500GBのHDDということは、39bitにもなるので、周期が32bitやそこらの乱数では足りないわけです。単純なLFSRだと500GB埋める前に周期が来てしまいます。

そこで、簡単なアルゴリズムで、周期が長く、そこそこ優れた乱数を発生させる方法を探していてXORSHIFTに出会ったというわけです。