c++ - 高效 Xorshift 向前跳过

Question

我需要一个快速的随机数生成器，它允许我随机访问随机数序列中不同位置的数字。我选择了 Xorshift，因为它快速且易于实现。

为了从序列中得到一个特定的随机数，我实现了下面的方法(mPos保存了下一个随机数的位置):

void XorshiftRandomGenerator::skipTo(unsigned int pos)
{
    // Reset if we passed the position
    if (mPos>pos)
        reset();

    // Generate random numbers until we're done
    while (mPos<pos)
        random();
}

随后的 random() 将返回所需的数字，但此方法非常昂贵。有没有一种方法可以使用 Xorshift 跳过大量随机数，而无需计算其间的每个随机数？

作为替代方案，我可以使用另一个随机数生成器。你能推荐一个允许快速向前跳转的吗？​​

Answer 1

Forest B. Brown 在 1994 年发表了一篇名为 Random Number Generation with Arbitrary Strides 的论文其中广泛涉及该主题。

正如 Nabb 在评论中所述，线性同余生成器 可用于高效跳过。当然，通常的advantages and disadvantages液化天然气适用:事情简单而且速度极快，但伪随机数的质量不是很高。公式解释here详细点。