3

Linux で。srand() 関数があり、シードを指定すると、その後の random() 関数の呼び出しで同じシーケンスの疑似乱数が保証されます。

このシード値を覚えて、この疑似乱数シーケンスを保存したいとしましょう。

さらに、後でこの疑似乱数列の 100000 番目の数が必要だとしましょう。

1 つの方法は、srand() を使用してシード番号を指定し、次に random() を 10 万回呼び出して、この番号を記憶することです。

疑似乱数リスト内の他の 99,999 個の数字をすべてスキップして、リスト内の 100 番目の数字を直接取得するより良い方法はありますか。

ありがとう、

メートル

4

4 に答える 4

2

randどのプラットフォームにも実装するための定義済みの標準があるかどうかはわかりません。ただし、GNU Scientific Libraryからこれを選択します。

— ジェネレーター: gsl_rng_rand

これは BSD ランド ジェネレーターです。その序列は

x n+1 = (ax n + c) mod m

a = 1103515245、c = 12345、m = 2 31です。シードは初期値 x 1を指定します。この発生器の周期は 2 31で、発生器ごとに 1 ワードのストレージを使用します。

したがって、 x nを「知る」には、 x n-1を知る必要があります。私が見逃している明らかなパターンがない限り、その前のすべての値を計算せずに値にジャンプすることはできません。(しかし、必ずしもすべてのrand実装に当てはまるわけではありません。)

x 1から始めると...

  • x 2 = (a * x 1 + c) % m
  • x 3 = (a * ((a * x 1 + c) % m) + c) % m
  • x 4 = (a * ((a * ((a * x 1 + c) % m) + c) % m) + c) % m
  • x 5 = (a * (a * ((a * ((a * x 1 + c) % m) + c) % m) + c) % m) + c) % m

それはかなり早く手に負えなくなります。その関数は簡単に還元できますか? そうではないと思います。

(x n が x n -1に依存する系列の統計句があります-- 誰かその単語が何であるか思い出せますか?)

于 2010-05-04T21:53:30.807 に答える
1

お使いのシステムで利用できる場合は、 &rand_rの代わりに使用するか、および と一緒に使用できます。を引数として取り、その状態を格納します。何度も呼び出した後、この符号なし整数の値を保存し、次回の開始値として使用します。randsrandinitstatesetstaterandomrand_runsigned *rand_r

には、ではなくrandom()使用します。復元する状態の状態バッファーの内容を保存します。状態を復元するには、バッファを埋めて を呼び出します。バッファーが既に現在の状態のバッファーである場合は、への呼び出しをスキップできます。initstatesrandomsetstatesetstate

于 2010-05-04T22:20:49.007 に答える
1

rand()これは、BSD関数を使用して @Mark の回答から開発されました。

rand1()seedn 回ステップスルーすることにより、 から始まる n 番目の乱数を計算します。

rand2()ショートカットを使用して同じことを計算します。一度に 2^24-1 ステップまでステップアップできます。内部的には 24 ステップしか必要ありません。

BSD乱数ジェネレーターで十分な場合は、これで十分です。

#include <stdio.h>

const unsigned int m = (1<<31)-1;

unsigned int a[24] = {
    1103515245, 1117952617, 1845919505, 1339940641, 1601471041,
    187569281 , 1979738369, 387043841 , 1046979585, 1574914049,
    1073647617, 285024257 , 1710899201, 1542750209, 2011758593,
    1876033537, 1604583425, 1061683201, 2123366401, 2099249153,
    2051014657, 1954545665, 1761607681, 1375731713
};

unsigned int b[24] = {
    12345, 1406932606, 1449466924, 1293799192, 1695770928, 1680572000,
    422948032, 910563712, 519516928, 530212352, 98880512, 646551552,
    940781568, 472276992, 1749860352, 278495232, 556990464, 1113980928,
    80478208, 160956416, 321912832, 643825664, 1287651328, 427819008
};

unsigned int rand1(unsigned int seed, unsigned int n)
{
    int i;
    for (i = 0; i<n; ++i)
    {
        seed = (1103515245U*seed+12345U) & m;
    }
    return seed;
}

unsigned int rand2(unsigned int seed, unsigned int n)
{
    int i;
    for (i = 0; i<24; ++i)
    {
        if (n & (1<<i))
        {
            seed = (a[i]*seed+b[i]) & m;
        }
    }
    return seed;
}

int main()
{
    printf("%u\n", rand1 (10101, 100000));
    printf("%u\n", rand2 (10101, 100000));
}

線形合同ジェネレーターに適応することは難しくありません。適切な整数型 (Haskell) を使用して言語でテーブルを計算しましたが、数行のコードを追加するだけで、C で別の方法でテーブルを計算することもできました。

于 2010-05-04T23:43:50.083 に答える
0

常に 100,000 番目のアイテムが必要な場合は、後で保管しておいてください。

または、シーケンスを生成して保存し、後でインデックスを使用して特定の要素をクエリすることもできます。

于 2010-05-04T21:47:59.290 に答える