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

Question

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

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

我希望避免必须播种并循环 n + 1 次才能获取下一个值。我想要的东西是否可以通过 rand 的通用 Linux 实现实现？

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。将数字求模 m 次幂与数字中的位数成线性关系，即 O(log(number))。要进行乘法逆运算，只需使用扩展欧几里得算法即可。后者只需执行一次。