6

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#nextInt%28int%29言います:

アルゴリズムは少しトリッキーです。(2^31 は n で割り切れないため) 不均一な分布になる値は拒否されます。値が拒否される確率は、n によって異なります。最悪のケースは n=2^30+1 で、リジェクトの確率は 1/2 で、ループが終了するまでの予測反復回数は 2 です。

アルゴリズム:

int bits, val;
do {
    bits = next(31);
    val = bits % n;
} while (bits - val + (n-1) < 0);

n > 2^30このコードは、とのケースをテストしbits > nます。次に、最上位ビットが設定され、条件の結果が負の 1 になります。

bitsせいぜい2^31-1=>50％の確率があることを理解しています。bits< 2^30 または 2^30 ～ 2^31 のいずれかです。

ともかく、

  1. なぜ2^31 は n で割り切れないのですか?
  2. 両方の数値が > 2^30 の場合にのみ効果があるのはなぜですか?

二項除算の魔法、一様分布を破るオーバーフローだと思いますか？

ありがとうございました！

4

3 に答える 3

5

これは、小さな範囲のサイズが大きな範囲のサイズで割り切れない大きな範囲の乱数から小さな範囲の乱数を生成したい場合に常に発生する問題です。

0 から 9 (両端を含む) までの乱数があり、それを 0 から 3 の間の 1 に変更したい場合、これを n%4 として簡単に実行した場合、3/10 の確率で 0 ( 0、4 または 8)%4 ですが、3 (3 または 7)%4 を得る確率は 2/10 です。これを回避する最も簡単な方法は、乱数が 7 より大きい場合に乱数を再生成することです。

それが話している最悪のケースは、小さい範囲のサイズが大きい範囲のサイズの半分をわずかに超える場合です。そのため、半分強の時間で再生成する必要があります。

于 2013-11-12T13:12:18.450 に答える
1

2^31 はべき乗または 2 でのみ割り切れます。コードを確認すると、この特殊なケースはループなしで個別に処理されます。説明は拒否プロセスに関連しており、n は 2 のべき乗ではありません。

于 2013-11-12T13:10:27.553 に答える
0

最初の質問について：

文章を理解したところ、2^31がnで割り切れない場合に偏在が起こると言われています。

申し訳ありませんが、2番目の質問についてはわかりません。

于 2013-11-12T13:04:22.937 に答える