Как найти период генератора псевдослучайных чисел?

[Kevsh]

Я использую метод мультипликативного датчика, то есть следующее число ищется как $x_{i+1}=(ax_i+b)\%M$. У генератора есть периодическая часть, до которой должна идти апериодическая часть. У моего генератора получается нулевая апериодическая часть, хотя такого быть по идее не может. Вот алгоритм, который я использую:
1)В цикле генерирую новое число по формуле;
2)Проверяю, есть ли это число в списке уже сгенерированных чисел. Если нет, то добавляю это число в список сгенерированных чисел. Если да, то выхожу из цикла;

Я думал, что будет как-то так:
1 3 2 6 7 9 0 2 6 7 9 0 2 6 7 9 0

То есть сначала идёт часть, которая не повторяется, а потом всё начинает повторяться с одним и тем же периодом. На деле получается так:
2 6 7 9 0 2 6 7 9 0 2 6 7 9 0
То есть всегда, при любых $a$, $b$ и $M$ я получаю генератор без апериодической части. С чем это может быть связано?

[nnosipov]

Kevsh в сообщении #1564866 писал(а):

То есть всегда, при любых $a$, $b$ и $M$ я получаю генератор без апериодической части.

Вот прямо при любых? Нельзя делать выводы лишь на основе нескольких опытов. Попробуйте взять $a$ и $M$ не взаимно простыми (например, $a=15$, $M=100$).

[Kevsh]

nnosipov
при ваших данных вообще длина получается равной единице. Если выбирать другие числа, то просто уменьшается длина периодической части. Апериодическая часть не появляется. Ещё более странным кажется факт, что критерий Пирсона у меня получается 99,9%.

-- 17.09.2022, 22:44 --

nnosipov
И, кстати, есть ощущение, что число, с которого начинается генерация, вообще не влияет на количество полученных чисел в периодической части.

[mihaild]

Kevsh в сообщении #1564871 писал(а):

при ваших данных вообще длина получается равной единице

Да ладно? Напишите последовательность при $x_0 = 1$, $a = 15$, $b = 0$, $M = 100$.

Kevsh в сообщении #1564871 писал(а):

Ещё более странным кажется факт, что критерий Пирсона у меня получается 99,9%

Критерий Пирсона для чего? Равновероятности получающихся значений? В этом ничего удивительного, они гарантированно встречаются с одинаковой частотой.

[Aritaborian]

Kevsh в сообщении #1564871 писал(а):

Апериодическая часть не появляется

Как это?

Используется синтаксис Matlab M

f[x_, a_, b_, m_] := Mod[a x + b, m]
NestList[f[#, 15, 0, 100] &, 1, 10]

Используется синтаксис Matlab M

{1, 15, 25, 75, 25, 75, 25, 75, 25, 75, 25}

[mihaild]

Aritaborian в сообщении #1564873 писал(а):

Странно надеяться на иное.

Не странно, оно зависит же.
Если $a = 2$, $b = 0$, $M = 6$, то при $x_0 = 1$ имеем период $2$, а при $x_0 = 3$ - период $1$.

[Aritaborian]

mihaild в сообщении #1564874 писал(а):

Не странно, оно зависит же.

Осознал самостоятельно, глупость убрал, гляжу, а вы уже подоспели ;-)

[Geen]

Kevsh в сообщении #1564866 писал(а):

Я думал, что будет как-то так

С чего бы вдруг, если ни одно число в сгенерированном списке не может повториться согласно описанию Вашего алгоритма?

[Kevsh]

Aritaborian
Да, действительно, вывел массив, программа действительно выдаёт период 2. Видимо, числа у меня хорошие подобраны. Просто странно, что в примере к выполнению ЛР апериодическая часть занимает процентов 20 последовательности, а у меня максимум пара элементов появляется, и то, если прям специально числа плохие подбирать. Допустим, в примере было так:
$a = 2387$

$b = 2391$

$M = 2387597$

$x_0 = 23485923405$

Получается 79629 чисел при периоде 61620. У меня получается 61621 число при периоде 61620. Странно.

Geen
Это просто для примера было, так, конечно, такой последовательности я не получал.

[nnosipov]

Kevsh в сообщении #1564878 писал(а):

Допустим, в примере было так:
$a = 2387$

$b = 2391$

$M = 2387597$

$x_0 = 23485923405$

Получается 79629 чисел при периоде 61620.

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

[Kevsh]

nnosipov
Понял, спасибо большое

[Евгений Машеров]

Если у Вас хороший генератор, с максимальным периодом, то есть a, b и M выбраны так, чтобы получился максимально возможный период M, то:
1. Апериодической части не будет.
2. Период от начального значения зависеть не будет.
Если генератор не с максимальным периодом, то он выдаёт не все возможные числа в этом диапазоне, и если дать на вход число из множества тех, которые не входят в выдаваемые в периоде, то будет апериодический участок, пока он не наткнётся на число из периодической выдачи и далее выдавать только из "периодических".

Что до определения периода - проще всего использовать схему "шаг вперёд, два шага... тоже вперёд". Запускаем два одинаковых генератора с равными начальными значениями. Один делает один шаг, второй два подряд. Замечаем первое совпадение, длина цикла равна числу итераций до второго совпадения.

[traffic_lights]

Инструкция Rdrand (как для IA-32, так и для x86-64) для генерации случайного числа при помощи внутреннего генератора случайных чисел доступна в процессорах Intel, начиная с архитектуры Ivy Bridge, и в процессорах AMD — начиная с модели Ryzen.

[TheRuinedMap]

Евгений Машеров в сообщении #1570695 писал(а):

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

Не обязательно. Генератор может разбивать диапазон на несколько циклов, каждый без апериодической части.

[B@R5uk]

Евгений Машеров в сообщении #1570695 писал(а):

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

Не очень надёжная схема. Если период кратен 2, то оба генератора будут синфазны, и совпадение просто не будет обнаружено.