9

Java でマップ ジェネレーターを作成しているときに、2 つの RNG のシードが非常に似ている (小さな整数が異なる) 場合、それらの最初の出力値が非常に似たものになるという、乱数ジェネレーターに関するやや厄介な問題を発見しました。

コード例:

Random r = new Random();
long n = 100000; //Choose any number
r.setSeed(n);  
System.out.println(r.nextInt());
r.setSeed(n+1);
System.out.println(r.nextInt());

座標を使用してマップ ジェネレーターをシードしているため、これは元の Java RNG に対する私の信頼をほとんど壊してしまいました。誰かがRandom.next(int bits)メソッドの再定義、またはこの問題の他の修正を提案できますか?

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

4

4 に答える 4

9

100000 と 100001 から取得した最初の ~20 個の値のシーケンスを比較しましたか?

これらは、シード 100000 および 100001 それぞれの最初の 20 の nextInt です。3 列目に異なるビットの量 (2 間の xor のビット数)

この最後の列は 16 前後のままである必要があります

-1986972922 -1987357671 13
-1760380366 -604895790  16
-1057894078 -329706441  15
-363772240  -1218064509 15
1545317691  -300240831  14
271304166   -900428132  21
1208561582  273461468   16
-1257783052 1069490639  16
-1549884799 40157720    15
-1514737808 -1818800021 17
-1030569735 1859508545  15
1310070992  880402584   18
-1513092400 971613287   19
-1993219517 354161779   16
-10847170   -204018237  15
-965377044  1488135032  14
802471291   1094582308  22
-539776032  -1021376555 15
2088199751  2070302462  12
-1271582124 64627614    19

3〜5回の繰り返しの後、彼はあまり似ていません

標準の Random に加えて、線形合同 RNG を実装します。これは、存在する最高の疑似乱数実装ではないが、メモリで最も効率的であることが知られています (1 期間で 1 つの 64 ビット ワードのみ2^48) 。

関心のある乗数は0x5deece66dLであり、c は0xbL

于 2011-05-28T20:15:08.860 に答える
2

2 つのシード (PRNG 状態) は、最下位ビットのみが異なります。PRNG は通常、いくつかの xor-ing とシフトを行うだけであることを考えると、これはそれほど驚くべきことではありません。

Randomとにかく、このように使用するべきではありません。PRNG の状態は、メソッドごとに更新されます (状態 / シードは、利用可能な 48 ビットの約 50 % だけ変化します) nextInt。あなたが気にする必要があるのはそれだけです。

于 2011-05-28T19:57:59.697 に答える
1

私が理解しているように、同じシードが与えられたときにいつでもシーケンスを再生成できるように、計算されたシードに依存する一連の乱数が必要です。そうですか？

類似のシードによって生成された乱数列は、最初は類似していますが、すぐに発散します。最初の k 個の値をスキップするだけで、ニーズにより適した結果が得られる場合があります。ここで、k は、シーケンスの非類似度と計算速度の必要性に応じて決定する必要がある数値です。

于 2011-05-28T20:05:27.397 に答える
0

java.security.SecureRandomは、質問に記載されているような問題に対処するために導入されjava.util.Random ました。 SecureRandom同じ予測可能性を示しません (少なくとも、露骨に明白ではありません)。前者は後者のサブクラスであるため、SecureRandom代わりにコードでを使用することで問題を解決できます。Random

Randomこの問題が発見された後、Sun はなぜ修正しなかったのかと疑問に思う人もいるかもしれません。その理由は後方互換性のためですRandom。任意のシードによって生成された特定の疑似乱数シーケンスに依存する既存のコードが壊れるため、 の動作を変更できませんでした。

于 2011-05-28T20:25:12.583 に答える