高效的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跳過

回答

相關問題