30

Java の Random クラスを使用した乱数の生成で奇妙なことを発見しました。基本的に、近いシード (たとえば 1 から 1000 の間) を使用して複数の Random オブジェクトを作成すると、各ジェネレーターによって生成される最初の値はほぼ同じになりますが、次の値は問題ないように見えます (さらに検索しませんでした)。

0 から 9 までのシードを持つ、最初に生成された 2 つの double を次に示します。

  • 0 0.730967787376657 0.24053641567148587
  • 1 0.7308781907032909 0.41008081149220166
  • 2 0.7311469360199058 0.9014476240300544
  • 3 0.731057369148862 0.07099203475193139
  • 4 0.7306094602878371 0.9187140138555101
  • 5 0.730519863614471 0.08825840967622589
  • 6 0.7307886238322471 0.5796252073129174
  • 7 0.7306990420600421 0.7491696031336331
  • 8 0.7302511331990172 0.5968915822372118
  • 9 0.7301615514268123 0.7664359929590888

そして 991 から 1000 まで:

  • 991 0.7142160704801332 0.9453385235522973
  • 992 0.7109015598097105 0.21848118381994108
  • 993 0.7108119780375055 0.38802559454181795
  • 994 0.7110807233541204 0.8793923921785096
  • 995 0.7109911564830766 0.048936787999225295
  • 996 0.7105432327208906 0.896658767102804
  • 997 0.7104536509486856 0.0662031629235198
  • 998 0.7107223962653005 0.5575699754613725
  • 999 0.7106328293942568 0.7271143712820883
  • 1000 0.7101849056320707 0.574836350385667

そして、これは 0 から 100,000 までのシードで生成された最初の値を示す図です。

シードに基づいて生成された最初のランダム double :

画像

これに関する情報を検索しましたが、この正確な問題に言及しているものは何も見つかりませんでした。LCG アルゴリズムには多くの問題があることは知っていますが、これについては知りませんでした。これが既知の問題であるかどうか疑問に思っていました。

また、この問題が最初の値 (または最初のいくつかの値) のみで発生するのか、それともより一般的で近いシードを使用することを避けるべきなのかを知っていますか?

ありがとう。

4

4 に答える 4

20

ソースと疑似乱数発生器に関するいくつかの論文をダウンロードして読むのが最善ですがRandom、ソースの関連部分の一部を以下に示します。まず、アルゴリズムを制御する 3 つの定数パラメーターがあります。

private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48) - 1;

この分析では、乗数は約 2^34 になり、マスクは 2^48 - 1 になり、加数は 0 にかなり近くなります。

シードを使用して Random を作成すると、コンストラクターは以下を呼び出しますsetSeed。

synchronized public void setSeed(long seed) {
    seed = (seed ^ multiplier) & mask;
    this.seed.set(seed);
    haveNextNextGaussian = false;
}

ゼロにかなり近いシードを提供しているため、設定される初期シード値はmultiplier、2 つが OR されたときに支配されます。シードがゼロに近いすべてのテスト ケースでは、内部で使用されるシードはおよそ 2^34 です。しかし、非常に大きなシード数を指定した場合でも、同様のユーザー提供のシードが同様の内部シードを生成することは簡単にわかります。

最後のピースはnext(int)、現在のシードに基づいて要求された長さのランダムな整数を実際に生成し、シードを更新するメソッドです。

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

これは「線形合同」疑似乱数ジェネレーターと呼ばれ、現在のシードに定数乗数を掛けてから定数加数を追加することによって、連続する各シードを生成することを意味します (この場合、下位 48 ビットを取るようにマスキングします)。 . ジェネレーターの品質は乗数と加数の選択によって決まりますが、そのようなすべてのジェネレーターからの出力は、現在の入力に基づいて簡単に予測でき、繰り返す前に設定された期間があります (したがって、それらを敏感な場所で使用しないことをお勧めします)。アプリケーション)。

与えられた同様のシードから同様の初期出力が表示さnextDoubleれる理由は、次の整数の計算には乗算と加算のみが含まれるため、次の整数の大きさは下位ビットの違いの影響をあまり受けないためです。次の double の計算には、シードに基づいて大きな整数を計算し、それを別の (定数) 大きな整数で割ることが含まれます。結果の大きさは、ほとんどの場合、整数の大きさに影響されます。

次のシードの計算を繰り返すと、シードの下位ビットの差が拡大されます。これは、定数乗数による乗算が繰り返され、48 ビット マスクが毎回最上位ビットを捨てるためです。拡散さえ。

于 2012-09-05T15:04:55.377 に答える
4

私はこれを「問題」とは呼びませんでした。

また、この問題が最初の値 (または最初のいくつかの値) のみで発生するのか、それともより一般的で近いシードを使用することを避けるべきなのかを知っていますか?

連続する数値間の相関パターンは、暗号化されていない PRNG に共通の問題であり、これは 1 つの兆候にすぎません。相関 (厳密には自己相関) は、アルゴリズムの基礎となる数学に固有のものです。それを理解したい場合は、おそらく、Knuth の Art of Computer Programming Chapter 3 の関連部分を読むことから始める必要があります。

予測不可能性が必要な場合は、（真の）ランダムシードを使用する必要がありますRandom...またはシステムに「かなりランダムな」シードを選択させます。たとえば、引数なしのコンストラクターを使用します。またはさらに良いのは、代わりに実際の乱数ソースまたは暗号品質の PRNG を使用することですRandom。

記録のために：

  1. javadoc (Java 7) は、Random() 自体がどのようにシードされるかを指定していません。
  2. Linux 用の Java 7 での の実装はRandom()、ナノ秒クロックからシードされ、「一意化子」シーケンスで XOR されます。「uniquifier」シーケンスは、異なる乗数を使用する LCG であり、その状態は静的です。これは、シードの自己相関を回避することを目的としています...
于 2012-09-05T13:44:30.893 に答える
2

これは疑似ランダム シードのかなり典型的な動作です。完全に異なるランダム シーケンスを提供する必要はありません。同じシードを使用した場合に同じシーケンスを再び取得できるという保証のみを提供します。

この動作は、PRNG の数学的形式が原因で発生します。Java のものは線形合同ジェネレーターを使用するため、線形合同ジェネレーターの 1 ラウンドでシードを実行する結果が表示されます。これは、すべてのビット パターンを完全に混同するには不十分であるため、同様のシードに対して同様の結果が得られます。

あなたの最善の戦略は、おそらく非常に異なるシードを使用することです.1つのオプションは、現在使用しているシード値をハッシュしてこれらを取得することです.

于 2012-09-05T13:46:43.920 に答える
-1

ランダム シードを作成することにより (たとえば、シード生成のために System.currentTimeMillis() または System.nanoTime() でいくつかの数学関数を使用する)、より良いランダムな結果を得ることができます。詳細については、こちらもご覧ください。

于 2012-09-05T13:44:04.190 に答える