c++ - 给定种子和偏移量，生成下一个伪随机值

Question

对于给定的实现，是否有可能rand在给定初始种子和rand到目前为止的调用次数的情况下有效地生成序列中的下一个数字？

我想要的是用来rand为模拟中的节点提供时间偏移。每个节点都将以其唯一的 id 作为种子，并使用 的输出rand来提供模拟延迟中的抖动。我希望每个节点都能够计算任何其他节点的下一个延迟以测量碰撞。我可以访问任何节点的初始种子并且rand已调用次数。

我想避免不得不播种和循环n + 1时间来获得下一个值。使用通用的 linux 实现，我想要什么rand？

Answer 1

glibc 中的随机数生成器是一个线性同余生成器，一个形式为 x_{n+1} = a * x_{n} + b mod m 的生成器。对于 a、b 和 m 的正确选择，它可能就足够了。结合两个或更多提高质量。

以这样的顺序向前跳过是相当容易的。x_{n+k} = a^{k} * x_{n} + b * (a^{k} - 1)/(a - 1) mod m。将一个数提高到一个 mod m 的幂与该数中的位数成线性关系，即 O(log(number))。要进行乘法逆运算，您只需使用扩展的欧几里得算法。您只需执行后者一次。