18

[0, n)で乱数を選択する一般的な方法の 1 つは、rand()モジュロn :の結果を取得することですrand() % n。ただし、利用可能な実装によって返される結果が完全に均一であっても、 がnで均等に除算されない場合、結果の[0, n)数値rand()の均一性に問題があるのではないでしょうか? たとえば、2 でnが 2 だとします。3 つの可能な出力: 0、1、および 2 のうち、モジュロnを使用すると、それぞれ 0、1、および 0 が得られます。したがって、出力はまったく均一ではありません。RAND_MAX + 1RAND_MAXrand()

これは実際には実際の問題ですか？[0, n)で乱数を選択しrand()、できれば浮動小数点演算を使用せずに、出力から一様に導出するより良い方法は何ですか?

4

4 に答える 4

10

あなたは正しいです、rand() % N正確に均一に分布していません。それがどれだけ重要かは、必要な数値の範囲と必要なランダム性の程度によって異なりますが、気にするほど十分なランダム性が必要な場合は、とにかく使用したくありませrand()ん。実乱数ジェネレーターを取得します。

そうは言っても、本当のランダム分布を得るには、次の 2 の累乗に変更し、必要な範囲になるまでサンプリングします (たとえば、0 ～ 9 の場合は を使用しますwhile(n = rand()%0x10 > 10);)。

于 2012-10-27T22:03:07.707 に答える
7

それは以下に依存します:

  • RAND_MAX の値
  • あなたのNの値

RAND_MAX が 2^32 であると仮定しましょう。N がかなり小さい場合 (2 としましょう)、バイアスは 1 / 2^31 です。つまり、小さすぎて気付かないことになります。

しかし、N がかなり大きい場合、たとえば 2^20 の場合、バイアスは 1/2^12、つまり 4096 分の 1 になります。かなり大きいですが、それでもかなり小さいです。

于 2012-10-27T21:55:12.247 に答える
1

あなたができる1つのアプローチは次のとおりです。

の値を知ってNいればR_MAX = ((RAND_MAX + 1) / N) * N;、均一性が得られます。

rand()したがって、カスタム関数を実行できます。

int custom_rand(int mod) {
    int x = rand();
    const int R_MAX = ((RAND_MAX + 1) / mod) * mod;    

    while (x > R_MAX) { // discard the result if it is bigger
        x = rand();
    }

    return (x % mod);
}
于 2012-10-27T22:11:57.533 に答える
1

縮小された範囲で一様乱数に剰余 (% は C の「モジュロ」演算子ではない) を使用する場合、2 つの問題があります。1 つ目は、数値が小さい方へのわずかな偏り (前述) であり、2 つ目は、一般的な PRNG では下位ビットのランダム性が低い傾向があることです。Knuth (The Art of Computer Programming、Vol II、Seminumerical Algorithms) から、(MIX から C に翻訳した後) rand()%2 はランダムな単一ビットの貧弱なソースであるという主張とともに、それを思い出すようです。(rand() > RAND_MAX/2) を選択することをお勧めします (または、RAND_MAX が 2 の累乗に近い場合は、上位ビットをテストします)。

残りは、短い間隔でカジュアルに使用するのに十分なはずです。シミュレーションには使用しないでください。実際には、大規模なシミュレーションや「モンテカルロ」計算では rand() を完全に避けてください。実装では、周期が 2^32 以下のオーダーになる傾向があります。2 GHz 以上のプロセッサで 40 億回の試行を超えることは難しくありません。

于 2012-10-27T22:42:06.533 に答える