Voller Zyklus - Full cycle

In einem Pseudozufallszahlengenerator (PRNG) ist ein vollständiger Zyklus oder eine vollständige Periode das Verhalten eines PRNG über seinen Satz gültiger Zustände. Insbesondere wird ein PRNG gesagt einen vollen Zyklus haben , wenn für jeden gültigen Samens Zustand durchläuft der PRNG jeden gültigen Zustand vor dem Samen Zustand zurückkehrt, das heißt, ist der Zeitraum , bis die Kardinalität des Zustandsraumes gleich.

Die Einschränkungen der Parameter eines PRNG, damit es einen vollständigen Zyklus besitzt, sind nur für bestimmte Arten von PRNGs bekannt, wie z. B. lineare Kongruenzgeneratoren und lineare Rückkopplungsschieberegister . Es gibt keine allgemeine Methode, um zu bestimmen, ob ein PRNG-Algorithmus den Zustandsraum nicht vollständig erschöpft, was im Vergleich zur Größe des internen Zustands des Algorithmus exponentiell groß sein kann.

Beispiel 1 (in C / C ++)

Bei einem Zufallszahlen-Startwert, der größer oder gleich Null ist, einer Gesamtstichprobengröße größer als 1 und einem inkrementellen Koprime zur Gesamtstichprobengröße kann ein vollständiger Zyklus mit der folgenden Logik generiert werden. Jede nicht negative Zahl, die kleiner als die Stichprobengröße ist, kommt genau einmal vor. 

unsigned int seed = 0;
unsigned int sample_size = 3000;
unsigned int generated_number = seed % sample_size;
unsigned int increment = 7;

for (unsigned int iterator = 0; iterator < sample_size; ++iterator)
{
    generated_number = (generated_number + increment) % sample_size;
}

Beispiel 1 (in Python) 

# Generator that goes through a full cycle
def cycle(seed: int, sample_size: int, increment: int):
    nb = seed
    for i in range(sample_size):
        nb = (nb + increment) % sample_size
        yield nb

# Example values
seed = 17
sample_size = 100
increment = 13

# Print all the numbers
print(list(cycle(seed, sample_size, increment)))

# Verify that all numbers were generated correctly
assert set(cycle(seed, sample_size, increment)) == set(range(sample_size))

Siehe auch