3

在 Linux 中。有一个 srand() 函数,您可以在其中提供一个种子,它会保证在随后对 random() 函数的后续调用中具有相同的伪随机数序列。

可以说,我想通过记住这个种子值来存储这个伪随机序列。

此外,假设我稍后想要这个伪随机序列中的第 100 个数字。

一种方法是使用 srand() 提供种子编号,然后调用 random() 10 万次,并记住该编号。

有没有更好的方法可以跳过伪随机列表中的所有 99,999 个其他数字,直接获取列表中的第 100 个数字。

谢谢,

4

4 回答 4

2

我不确定是否有rand在任何平台上实施的明确标准;但是,从GNU Scientific Library中选择这个:

— 生成器:gsl_rng_rand

这是 BSD rand 生成器。它的顺序是

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代替rand& srand,或使用initstateand setstatewith randomrand_r接受一个unsigned *作为参数,它存储它的状态。rand_r多次调用后,保存这个无符号整数的值,下次作为起始值。

对于random(),使用initstate而不是srandom。为要恢复的任何状态保存状态缓冲区的内容。要恢复状态,请使用并调用 填充缓冲区setstate。如果缓冲区已经是当前状态缓冲区,则可以跳过对setstate.

于 2010-05-04T22:20:49.007 回答
1

rand()这是使用 BSD功能从@Mark 的答案开发的。

rand1()seed通过逐步执行 n 次计算从 开始的第 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 回答