5

簡略化 (つまり、並行性を除外)すると、Random.next(int bits)次のようになります。

protected int next(int bits) {
    seed = (seed * multiplier + addend) & mask;
    return (int) (seed >>> (48 - bits));
}

マスキングを使用してシードを 48 ビットに減らします。なぜそれはただより良いのですか

protected int next(int bits) {
    seed = seed * multiplier + addend;
    return (int) (seed >>> (64 - bits));
}

? 私は乱数についてかなり読んだことがありますが、これには理由がありません。

4

4 に答える 4

5

その理由は、下位ビットがより低い期間を持つ傾向があるためです (少なくとも Java が使用するアルゴリズムでは)。

ウィキペディアから-線形合同ジェネレーター：

上に示したように、LCG は生成する値のすべてのビットを常に使用するとは限りません。Java の実装では、反復ごとに 48 ビットが生成されますが、これらの値から上位 32 ビットのみが返されます。これは、上位ビットが下位ビットよりも周期が長いためです (以下を参照)。この手法を使用する LCG は、使用しない場合よりもはるかに優れた値を生成します。

編集：

さらに読んだ後 (便利なことにウィキペディアで)、a、c、および m の値は、完全な周期を持つために次の条件を満たす必要があります。

  1. c と m は互いに素でなければなりません

  2. a-1 は m のすべての素因数で割り切れます

  3. m が 4 の倍数の場合、a-1 は 4 の倍数

私がはっきりと言えるのは、まだ満足しているのは＃3だけです。#1 と #2 をチェックする必要がありますが、どちらか (または両方) が失敗しているように感じます。

于 2011-04-07T23:51:01.057 に答える
2

java.util.Random の上部にあるドキュメントから:

  • アルゴリズムはThe Art of Computer Programming で説明されています。
  • セクション 3.2.1 の Donald Knuth による第 2 巻。これは 48 ビットのシードです。
  • 線形合同式。

したがって、アルゴリズム全体は、64 ビットのシードではなく、48 ビットのシードで動作するように設計されています。クヌースさんと一緒に取り上げていただけると思います ;p

于 2011-04-07T23:51:35.140 に答える
0

これを行う正当な理由があったようには見えません。マスクの適用は、実績のある設計を使用した保守的なアプローチです。それを省くことはおそらくより良いジェネレーターにつながるでしょう、しかし、数学をよく知らなければ、それは危険なステップです。

マスキングのもう1つの小さな利点は、8ビットアーキテクチャでは8バイトではなく6バイトを使用するため、速度が向上することです。

于 2011-04-20T02:55:15.190 に答える
0

ウィキペディアから(@ helloworld922 が投稿した引用によって言及された引用):

LCG のさらなる問題は、m が 2 の累乗に設定されている場合、生成されたシーケンスの下位ビットの周期がシーケンス全体よりもはるかに短いことです。一般に、基数 b 表現の n 番目の最下位桁は、ある整数 k に対して bk = m である場合、出力シーケンスの最大周期 bn で繰り返されます。

さらに、それは続きます (私のイタリック体):

m が 2 のべき乗である場合の LCG の下位ビットは、いかなる程度のランダム性についても信頼すべきではありません。実際、モジュラス項に 2n を代入するだけで、下位ビットが非常に短いサイクルを通過することがわかります。特に、m が 2 のべき乗である場合のフルサイクル LCG は、奇数と偶数の結果を交互に生成します。

結局のところ、その理由はおそらく歴史的なものです。Sun の人々は何かが確実に機能することを望んでおり、Knuth 式は 32 ビットの有効ビットを与えました。java.util.RandomAPI には次 のように記載されていることに注意してください(私のイタリック体):

Random の 2 つのインスタンスが同じシードで作成され、それぞれに対して同じ一連のメソッド呼び出しが行われた場合、それらは同一の数列を生成して返します。このプロパティを保証するために、特定のアルゴリズムがクラス Random に指定されています。Java 実装は、Java コードの完全な移植性のために、クラス Random に対してここに示されているすべてのアルゴリズムを使用する必要があります。ただし、クラス Random のサブクラスは、すべてのメソッドの一般規約に準拠している限り、他のアルゴリズムを使用することが許可されています。

そのため、参照実装としてこれにこだわっています。ただし、別のジェネレーターを使用できない (および Random をサブクラス化するか、新しいクラスを作成する) ことができないという意味ではありません。

同じウィキペディアのページから：

MMIX by ドナルド・クヌース m=2 64 a=6364136223846793005 c=1442695040888963407

あなたのための64ビット式があります。

(Knuth が指摘しているように) 乱数は注意が必要であり、必要に応じてjava.util.Random、64 ビットの数値が必要な場合は、2 回呼び出してビットを連結するだけで問題ない場合があります。本当に統計的性質を気にするならMersenne Twisterのようなものを使うか、情報漏洩・予測不可能性を気にするなら使ってみてくださいjava.security.SecureRandom。

于 2011-04-08T00:37:33.677 に答える