2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Как найти период генератора псевдослучайных чисел?
Сообщение22.11.2022, 17:10 
Заслуженный участник
Аватара пользователя


16/07/14
8344
Цюрих
B@R5uk в сообщении #1570975 писал(а):
Не очень надёжная схема. Если период кратен 2, то оба генератора будут синфазны, и совпадение просто не будет обнаружено.
Это стандартный алгоритм поиска цикла в связном списке. Совпадение гарантированно будет, потому что после входа в цикл на каждой итерации длина пути от быстрого до медленного итератора уменьшается на $1$.

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


26/05/12
1534
приходит весна?
mihaild в сообщении #1570979 писал(а):
уменьшается на 1
О, точно, на разность же надо смотреть. Спасибо.

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


11/03/08
9490
Москва
TheRuinedMap в сообщении #1570734 писал(а):
Не обязательно. Генератор может разбивать диапазон на несколько циклов, каждый без апериодической части.


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

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


11/03/08
9490
Москва
B@R5uk в сообщении #1570975 писал(а):
Не очень надёжная схема. Если период кратен 2, то оба генератора будут синфазны, и совпадение просто не будет обнаружено.


Совершенно надёжная. Пример: "генератор" с периодом 4 вида $x_{i+1}=(x_i+1) \mod 4$
Запускаем с начальным значением 0
(номер испытания: выход первого генератора; выходы двух подряд запусков второго генератора)
1: 1; 1,2
2: 2; 3,0
3: 3; 1,2
4: 0; 3,0 - первое совпадение, запоминаем N=4
5: 1; 1,2
6: 2; 3,0
7: 3; 1,2
8: 0; 3,0 - второе совпадение, период равен 8-4=4

Синфазности тут в принципе быть не может, она сбивается на каждом шаге, поскольку второй запускается по два раза, и разность позиций в цикле всякий раз растёт на единицу. Апериодика пропускается, поскольку в апериодической последовательности не может быть тех значений, которые входят в цикл (естественно, это для генераторов вида $x_{i+1}=f(x_i)$ - линейных конгруэнтных, "середины квадрата" и другие, если генератор зависит от двух или более предыдущих, как генератор Фибоначчи, то проверка усложняется)
В случае распадения на несколько циклов находится один из них, способа отыскать все без перебора не знаю.

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


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

Это я про то, что не надо изобретать велосипед, если его уже списали и заменили на мерс. Кроме того, может встать еще одна проблема: генерация больших массивов случайных чисел, особенно в параллельном режиме. Использовать много мегабайтные процессорные кэши в этом случае мало кому под силу и хотя диспетчер задач будет показывать стопроцентную загрузку всех используемых ядер, на самом деле кпд будет не более чем несколько процентов. В этом случае советую использовать пакет Statistical Functions из Intel® Math Kernel Library: очень грамотно реализованная шняга почти на все вкусы.

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


11/03/08
9490
Москва
Это несколько иная задача. Rdrand использует аппаратный источник энтропии. Что важно для криптографии, обеспечивая невоспроизводимость, но плохо для отладки программ (впрочем, были претензии и у криптографов). Выбирается две последовательности по 256 бит от аппаратного ГСЧ, которые действительно случайны, но статистические их качества не гарантированы, затем они подаются на вход шифратора AES, после чего полученная 256-битная последовательность, оставаясь случайной, имеет распределение, удовлетворяющее статистическим критериям. Затем она используется как начальная точка для ГПСЧ, выдающего 511 чисел, для дальнейшего вновь запрашивается аппаратный генератор (истинно) случайных чисел.

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


12/07/21
108
Евгений Машеров в сообщении #1571428 писал(а):
Это несколько иная задача.

Задача у всех генераторов одна и та же. Остальное про RdRand - это спекуляции (где нет детерминированности, то это непреложный факт: вспоминается недавний мобель за опровержение существования скрытых параметров: а сколько копий было сломано, начиная с Эйнштейна).
Кроме того в задаче TC нужны большие выборки: я поэтому и дополнил свое сообщение, чтобы он долго не мучился: $x_{i+1}=(ax_i+b)\%M$ в Intel MKL тоже есть.

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


11/03/08
9490
Москва
Ну, на уровне философских воззрений, может, и одна. А на уровне практики появляются "досадные мелочи". Кстати, а откуда Вы взяли информацию, что "в задаче ТС нужны большие выборки"? Лично я не уверен даже, что это прикладная задача, а не учебная. И не научно-исследовательская "изучение характеристик генератора СЧ".

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

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



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

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


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

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