2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 20:52 
Я использую метод мультипликативного датчика, то есть следующее число ищется как $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$ я получаю генератор без апериодической части. С чем это может быть связано?

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 21:53 
Kevsh в сообщении #1564866 писал(а):
То есть всегда, при любых $a$, $b$ и $M$ я получаю генератор без апериодической части.
Вот прямо при любых? Нельзя делать выводы лишь на основе нескольких опытов. Попробуйте взять $a$ и $M$ не взаимно простыми (например, $a=15$, $M=100$).

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

-- 17.09.2022, 22:44 --

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

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:49 
Аватара пользователя
Kevsh в сообщении #1564871 писал(а):
при ваших данных вообще длина получается равной единице
Да ладно? Напишите последовательность при $x_0 = 1$, $a = 15$, $b = 0$, $M = 100$.
Kevsh в сообщении #1564871 писал(а):
Ещё более странным кажется факт, что критерий Пирсона у меня получается 99,9%
Критерий Пирсона для чего? Равновероятности получающихся значений? В этом ничего удивительного, они гарантированно встречаются с одинаковой частотой.

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:52 
Аватара пользователя
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}

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:56 
Аватара пользователя
Aritaborian в сообщении #1564873 писал(а):
Странно надеяться на иное.
Не странно, оно зависит же.
Если $a = 2$, $b = 0$, $M = 6$, то при $x_0 = 1$ имеем период $2$, а при $x_0 = 3$ - период $1$.

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:58 
Аватара пользователя
mihaild в сообщении #1564874 писал(а):
Не странно, оно зависит же.
Осознал самостоятельно, глупость убрал, гляжу, а вы уже подоспели ;-)

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:59 
Аватара пользователя
Kevsh в сообщении #1564866 писал(а):
Я думал, что будет как-то так

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

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

$b = 2391$

$M = 2387597$

$x_0 = 23485923405$

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

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

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение18.09.2022, 06:54 
Kevsh в сообщении #1564878 писал(а):
Допустим, в примере было так:
$a = 2387$

$b = 2391$

$M = 2387597$

$x_0 = 23485923405$

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

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение18.09.2022, 14:21 
nnosipov
Понял, спасибо большое

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

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

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

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение21.11.2022, 18:18 
Аватара пользователя
Евгений Машеров в сообщении #1570695 писал(а):
Если генератор не с максимальным периодом, то он выдаёт не все возможные числа в этом диапазоне, и если дать на вход число из множества тех, которые не входят в выдаваемые в периоде, то будет апериодический участок, пока он не наткнётся на число из периодической выдачи и далее выдавать только из "периодических".


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

 
 
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение22.11.2022, 17:03 
Аватара пользователя
Евгений Машеров в сообщении #1570695 писал(а):
Запускаем два одинаковых генератора с равными начальными значениями. Один делает один шаг, второй два подряд. Замечаем первое совпадение, длина цикла равна числу итераций до второго совпадения.

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

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group