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その値は十分に離れています。

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してくださいdebugcn@gmail.com

編集
0

コメントを追加

0

関連記事

分類Dev

最近のVisualStudioの更新により、キーボードで閉じ中括弧を作成するために使用されるショートカットが導入されました。問題のあるコマンドを見つける方法は?

分類Dev

重複するセッションをマージします。セッションの終了値を見つけるにはどうすればよいですか?[カープーリングに似たリートコード]

分類Dev

Googleスプレッドシートの他の列よりも短い列の終わりにある値を持つ最後のセルを見つけるにはどうすればよいですか?

分類Dev

値を介してネストされたオブジェクトを検索するときに、完全なドット区切りのキーを見つけるにはどうすればよいですか?

分類Dev

リストに対してパンダ列のサブセットで一致する値を見つけるためのより高速な方法

分類Dev

Googleスプレッドシートで、非数値データの最頻値をどのように見つけることができますか?

分類Dev

E:64ビットシステムに32ビットOpenSSLをダウンロードしようとすると、パッケージlibssl-devが見つかりません

分類Dev

FORループを使用して欠落値を削除することにより、Rデータセットの列の平均を見つける

分類Dev

64ビットLinuxで32ビットバージョンのJavaへのパスを見つけるにはどうすればよいですか?

分類Dev

ビット操作を効率的に使用して、64ビット値の唯一のセットビットの位置を見つける方法は?

分類Dev

テストによって形成された行列の最大値を見つけるコードが必要

分類Dev

2 つの非常に類似したコード セットの結果が非常に異なる理由を見つけようとする初心者

分類Dev

通知によってトリガーされた、ラベルのテキストを変更しようとしたときに、オプションの値をアンラップしているときに予期せずnilが見つかりました

分類Dev

Googleスプレッドシートの値の範囲の間にある値を動的に見つける

分類Dev

ビット演算を使用して2つの数値のGCDを見つける次の関数はどのように機能しますか?

分類Dev

C ++コードをリントして、未使用の戻り値をすべて見つけるにはどうすればよいですか?

分類Dev

平均より下(または上)の値を見つける方法

分類Dev

ラケットでより効率的に最小値を見つける

分類Dev

次数中心性networkx値の辞書で最大値のキーを見つけるためのよりエレガントなソリューション?

分類Dev

O(n)時間よりも複雑な、ソートおよびシフトされた配列の最小値を見つける

分類Dev

ちょうど3除数で数値を見つけるためのより良いソリューション

分類Dev

ファイルを見つけてナビゲートするためのショートカットは機能しなくなりました

分類Dev

Javaを使用して2Dマトリックスの最初の最大要素を見つける必要がありますが、コードが思ったように機能しないようです。誰か助けてもらえますか?

分類Dev

Windows 7 64ビットで追加のプリンター32ビットドライバーのインストールに失敗すると、「選択したプリンタードライバーが見つかりません」というエラーが表示されます。どうすればよいですか?

分類Dev

シートのセル内の値に一致するGoogleスプレッドシートを見つけて、コードを実行します

分類Dev

64ビットのWindows7でルートキットを見つける方法はありますか?

分類Dev

Visual Studio 32ビットリンカーはどのようにして64ビットリンカーを見つけますか?

分類Dev

Googleスプレッドシートで基準の次の値を見つけるためのArrayformula

分類Dev

NumPyndArrayのブール値に基づいて最長の系列を見つけるためのより効率的なソリューション

Related 関連記事

  1. 1

    最近のVisualStudioの更新により、キーボードで閉じ中括弧を作成するために使用されるショートカットが導入されました。問題のあるコマンドを見つける方法は?

  2. 2

    重複するセッションをマージします。セッションの終了値を見つけるにはどうすればよいですか?[カープーリングに似たリートコード]

  3. 3

    Googleスプレッドシートの他の列よりも短い列の終わりにある値を持つ最後のセルを見つけるにはどうすればよいですか?

  4. 4

    値を介してネストされたオブジェクトを検索するときに、完全なドット区切りのキーを見つけるにはどうすればよいですか?

  5. 5

    リストに対してパンダ列のサブセットで一致する値を見つけるためのより高速な方法

  6. 6

    Googleスプレッドシートで、非数値データの最頻値をどのように見つけることができますか?

  7. 7

    E:64ビットシステムに32ビットOpenSSLをダウンロードしようとすると、パッケージlibssl-devが見つかりません

  8. 8

    FORループを使用して欠落値を削除することにより、Rデータセットの列の平均を見つける

  9. 9

    64ビットLinuxで32ビットバージョンのJavaへのパスを見つけるにはどうすればよいですか?

  10. 10

    ビット操作を効率的に使用して、64ビット値の唯一のセットビットの位置を見つける方法は?

  11. 11

    テストによって形成された行列の最大値を見つけるコードが必要

  12. 12

    2 つの非常に類似したコード セットの結果が非常に異なる理由を見つけようとする初心者

  13. 13

    通知によってトリガーされた、ラベルのテキストを変更しようとしたときに、オプションの値をアンラップしているときに予期せずnilが見つかりました

  14. 14

    Googleスプレッドシートの値の範囲の間にある値を動的に見つける

  15. 15

    ビット演算を使用して2つの数値のGCDを見つける次の関数はどのように機能しますか?

  16. 16

    C ++コードをリントして、未使用の戻り値をすべて見つけるにはどうすればよいですか?

  17. 17

    平均より下(または上)の値を見つける方法

  18. 18

    ラケットでより効率的に最小値を見つける

  19. 19

    次数中心性networkx値の辞書で最大値のキーを見つけるためのよりエレガントなソリューション?

  20. 20

    O(n)時間よりも複雑な、ソートおよびシフトされた配列の最小値を見つける

  21. 21

    ちょうど3除数で数値を見つけるためのより良いソリューション

  22. 22

    ファイルを見つけてナビゲートするためのショートカットは機能しなくなりました

  23. 23

    Javaを使用して2Dマトリックスの最初の最大要素を見つける必要がありますが、コードが思ったように機能しないようです。誰か助けてもらえますか?

  24. 24

    Windows 7 64ビットで追加のプリンター32ビットドライバーのインストールに失敗すると、「選択したプリンタードライバーが見つかりません」というエラーが表示されます。どうすればよいですか?

  25. 25

    シートのセル内の値に一致するGoogleスプレッドシートを見つけて、コードを実行します

  26. 26

    64ビットのWindows7でルートキットを見つける方法はありますか?

  27. 27

    Visual Studio 32ビットリンカーはどのようにして64ビットリンカーを見つけますか?

  28. 28

    Googleスプレッドシートで基準の次の値を見つけるためのArrayformula

  29. 29

    NumPyndArrayのブール値に基づいて最長の系列を見つけるためのより効率的なソリューション

ホットタグ

アーカイブ