Предположим, я использую линейный конгруэнтный генератор псевдослучайных чисел (PRNG). Учитывая начальное число , коэффициент умножения (a), коэффициент сдвига (c) и коэффициент модуля (m), как я могу определить период моего PRNG? Я определяю это с помощью экспериментов / алгоритмов обнаружения паттернов, или есть прямая формула для расчета его периода? $x_0$

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

Если вы ограничиваете себя сжиженным газом полного цикла, то ответ прост, по определению это просто m . $m$

Чтобы найти период не полного цикла LCN PRNG для данного начального числа, вам просто нужно посчитать количество итераций PRNG, пока он не сгенерирует начальное значение еще раз.

Со ссылочной страницы википедии :

Продолжительность периода

Период общего LCG составляет не более $m$ , а для некоторых выборов гораздо меньше. При условии, что $c$ отлично от нуля, LCG будет иметь полный период для всех начальных значений, если и только если :

• $c$ и$m$ являютсявзаимно простыми,
• $a - 1$ делится на всепростые множителив$m$
• $a - 1$ кратно 4, если$m$ кратно 4.

Хотя LCG способны генерировать приличные псевдослучайные числа , это чрезвычайно чувствительно к выбору параметров $c$ , $m$ и $a$ .

Исторически неудачный выбор приводил к неэффективному внедрению LCG. Особенно показательным примером этого является RANDU, который широко использовался в начале 1970-х годов и привел ко многим результатам, которые в настоящее время подвергаются сомнению из-за использования этого плохого LCG.

Почему вы хотите использовать генератор полного цикла

Если вы не ограничиваете себя PRNG с полным циклом LCG, тогда вы берете на себя огромный риск .

Если вы не знаете, что данный LCG является полным циклом, то вы можете получить генератор с произвольным числом взаимно отличающихся друг от друга последовательностей, некоторые из которых могут быть смущающе маленькими и иметь ужасающую случайность, возможно, даже хуже, чем печально известный генератор RANDU ,

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

дальнейшее чтение

Чтобы получить отличную информацию о генераторах псевдослучайных чисел, я настоятельно рекомендую вам прочитать главу « Числовые рецепты», посвященную случайным числам.