math - 创建一个随机序列，跳到序列的任何部分

Question

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

比方说，我想通过记住这个种子值来存储这个伪随机序列。

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

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

有没有更好的办法跳过伪随机列表中的所有其他99,999个数字，直接得到列表中的第100个数字。

谢谢，

米

Answer 1

我不确定在任何平台上是否存在用于实现 rand 的定义标准；然而，从 GNU Scientific Library 中挑选这个:

— Generator: gsl_rng_rand

This is the BSD rand generator. Its sequence is

x_n+1 = (a x_n + c) mod m

with a = 1103515245, c = 12345 and m = 2³¹. The seed specifies the initial value, x₁. The period of this generator is 2³¹, and it uses 1 word of storage per generator.

所以要“知道”x_n 需要您知道 x_n-1。除非我遗漏了一些明显的模式，否则你不能在不计算它之前的所有值的情况下跳转到一个值。 (但不一定是每个 rand 实现的情况。)

如果我们从 x₁...开始

• x₂ = (a * x₁ + c) % m
• x₃ = (a * ((a * x₁ + c) % m) + c) % m
• x₄ = (a * ((a * ((a * x₁ + c) % m) + c) % m) + c) % m
• x₅ = (a * (a * ((a * ((a * x₁ + c) % m) + c) % m) + c ) % m) + c) % m

它很快就会失控。该功能是否易于简化？我不这么认为。

_{(有一个序列的统计短语，其中 xn 取决于 xn-1 -- 谁能提醒我这个词是什么？)}