View source for Full cycle

{{Short description|Behavior used in pseudorandom number generation}}
In a [[Pseudorandom number generator|pseudorandom number generator]] (PRNG), a '''full cycle''' or '''full period''' is the behavior of a PRNG over its set of valid states. In particular, a PRNG is said to have a full cycle if, for any valid [[Random seed|seed state]], the PRNG traverses every valid state before returning to the seed state, i.e., the period is equal to the cardinality of the state space.

The restrictions on the parameters of a PRNG for it to possess a full cycle are known only for certain types of PRNGs, such as [[Linear congruential generator|linear congruential generator]]s and [[Linear-feedback shift register|linear-feedback shift register]]s. There is no general method to determine whether a PRNG algorithm is full-cycle short of exhausting the state space, which may be exponentially large compared to the size of the algorithm's internal state.

==Example 1 (in C/C++)==
Given a random number seed that is greater or equal to zero, a total sample size greater than 1, and an increment [[Coprime integers|coprime]] to the total sample size, a full cycle can be generated with the following logic. Each nonnegative number smaller than the sample size occurs exactly once.

<source lang="cpp">
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;
}
</source>

==Example 1 (in Python)==
<source lang="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))
</source>

==See also==
* [[Linear congruential generator]]
* [[Xorshift]]

[[Category:Pseudorandom number generators]]

{{Sourceattribution|Full cycle}}