[解決済み] なぜrand()%6に偏りがあるのですか？

疑問点

std::randの使い方を読んでいたら、以下のようなコードが見つかりました。 cppreference.com

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

右の式は何が問題なのでしょうか？試してみましたが、完全に動作します。

どのように解決するのですか？

には2つの問題があります。 rand() % 6 (この 1+ はどちらの問題にも影響しません)。

まず、いくつかの回答で指摘されているように、もし下位ビットの rand() が適切に一様でない場合、余剰演算子の結果もまた一様ではありません。

次に、もし rand() が6の倍数でない場合、残りは高い値より低い値を多く生成します。これはたとえ rand() が完全に分散した値を返す場合でも同じです。

極端な例として rand() が一様な分布の値を生成するとします。 [0..6] . これらの値に対する余りを見てみると rand() が範囲内の値を返した場合 [0..5] の範囲にある値を返し、余りは [0..5] . このとき rand() は 6 を返します。 rand() % 6 は0を返します。 rand() が0を返した場合と同様に0を返します。つまり、他のどの値よりも2倍多くの0を持つ分布が得られます。

2つ目は リアル の問題です。 rand() % 6 .

その問題を回避する方法として を破棄することです。 の値で、一様でない重複を生成することです。以下である6の最大倍数を計算するのです。 RAND_MAX 以下である6の最大倍数を計算し、いつでも rand() がその倍数以上の値を返すたびにそれを拒否し、必要な回数だけ再び `rand() を呼び出します。

というわけで。

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

これは問題のコードの別の実装で、何が起こっているかをより明確に示すことを意図しています。