Полный цикл

В генераторе псевдордомов (PRNG) полный цикл или полный период - это поведение PRNG над его набором действительных состояний. В частности, PRNG, как говорят, имеет полный цикл, если для любого достоверного состояния семян PRNG пересекает каждое действительное состояние, прежде чем вернуться в состояние семян, то есть период равен кардинальности пространства штатов.

Ограничения на параметры PRNG, чтобы он обладал полным циклом, известны только для определенных типов PRNG, таких как линейные конгруэнтные генераторы и регистры смены линейной обратной связи . Не существует общего метода определения того, является ли алгоритм PRNG полным циклом, не хватает исчерпания пространства состояний, что может быть экспоненциально большим по сравнению с размером внутреннего состояния алгоритма.

Пример 1 (в C/C ++)

Учитывая случайное число семян, которое больше или равно нулю, общий размер выборки превышает 1, и увеличение доклада к общему размеру выборки может быть сгенерирован с помощью следующей логики. Каждое неотрицательное число меньше, чем размер выборки, происходит ровно один раз.

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;
}

Пример 1 (в 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))

Смотрите также