12

範囲[rangeLow、rangeHigh]の一様分布から整数を選択すると思われるC関数を作成しました。これは宿題ではありません。私はこれを、楽しみのためにやっていることをいじくり回しているいくつかの組み込みシステムで使用しています。

私のテストケースでは、このコードは適切な分布を生成するように見えます。ただし、実装が正しいとは完全には確信していません。誰かが健全性チェックを行い、ここで何か間違ったことをしたかどうか教えてもらえますか？

//uniform_distribution returns an INTEGER in [rangeLow, rangeHigh], inclusive.
int uniform_distribution(int rangeLow, int rangeHigh)
{
    int myRand = (int)rand(); 
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int myRand_scaled = (myRand % range) + rangeLow;
    return myRand_scaled;
}
//note: make sure rand() was already initialized using srand()

PS私はこのような他の質問を検索しました。ただし、ランダムな浮動小数点数ではなく、ランダムな整数について説明している質問の小さなサブセットを除外することは困難でした。

4

4 に答える 4

13

rand（）が[0..RAND_MAX]の範囲で一様分布の値Iを生成し、[L、H]の範囲で一様分布の値Oを生成するとします。

Iが[0..32767]の範囲にあり、Oが[0..2]の範囲にあるとします。

提案された方法によると、O = I％3です。与えられた範囲には、I％3 = 0の10923番号、I％3 = 1の10923番号がありますが、I％3=2の10922番号しかないことに注意してください。したがって、あなたのメソッドはIからOに値を均一にマッピングしません。

別の例として、Oが[0..32766]の範囲にあるとします。

提案された方法によると、O = I％32767です。これで、I=0とI=32767の両方でO=0になります。したがって、0は他のどの値よりも2倍の可能性があります-あなたの方法は再び不均一です。

均一なマッピングを生成するための推奨される方法は次のとおりです。

  1. [L、H]の範囲のランダムな値を格納するために必要なビット数を計算します。

    unsigned int nRange =（unsigned int）H-（unsigned int）L + 1;
    unsigned int nRangeBits =（unsigned int）ceil（log（（double（nRange）/ log（2。））;

  2. nRangeBitsランダムビットを生成します

    これは、rand（）の結果を右にシフトすることで簡単に実装できます。

  3. 生成された数がHL以下であることを確認してください。そうである場合は、手順2を繰り返します。

  4. これで、Lを追加するだけで、生成された数をOにマップできます。

于 2012-07-25T08:27:22.900 に答える
10

一部の実装でrand()は、下位ビットに適切なランダム性を提供しなかったため、モジュラス演算子は非常にランダムな結果を提供しませんでした。その場合は、代わりにこれを試すことができます。

int uniform_distribution(int rangeLow, int rangeHigh) {
    double myRand = rand()/(1.0 + RAND_MAX); 
    int range = rangeHigh - rangeLow + 1;
    int myRand_scaled = (myRand * range) + rangeLow;
    return myRand_scaled;
}

この方法を使用rand()すると、Liorが指摘したようにバイアスが発生します。ただし、を計算するための背番号ジェネレーターを見つけることができれば、この手法は問題ありませんmyRand。考えられる候補の1つはですdrand48()。これにより、検出が非常に困難なものへのバイアスの量が大幅に減少します。

ただし、暗号的に安全なものが必要な場合は、rand()それ自体が暗号的に安全であると仮定して、Liorの回答に概説されているアルゴリズムを使用する必要があります（デフォルトのアルゴリズムはおそらくそうではないため、見つける必要があります）。以下は、Liorが説明したものの簡略化された実装です。ビットをカウントする代わりに、範囲が内RAND_MAXにあると想定し、適切な倍数を計算します。最悪の場合、アルゴリズムは、範囲内の数値に対する要求ごとに、平均して2回乱数ジェネレーターを呼び出すことになります。

int uniform_distribution_secure(int rangeLow, int rangeHigh) {
    int range = rangeHigh - rangeLow + 1;
    int secureMax = RAND_MAX - RAND_MAX % range;
    int x;
    do x = secure_rand(); while (x >= secureMax);
    return rangeLow + x % range;
}
于 2012-07-25T03:06:01.233 に答える
3

rand（）はあまり良くないことが知られていると思います。それはあなたが必要とする「ランダムな」データのどれだけ良いかによるだけです。

テストを作成してからカイ2乗値を計算して、均一なジェネレーターがどれだけ優れているかを確認できると思います。

http://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test

用途によっては（オンラインポーカーシャッフラーには使用しないでください）、LFSRを検討することもできます。

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

疑似ランダム出力が必要な場合は、より高速になる可能性があります。また、私はその主張を裏付けるのに十分な数学を研究していませんが、おそらくそれらは均一である可能性があります。

于 2012-07-25T02:11:40.030 に答える
1

配布エラーを修正するバージョン（Liorによって示される）は、rand（）によって返される上位ビットを含み、整数演算のみを使用します（それが望ましい場合）。

int uniform_distribution(int rangeLow, int rangeHigh)
{
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int copies=RAND_MAX/range; // we can fit n-copies of [0...range-1] into RAND_MAX
    // Use rejection sampling to avoid distribution errors
    int limit=range*copies;    
    int myRand=-1;
    while( myRand<0 || myRand>=limit){
        myRand=rand();   
    }
    return myRand/copies+rangeLow;    // note that this involves the high-bits
}

//注：rand（）がsrand（）を使用してすでに初期化されていることを確認してください

rangeこれは、よりもはるかに小さい場合はうまく機能するはずです。そうでない場合は、低ビットの点で適切な乱数ジェネレータではないRAND_MAX問題に戻ります。rand()

于 2012-07-25T20:34:45.643 に答える