How to calculate the kth smallest number of a linear congruent generator

Question

According to Wikipedia , a linear congruent generator is defined by the recurrence relation below:

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

where 0 < m , 0 <= a < m , 0 <= c < m , 0 <= X(0) < m are integer constants that define the generator.

If the values a , c , m , X(0) and n , can I determine the k smallest value ( 1 <= k <= n ) for the set {X(0), X(1), ..., X(n)} really fast? (faster than O(n) - based on a sorting algorithm)

Answer 1

Assuming you don't save the smallest elements of k during generation ...

If (n >= m) and the constants satisfy the criteria of the full period ( here), then the k smallest element will be k-1 .

If (n >= m) and the constants do not meet the criteria or (n < m) , then you need to perform a linear search, which can end if k -th is the lowest before the date k-1 .