如何計算的線性同餘發生器

Question

根據Wikipedia，線性同餘發生器由下面的遞推關係式定義的k個最小的數：

X(n) = {a.X(n-1) + c} mod m 

其中0 < m，0 <= a < m，0 <= c < m，0 <= X(0) < m是整數指定生成器的常量。

如果價值a，c，m，X(0)和n給出，可我確定一套{X(0), X(1), ..., X(n)}非常快的k個最小值（1 <= k <= n）？ （比O(n)更快 - 基於由排序算法）

Answer 1

假設你生成期間不是在存儲k最低的項目...

如果(n >= m)和常數滿足一個完整週期（ref here）的標準，則k-最小的項目將是k-1。

如果(n >= m)和常量不符合標準或(n < m)那麼你需要做的，可以終止線性搜索，如果k迄今爲止最低的第是k-1。