64ビットLCGのより独立したシード値を見つける（MMIX（Knuthによる））
user1172131
64ビットLCG（MMIX（by Knuth））を使用しています。コード内に特定の乱数ブロックを生成し、それらを使用していくつかの操作を実行します。私のコードはシングルコアで動作し、実行時間を短縮するために作業を並列化したいと思います。
この意味でより高度な方法を考える前に、より多くの同一のコードを並行して実行したいと思います（実際、コードは特定の数の独立したシミュレーションで同じタスクを繰り返すので、シミュレーションの数をより多くのシミュレーションに分割できます同一のコードを並行して実行します）。
私の唯一の問題は、各コードのシードを見つけることです。特に、異なるコードで生成されたデータ間の望ましくない重要な相関の可能性を回避するために、さまざまなコードで生成された乱数が重複しないようにする必要があります。そうするために、最初のコードの特定のシードから始めて、絶対値ではなく疑似ランダムシーケンスで非常に離れた値（次のシード）を見つける方法を見つける必要があります（つまり、最初のシードから2番目のシードまで、LCGの膨大な数のステップが必要です）。
私の最初の試みはこれでした：
シーケンスで生成された2つの連続した数の間のLCG関係から始めます
したがって、原則として、たとえばn = 2 ^ 40およびI_0が最初のシードの値に等しい場合に上記の関係を計算し、最初のシードからランダムCLGシーケンスで2 ^ 40ステップ離れた新しいシードを取得できます。 。
問題は、そうすることで、a ^ nを計算してオーバーフローする必要があるということです。実際、MMIX（Knuthによる）a〜2 ^ 62の場合、unsigned long long int（64ビット）を使用します。ここでの唯一の問題は、上記の関係の分数であることに注意してください。合計と乗算しかない場合は、次のモジュラープロパティによるオーバーフローの問題を無視できます（実際、c（64ビットジェネレーター）として2 ^ 64を使用しています）。
それで、特定の値（最初のシード）から始めて、LC疑似ランダムシーケンスの膨大な数のステップから離れた2番目の値をどのように見つけることができますか？
r3mainer
フォームのLCGは、x[n+1] = (x[n] * a + c) % m任意の位置にすばやくスキップできます。
ゼロのシード値から始めて、LCGの最初の数回の反復で次のシーケンスが得られます。
x₀ = 0
x₁ = c % m
x₂ = (c(a + 1)) % m
x₃ = (c(a² + a + 1)) % m
x₄ = (c(a³ + a² + a + 1)) % m
各項が実際には等比数列の合計であることが非常に簡単にわかります。これは簡単な式で計算できます。
x_n = (c(a^{n-1} + a^{n-2} + ... + a + 1)) % m
= (c * (a^n - 1) / (a - 1)) % m
(a^n - 1)用語により迅速に算出することができるべき乗剰余が、で除算する(a-1)ので、ビットトリッキーである(a-1)とm我々は計算できないので、両方であっても（すなわち、互いに素ではない）であるモジュラ逆数の(a-1) mod m直接の。
代わりに、を計算して(a^n-1) mod m*(a-1)から、結果の単純な（非モジュラー）除算を実行しa-1ます。Pythonでは、計算は次のようになります。
def lcg_skip(m, a, c, n):
# Calculate nth term of LCG sequence with parameters m (modulus),
# a (multiplier) and c (increment), assuming an initial seed of zero
a1 = a - 1
t = pow(a, n, m * a1) - 1
t = (t * c // a1) % m
return t
def test(nsteps):
m = 2**64
a = 6364136223846793005
c = 1442695040888963407
#
print("Calculating by brute force:")
seed = 0
for i in range(nsteps):
seed = (seed * a + c) % m
print(seed)
#
print("Calculating by fast method:")
# Calculate nth term by modular exponentiation
print(lcg_skip(m, a, c, nsteps))
test(1000000)
したがって、出力シーケンスが重複しないLCGを作成するには、によって生成された初期シード値を使用するだけlcg_skip()で、nその値は十分に離れています。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
関連記事
Related 関連記事
- 1
最近のVisualStudioの更新により、キーボードで閉じ中括弧を作成するために使用されるショートカットが導入されました。問題のあるコマンドを見つける方法は？
- 2
重複するセッションをマージします。セッションの終了値を見つけるにはどうすればよいですか？[カープーリングに似たリートコード]
- 3
Googleスプレッドシートの他の列よりも短い列の終わりにある値を持つ最後のセルを見つけるにはどうすればよいですか？
- 4
文字列の列を使用して別のシートで同じ文字列を検索し、シート1の対応する値を見つかった値の横に貼り付けるにはどうすればよいですか？
- 5
最大合計値まで適合するように繰り返し可能な値のセットを見つけるためのアルゴリズム
- 6
値を介してネストされたオブジェクトを検索するときに、完全なドット区切りのキーを見つけるにはどうすればよいですか？
- 7
リストに対してパンダ列のサブセットで一致する値を見つけるためのより高速な方法
- 8
Googleスプレッドシートで、非数値データの最頻値をどのように見つけることができますか？
- 9
FORループを使用して欠落値を削除することにより、Rデータセットの列の平均を見つける
- 10
テストによって形成された行列の最大値を見つけるコードが必要
- 11
E：64ビットシステムに32ビットOpenSSLをダウンロードしようとすると、パッケージlibssl-devが見つかりません
- 12
Googleスプレッドシートで重複値が最初に発生したまま、セルの範囲で重複値を見つけて削除するにはどうすればよいですか？
- 13
64ビットLinuxで32ビットバージョンのJavaへのパスを見つけるにはどうすればよいですか？
- 14
ビット操作を効率的に使用して、64ビット値の唯一のセットビットの位置を見つける方法は？
- 15
通知によってトリガーされた、ラベルのテキストを変更しようとしたときに、オプションの値をアンラップしているときに予期せずnilが見つかりました
- 16
2 つの非常に類似したコード セットの結果が非常に異なる理由を見つけようとする初心者
- 17
Googleスプレッドシートの値の範囲の間にある値を動的に見つける
- 18
繰り返しなしでセットのバリエーションを見つけるためのアルゴリズムをC ++で作成するにはどうすればよいですか（つまり、n個の要素、kを選択）？
- 19
ビット演算を使用して2つの数値のGCDを見つける次の関数はどのように機能しますか？
- 20
C ++コードをリントして、未使用の戻り値をすべて見つけるにはどうすればよいですか？
- 21
平均より下（または上）の値を見つける方法
- 22
ラケットでより効率的に最小値を見つける
- 23
次数中心性networkx値の辞書で最大値のキーを見つけるためのよりエレガントなソリューション？
- 24
O（n）時間よりも複雑な、ソートおよびシフトされた配列の最小値を見つける
- 25
ちょうど3除数で数値を見つけるためのより良いソリューション
- 26
Javaを使用して2Dマトリックスの最初の最大要素を見つける必要がありますが、コードが思ったように機能しないようです。誰か助けてもらえますか？
- 27
javascriptで指定されたビットの値を見つける
- 28
ファイルを見つけてナビゲートするためのショートカットは機能しなくなりました
- 29
シートのセル内の値に一致するGoogleスプレッドシートを見つけて、コードを実行します
コメントを追加