10

範囲内の全期間または全サイクルを「占める」疑似乱数/順列を生成したいと思います。通常、「線形合同法」（LCG）を使用して、次のような式を使用してこのようなシーケンスを生成できます。

X = (a*Xs+c) Mod R

Xsがシード、Xが結果、aとcが互いに素の定数、Rが最大（範囲）です。

（全期間/全サイクルとは、任意のXがランダム/順列シーケンスで1回だけ発生し、0からR-1または1からRの範囲内になるように定数を選択できることを意味します）。

LCGは私のニーズのほとんどすべてを満たしています。私がLCGで抱えている問題は、奇数/偶数の結果がランダムでないことです。つまり、シードXnの場合、結果Xは奇数/偶数を交互に繰り返します。

質問：

  1. 奇数/偶数を交互にしない類似のものを作成する方法を知っている人はいますか？

  2. 「複合LCG」を構築できると思いますが、詳細はわかりません。誰かがこのCLCGの例を挙げてもらえますか？

  3. 上記の詳細と以下の制約を満たす可能性のある代替式はありますか？

制約：

  1. 単純なシードベースの式に基づいたものが欲しいです。つまり、次の番号を取得するために、シードを提供し、並べ替えられたシーケンスで次の「乱数」を取得します。具体的には、事前に計算された配列を使用できません。（次のポイントを参照）
  2. シーケンスは絶対に「フル期間/フルサイクル」である必要があります
  3. 範囲Rは、数百万、さらには32ビット/4億になる可能性があります。

  4. 計算はオーバーフローを起こさず、効率的/高速である必要があります。つまり、大きな指数や数十の乗算/除算がないことです。

  5. シーケンスは、ひどくランダムまたは安全である必要はありません-暗号化されたランダム性は必要ありません（ただし、実行可能な場合は使用できます）。奇数/偶数シーケンスなしで、「良好な」ランダム性または見かけのランダム性だけです。

どんな考えでもありがたいです-事前に感謝します。

更新：理想的には、範囲変数は正確な2の累乗ではない可能性がありますが、どちらの場合でも機能するはずです。

4

6 に答える 6

10

些細な解決策。R必要な範囲よりもやや大きい素数で LCG を作成し、その範囲内aのcどこかでランダムにします。必要以上の数値が得られた場合は、範囲内に戻るまで繰り返します。

数値出力には、使用する素数よりも小さい素数まで、2、3、5 などを法とする特に単純なパターンはありません。

必要な範囲が大きい場合、最も近い大きな素数はわずかに大きくなるため、2 回呼び出す必要はほとんどありません。たとえば、希望する範囲が 10 億の場合、素数として 1000000007 を使用でき、0.000001% 未満の時間で余分な数値をスキップする必要があります。

http://primes.utm.edu/curios/includes/primetest.phpにアクセスし、素数になるまで数字を入力して、この素数を見つけました。私は少し幸運でした。nで終わるオッズ1, 3, 7, 9は2.5/log(n)、約 10 億で約 12% であり、わずか 4 回の試行でこの数字を見つけることができたのは幸運でした。しかし、それほど幸運ではありませんでした.3回の試行で見つけたので、平均して8回必要だったはずです.

編集:この乱数ジェネレーターは、より短いサイクルを持つことができます。@dzugaru のメモを参照してください。

于 2011-06-10T01:50:36.803 に答える
3

奇数/偶数の交代が唯一の問題である場合は、状態変化の計算を変更しないでください。各出力を使用する前に、下位ビットをシフトアウトするか、ビットを入れ替えることができます。

編集：

ビットスワッピング（固定パターン）バリアントを使用すると、期間全体を生成し続けることができます。

初期LCGの擬似コード：

function rand
   state := update(state)
   return state

スワッピングを含むLCGの擬似コード：

function rand2
   state := update(state) -- unchanged state computation
   return swapped(state)  -- output swapped state
于 2010-08-27T11:48:42.197 に答える
2

もう1つの簡単で効率的でよく理解されているPRNGは、線形フィードバックシフトレジスタです。記事の手順に従って、全期間を簡単に達成できます。

編集：

フォーマット保存暗号化のために開発された技術のいくつかを検討するかもしれません。これらは順列を生成するために容易に適応できると私は信じています。

于 2010-08-27T12:13:11.317 に答える
2

暗号強度が必要ないからといって、暗号からいくつかのアイデアを借りることができないというわけではありません... Feistel ネットワーク (Luby-Rackoff 構築) のように。

ウィキペディアの写真はかなり明確です。

シンプルで高速な F を選択した場合 (一意の出力を保証する必要さえありません)、シーケンス (0、1、2、...、2^n-1) をいくつかのラウンドにフィードするだけです。 Feistel ネットワーク。構造は可逆であるため、出力が繰り返されないことが保証されます。

32 ビットのサンプル コード:

#include <stdint.h>
#include <stdio.h>

/* Just some fixed "random" bits... */
union magic {
    double d;
    uint16_t n[4];
};

const union magic bits = { 3.141592653589793238462643383 };

static uint16_t
F(uint16_t k, uint16_t x)
{
    return 12345*x + k;
}

static uint32_t
gen_rand(uint32_t n)
{
    uint16_t left = n >> 16;
    uint16_t right = n & ((1UL << 16) - 1);

    for (unsigned round=0 ; round < 4 ; ++round) {
        const uint16_t next_right = left ^ F(bits.n[round], right);
        const uint16_t next_left = right;
        right = next_right;
        left = next_left;
    }

    return (((uint32_t)left) << 16) + right;
}

int
main(int argc, char *argv[])
{
    for (uint32_t n = 0 ; n < 10 ; ++n) {
        printf("gen_rand(%lu) == %08lx\n", (unsigned long)n,
               (unsigned long)gen_rand(n));
    }
    return 0;
}

F() の定義やラウンド数などは好みに合わせて変更できます。そこで何を使っても「フルサイクル」の性質が保証されています。つまり、main0 から 2^32-1 までのループがある場合、F やラウンド数に何を使用するかに関係なく、各 32 ビット整数は 1 回だけ発生します。

gen_randへの入力は「現在の乱数」ではないため、これは指定された要件を正確には満たしていません...入力は次の整数です。ただし、これにより、シーケンスの任意の要素を自由に生成できます (ランダム アクセス)。また、本当に「現在の乱数」を入力として渡したい場合は、簡単に反転できます。

R が 2 の累乗である必要がありますが、さまざまなビット数に適応するのは非常に簡単です。

于 2011-06-15T21:35:33.350 に答える
1

次のリンクでは、LCG を組み合わせた例を見つけることができます。(ドキュメントとソースが含まれています) (注: アルゴリズムはオープンですが、ソースのライセンスはオープンではありません (つまり、派生コードはありません))

http://resource.npl.co.uk/docs/science_technology/scientific_computing/ssfm/documents/wh_rng_version096.zip

次の 7 段階の XORshift RNG の例を試すこともできます。

https://gist.github.com/709285

于 2010-12-12T01:37:04.147 に答える