Wie die k-ten kleinsten Nummer eines Kongruenzgenerator

Question

Nach Wikipedia ein Kongruenzgenerator durch die Rekursionsformel zur Berechnung unten definiert ist:

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

wo 0 < m, 0 <= a < m, 0 <= c < m, 0 <= X(0) < m integer sind Konstanten, die den Generator angeben.

Wenn der Wert von a, c, m, X(0) und n gegeben sind, kann ich den k-ten kleinsten Wert (1 <= k <= n) des Satzes {X(0), X(1), ..., X(n)} sehr schnell bestimmen? (Schneller als O(n) - Basis von Algorithmus Sortierung)

Answer 1

Angenommen, Sie sind nicht die k niedrigsten Gegenstände bei Erzeugung Speicherung ...

Wenn (n >= m) und die Konstanten erfüllen die Kriterien für eine volle Periode (ref here), dann die k -das kleinste Element wird k-1 sein.

Wenn (n >= m) und die Konstanten erfüllen nicht die Kriterien oder (n < m) dann müssen Sie eine lineare Suche tun, die, wenn die k-ten niedrigsten bisher k-1 ist beenden.