Полный цикл - Full cycle

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

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

Пример 1 (на C / C ++)

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

беззнаковый int семя = 0;беззнаковый int размер образца = 3000;беззнаковый int сгенерированное_число = семя % размер образца;беззнаковый int приращение = 7;за (беззнаковый int итератор = 0; итератор < размер образца; ++итератор){    сгенерированное_число = (сгенерированное_число + приращение) % размер образца;}

Пример 1 (на Python)

# Генератор, который проходит полный циклdef цикл(семя: int, размер образца: int, приращение: int):    nb = семя    за я в классифицировать(размер образца):        nb = (nb + приращение) % размер образца        урожай nb# Примеры значенийсемя = 17размер образца = 100приращение = 13# Вывести все числаРаспечатать(список(цикл(семя, размер образца, приращение)))# Убедитесь, что все числа были сгенерированы правильноутверждать набор(цикл(семя, размер образца, приращение)) == набор(классифицировать(размер образца))

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