如何计算线性同余生成器的第k个最小数

Question

根据维基百科,线性同余生成器由下面的递归关系定义:

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给出,我能确定k个最小值(1 <= k <= n的)设置{X(0), X(1), ..., X(n)}非常快？(比O(n)基于排序算法的更快)

Answer 1

假设您在生成过程中没有存储k最低的项目......

如果(n >= m)和 常数满足完整周期的标准（请参阅此处），则k第一个最小的项目将是k-1。

如果(n >= m)和 常量不满足条件，或者(n < m)您需要进行线性搜索，如果k迄今为止的第一个最低值是，则可以终止k-1。