6

このコードが一様分布の数値を生成するのはなぜですか？私はそれを理解するのにいくつかの困難があります。誰かが説明できますか？ありがとう。

int RandomUniform(int n) {  
  int top = ((((RAND_MAX - n) + 1) / n) * n - 1) + n;  
  int r;  
  do {  
    r = rand();  
  } while (r > top);  
  return (r % n);  
}

更新：rand（）％nが均一に分散されたシーケンスを提供しない理由を理解しています。私の質問はなぜ

top = ((((RAND_MAX - n) + 1) / n) * n - 1) + n;

ここでの懸念は何ですか？単純なtop=RAND_MAX / n*nで十分だと思います。

4

3 に答える 3

10

rand()この関数は、が均一に分布していることを前提としています。それが有効な仮定であるかどうかは、の実装に依存しますrand()。

が均一であるとすると、を計算するrand()ことで範囲内の乱数を取得できます。ただし、一般的に、これは完全に均一ではありません。たとえば、が3で7であるとします。[0,n)rand()%nnRAND_MAX

rand()      0 1 2 3 4 5 6 7
rand() % n  0 1 2 0 1 2 0 1

0と1は3/8の確率で発生しますが、2は2/8の確率でしか発生しないことがわかります。分布は均一ではありません。

コードは、生成できるrand()最大の倍数以上の値を破棄します。nこれで、各値の確率は等しくなります。

rand()      0 1 2 3 4 5 6 7
rand() % n  0 1 2 0 1 2 X X

したがって、ループが終了しないほど不運でない限り、0、1、および2はすべて1/3の確率で発生します。

アップデートについて：

単純なtop=RAND_MAX / n*nで十分だと思います。

RAND_MAX排他的境界（実際の最大値より1つ多い）である場合、それは正しいでしょう。これは包括的境界であるため、排他的境界を取得するには1つ追加する必要があります。次のロジック>は包括的境界と比較されるため、計算後にもう一度1を減算します。

int top = ((RAND_MAX + 1) / n) * n - 1;

ただし、RAND_MAXがに等しい場合INT_MAX、計算はオーバーフローします。これを回避するにnは、計算の最初に減算し、最後に再度加算します。

int top = (((RAND_MAX - n) + 1) / n) * n - 1 + n;
于 2013-02-04T15:45:40.590 に答える
7

my_rand()根本的な問題は次のとおりです。0から6までの値を生成する乱数ジェネレーターがあり、0から5までの値を生成したいとします。ジェネレーターを実行して戻るmy_rand() % 6と、一様分布は得られません。0をmy_rand()返すと、0になります。my_rand()1を返すと、 6を返すまで1などを取得します。その場合my_rand() % 6は0です。したがって、全体my_rand() % 6として、他の値の2倍の頻度で0を返します。これを修正する方法は、5より大きい値を使用しないことです。つまり、ループを作成して、大きすぎるmy_rand() % 5値を破棄する代わりに。my_rand()それは本質的に問題のコードが行っていることです。私はそれをたどっていませんが、通常の実装はの最大の倍数を計算することですnそれは、以下であり、その倍数より大きい値を返すときはRAND_MAXいつでも、戻って新しい値を取得します。rand()

于 2013-02-04T15:40:16.950 に答える
2

topを計算するコードをトレースしませんでしたが、返すことができるRAND_MAX最大の値です。より良い上限になりますが、たとえば、の場合、結果は予測できません。したがって、おそらくすべてのコードがオーバーフローを回避しようとしています。rand()(RAND_MAX + 1) / n * nRAND_MAXINT_MAX

于 2013-02-04T16:02:07.520 に答える