3

我需要一个快速的随机数生成器，它允许我在随机数序列的不同位置随机访问数字。我选择了 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 跳过大量随机数，而不计算其间的每个随机数？

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

4

3 回答 3

2

Forest B. Brown 在 1994 年发表了一篇名为Random Number Generation with Arbitrary Strides的论文，该论文广泛讨论了这个主题。

正如 Nabb 在评论中所说，线性同余生成器可用于有效跳过。当然，液化天然气通常的优点和缺点也适用：事情简单且速度极快，但伪随机数的质量不是很高。公式在这里详细解释。

于 2015-02-13T12:35:18.970 回答
2

你当然可以跳入 xorshift，这里描述了这个过程，但我自己没有读过，所以我不知道它是多么容易遵循。

或者，您可以查看PCG，它通过使用底层 LCG（与@Daerst 的答案相同）提供跳转功能，但对其进行后处理以改善其统计属性，或者此处描述的一些可拆分生成器。例如，SplitMix 生成器只有一个常数的循环加法，因此要跳跃任意距离，您只需将跳跃距离乘以常数并加上（这里是一个显然通过 BigCrush 的 SplitMix 导数）。

于 2016-06-19T04:53:18.457 回答
1

您可以使用随机数生成器的层次结构。即，您使用生成器 A 生成的每个数字都用作生成器 B 的种子，生成器 B 会生成 100 个数字，然后再从 A 获取下一个数字以重新初始化自身并生成接下来的 100 个数字等。这样您可以分步向前跳过乘以 100。您当然可以将其级联到生成器树中。

于 2012-07-27T17:48:29.620 回答