はじめに
[0,1)の浮動小数点数乱数については以前にコードを書きました.
[0,N)の範囲の整数乱数を生成する方法について書きます. 非常に詳しい説明と実装が[1]にあります.
バイアスありの方法
次のように余りを計算する方法では偏ることは有名ですね. 2^32個の数字をrange個にマッピング仕直す計算なので, 2^32/rangeが割り切れない場合小さな数字から多くマッピングされます.
uint32_t bounded_rand(rng_t& rng, uint32_t range)
{
return rng() % range;
}
次のように, [0 1)の浮動小数点数を介する方法も偏りますね. 上の方法と違い偏りの出方が異なります.
uint32_t bounded_rand(rng_t& rng, uint32_t range)
{
double zeroone = 0x1.0p-32 * rng();
return range * zeroone;
}
次のものは, 32:32の固定小数点数で上の方法と同じことをしています. 偏りはありますが多くのシステムで最速になります. GPGPUで偏りが許容できるなら, これでもありかもしれません.
高速に計算しようとすると, 結果のビット数の倍精度を計算する命令が必要なので, システム依存になってしまいます.
uint32_t bounded_rand(rng_t& rng, uint32_t range)
{
uint32_t x = rng();
uint64_t m = uint64_t(x) * uint64_t(range);
return m >> 32;
}
バイアスなしの方法
私は[1]にある実装の中から, ポータビリティとパフォーマンスのバランスがよさそうなもの使っています.
次は, Lemire's Method[2]の32bit版になります.
uint32_t bounded_rand(rng_t& rng, uint32_t range)
{
uint32_t t = (-range) % range;
uint64_t m;
uint32_t l;
do {
uint32_t x = rng();
m = uint64_t(x) * uint64_t(range);
l = uint32_t(m);
} while (l < t);
return m >> 32;
}
まとめ
乱数関係の偏りについては, 大体計算式が間違っていることが多いように思います. スマートフォンゲームのガチャなど, エンジニアの技術力不足で偏っていることなどよくありますね.