10

私は、C で乱数を取得するための歪みのない方法を見つけたいと思っています (ただし、せいぜい 0 ～ 20 の値に使用し、おそらく 0 ～ 8 のみに使用します)。この式を見たことがありますが、いくつかのテストを実行した後、それが歪んでいるかどうかはわかりません. 何か助けはありますか？

使用される完全な関数は次のとおりです。

int randNum() 
{ 
    return 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
}

次を使用してシードしました：

unsigned int iseed = (unsigned int)time(NULL);
srand (iseed);

以下に提案されているものは、私が試した私のために働くことを拒否します

int greek; 
for (j=0; j<50000; j++) 
{ 
greek =rand_lim(5); 
printf("%d, " greek); 
greek =(int) (NUM * (rand() / (RAND_MAX + 1.0))); 
int togo=number[greek]; 
number[greek]=togo+1; 
}

printfをコメントアウトすると、動作が停止し、同じ回数50000回になります。

4

1 に答える 1

16

はい、RAND_MAX がたまたま 10 の倍数でない限り、歪んでいます。

0 から RAND_MAX までの数字を 10 個の山に分割しようとすると、実際には 3 つの可能性しかありません。

  1. RAND_MAX は 10 の倍数で、山は均等に出てきます。
  2. RAND_MAX は 10 の倍数ではなく、パイルは不均一になります。
  3. 最初は不均一なグループに分割しますが、不均一にするすべての「余分なもの」を捨てます。

RAND_MAX を制御できることはめったになく、とにかく素数であることがよくあります。それは本当に可能性として2と3しか残していません。

3 番目のオプションは、おおまかに次のようになります。これにより、コードも簡素化されます (ほんの少し)。

int rand_lim(int limit) {
/* return a random number in the range [0..limit)
 */

    int divisor = RAND_MAX/limit;
    int retval;

    do { 
        retval = rand() / divisor;
    } while (retval == limit);

    return retval;
}

この方法がゆがみを残すのではないかと疑問に思われる方のために、純粋にテスト用にかなり異なるバージョンも作成しました。これは非常に限定された範囲を持つ明らかにランダムではないジェネレーターを使用するため、範囲内のすべての数値を単純に繰り返すことができます。次のようになります。

#include <stdlib.h>
#include <stdio.h>

#define MAX 1009

int next_val() {
    // just return consecutive numbers
    static int v=0;

    return v++;
}

int lim(int limit) {
    int divisor = MAX/limit;
    int retval;

    do {
        retval = next_val() / divisor;
    } while (retval == limit);

    return retval;
}

#define LIMIT 10

int main() {

    // we'll allocate extra space at the end of the array:
    int buckets[LIMIT+2] = {0};
    int i;

    for (i=0; i<MAX; i++)
        ++buckets[lim(LIMIT)];

    // and print one beyond what *should* be generated
    for (i=0; i<LIMIT+1; i++)
        printf("%2d: %d\n", i, buckets[i]);
}

そのため、0 から 1009 までの数字から始めます (1009 は素数であるため、選択した範囲の正確な倍数にはなりません)。つまり、1009 個の数字から始めて、10 個のバケットに分割します。これにより、各バケットに 100 が与えられ、残りの 9 個 (いわば) がdo/whileループによって「食べられ」ます。現在書かれているように、追加のバケットを割り当てて出力します。これを実行すると、バケット 0..9 のそれぞれで正確に 100 を取得し、バケット 10 で 0 を取得します。/ ループをコメントアウトするdoとwhile、0..9 のそれぞれで 100 が表示され、バケット 10 で 9 が表示されます。

念のために、生成された範囲 (主に素数を使用) とバケット数の両方について、他のさまざまな数値を使用してテストを再実行しました。doこれまでのところ、任意の範囲で歪んだ結果を生成することはできませんでした (もちろん/whileループが有効になっている限り)。

もう 1 つの詳細: このアルゴリズムで剰余ではなく除算を使用したのには理由があります。適切な（またはまともな）実装ではrand()無関係ですが、除算を使用して数値を範囲にクランプすると、入力の上位ビットが保持されます。剰余で行う場合は、入力の下位ビットを保持します。たまたま、典型的な線形合同疑似乱数ジェネレーターでは、下位ビットは上位ビットよりもランダム性が低くなる傾向があります。合理的な実装では、すでにいくつかの最下位ビットが破棄されているため、これは無関係になります。一方、randaround のかなり貧弱な実装がいくつかあり、ほとんどの場合それらのうち、剰余ではなく除算を使用することで、出力の品質が向上します。

また、大まかに反対のことを行うジェネレーターがあることも指摘しておく必要があります。下位ビットは上位ビットよりもランダムです。少なくとも私の経験では、これらは非常にまれです。上位ビットがよりランダムになるものは、かなり一般的です。

于 2012-04-18T23:11:19.330 に答える