c++ - 範囲内の乱数をすばやく安全に判別

Question

* （包括的）から（排他的）の範囲内の乱数を迅速かつ安全に決定するにはどうすればよいですか？0r

言い換えれば、棄却サンプリングの最適化されたバージョン：

u32 myrand(u32 x)
{
    u32 ret = rand();

    while(ret >= x)
        ret = rand();

    return(ret);
}

*安全とは、一様分布を意味します。

Answer 1

結果を均一に分布させたい場合は、棄却サンプリングが最適です。よりスマートなことをするのは難しいことで有名です。たとえば、モジュロ演算子を使用すると、2の累乗ではない任意の数値の結果値の分布が不均一になります。

ただし、投稿するアルゴリズムは、不要な最上位ビットを破棄することで改善できます。（下記参照。）

これは、標準のJavaAPIが実装する方法Random.nextInt(int n)です。

public int nextInt(int n) {

    [...]

    if ((n & -n) == n)  // i.e., n is a power of 2
        return (int)((n * (long)next(31)) >> 31);

    int bits, val;
    do {
        bits = next(31);
        val = bits % n;
    } while (bits - val + (n-1) < 0);

    return val;
}

そして、コメンスであなたは読むことができます：

アルゴリズムは少し注意が必要です。不均一な分布になる値を拒否します（2 ^31はnで割り切れないため）。値が拒否される確率はnによって異なります。最悪のケースはn =2 ³⁰ +1であり、拒否の確率は1/2であり、ループが終了するまでの予想される反復回数は2です。

Answer 2

u32 myrand(u32 x)
{
    return rand() % (x+1);
}

質問が均等な配布を含むように変更されたため、これには次のようなものが必要になります。

u32 myrand(u32 x)
{
   assert(x <= RAND_MAX && x > 0);
   int numOfRanges = (RAND_MAX % x);
   int maxAcceptedRand = numOfRanges * x;
   int randNumber;
   do
   {
      randNumber = rand();
   }
   while(randNumber <= maxAcceptedRand);
   return number / numOfRanges;
}