高效的Xorshift跳过

我需要一个快速的随机数发生器，它允许我随机访问随机数序列中不同位置的数字。我选择了Xorshift，因为它快速且易于实施。高效的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跳过大量的随机数，而不计算它们之间的每个随机数？

作为另一种选择，我可以与另一个随机数发生器。你能建议一个允许快速跳过吗？

来源

2012-07-27 Daerst

我认为一个线性同余发生器应该让你相当容易地跳过（即在对数时间）。 – Nabb 2012-07-29 14:45:36

森林B.布朗有一本1994年的论文，名为Random Number Generation with Arbitrary Strides，它广泛涉及这个主题。

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

来源

2015-02-13 12:35:18 Daerst

您可以使用随机数生成器的层次结构。即你用发电机A产生的每个数字都被用作发电机B的种子，它产生100个数字，然后它从A的下一个数字重新初始化自己并产生接下来的100个数字等等。这样，你可以跳过你当然可以把它串联成一个发电机组。

来源

2012-07-27 17:48:29 x4u

伟大的提示，谢谢！不过，我想知道是否有一种数学方法可以跳过Xorshift，或者是为快速跳过而设计的RNG。 – Daerst 2012-07-27 20:26:49

你当然可以在xorshift中跳转，这个过程被描述为here，但是我没有为自己读过，所以我不知道它是多么容易遵循。

或者，你可以看看PCG通过使用底层LCG（同@ Daerst的答案），但后处理它来改善其统计性质，或一些可裂发电机的描述here提供了一个跳跃功能。例如，SplitMix生成器只有一个常量的循环加法，所以要跳过任意距离，只需要将跳跃距离乘以常数，然后加上（here的SplitMix派生物，它似乎通过了BigCrush）。

来源

2016-06-19 04:53:18 sh1

高效的Xorshift跳过

回答

相关问题