2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 20:52 


19/11/20
239
Москва
Я использую метод мультипликативного датчика, то есть следующее число ищется как $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:39 


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

-- 17.09.2022, 22:44 --

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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:52 
Аватара пользователя


11/06/12
10363
стихия.вздох.мюсли
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 
Заслуженный участник
Аватара пользователя


16/07/14
7098
Цюрих
Aritaborian в сообщении #1564873 писал(а):
Странно надеяться на иное.
Не странно, оно зависит же.
Если $a = 2$, $b = 0$, $M = 6$, то при $x_0 = 1$ имеем период $2$, а при $x_0 = 3$ - период $1$.

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:58 
Аватара пользователя


11/06/12
10363
стихия.вздох.мюсли
mihaild в сообщении #1564874 писал(а):
Не странно, оно зависит же.
Осознал самостоятельно, глупость убрал, гляжу, а вы уже подоспели ;-)

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение17.09.2022, 22:59 
Заслуженный участник
Аватара пользователя


01/09/13
3551
Kevsh в сообщении #1564866 писал(а):
Я думал, что будет как-то так

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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение18.09.2022, 01:05 


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

$b = 2391$

$M = 2387597$

$x_0 = 23485923405$

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

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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение18.09.2022, 06:54 
Заслуженный участник


20/12/10
8862
Kevsh в сообщении #1564878 писал(а):
Допустим, в примере было так:
$a = 2387$

$b = 2391$

$M = 2387597$

$x_0 = 23485923405$

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

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


19/11/20
239
Москва
nnosipov
Понял, спасибо большое

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение21.11.2022, 13:38 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение21.11.2022, 15:37 


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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение21.11.2022, 18:18 
Аватара пользователя


28/10/21
82
Евгений Машеров в сообщении #1570695 писал(а):
Если генератор не с максимальным периодом, то он выдаёт не все возможные числа в этом диапазоне, и если дать на вход число из множества тех, которые не входят в выдаваемые в периоде, то будет апериодический участок, пока он не наткнётся на число из периодической выдачи и далее выдавать только из "периодических".


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

 Профиль  
                  
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение22.11.2022, 17:03 
Аватара пользователя


26/05/12
1515
приходит весна?
Евгений Машеров в сообщении #1570695 писал(а):
Запускаем два одинаковых генератора с равными начальными значениями. Один делает один шаг, второй два подряд. Замечаем первое совпадение, длина цикла равна числу итераций до второго совпадения.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group