2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Выбор критерия.
Сообщение27.03.2020, 11:36 


17/03/20
183
Добрый день уважаемые форумчане! Поставлена задача исследования двух алгоритмов ГПСЧ, выбран линейный конгруэнтный метод и так намазываемый алгоритм с РСЛОС "Вихрь Мерсенна". Суть такова: имеется набор $\xi_{n}$, каждый такой элемент $\xi_{i}$, представляет собой сгенерированную пару чисел $x, y$. Сначала применялся конгруэнтный метод, а затем "Вихрь Мерсенна". Необходимо, чтобы числа $x, y$ каждого соседнего набора $\xi_{n+1}$ отличались как можно более от чисел предыдущего набора $\xi_{n}$, т.е были независимы. Так вот вопрос, что можно выбрать в качестве критерия независимости этих пар чисел для каждого набора, чтобы сравнить какой алгоритм эффективнее генерирует псевдослучайные числа?

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение27.03.2020, 23:35 
Заслуженный участник


26/05/14
981
Тестирование_псевдослучайных_последовательностей

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 09:11 


17/03/20
183
slavav в сообщении #1447767 писал(а):


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

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 10:34 


17/03/20
183
Просто если коэффициент корреляции равен нулю, это не означает, что элементы в последовательности независимы... А мне надо именно исследовать то, что соседний набор независим от предыдущего, и все остальных, расположенных до него. Поэтому я поинтересовался. Я читал книгу Кнута, там описано про тестирование именно на случайность, на равномерность, но распределение и так равномерно. А вот независимы ли $\xi_{n}$...? К тому же у меня получается, что каждый такой набор $\xi_{i}$ еще и имеет размерность m=2.

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 10:55 
Заслуженный участник


26/05/14
981
Я бы собрал все пары $(x_i, y_i)$ в одну последовательность $x_1, y_1, x_2, y_2, \dots, x_i, y_i, \dots$ и тестировал бы её тестами из NIST.
Так как статистические тесты выявляют не случайные подпоследовательности (это что вам нужно), то они покажут насколько независимы ваши пары.

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 11:17 


17/03/20
183
slavav в сообщении #1447833 писал(а):
Я бы собрал все пары $(x_i, y_i)$ в одну последовательность $x_1, y_1, x_2, y_2, \dots, x_i, y_i, \dots$ и тестировал бы её тестами из NIST.
Так как статистические тесты выявляют не случайные подпоследовательности (это что вам нужно), то они покажут насколько независимы ваши пары.

Хорошо, спасибо, буду пробовать!

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 14:18 


17/03/20
183
slavav в сообщении #1447833 писал(а):
Я бы собрал все пары $(x_i, y_i)$ в одну последовательность $x_1, y_1, x_2, y_2, \dots, x_i, y_i, \dots$ и тестировал бы её тестами из NIST.
Так как статистические тесты выявляют не случайные подпоследовательности (это что вам нужно), то они покажут насколько независимы ваши пары.


Правда есть проблема, у меня числа сгенерированные от 0 до 1, и они не в двоичной форме, а эти тесты работают для бинарных чисел, т.е мне мои 200000 x и y придется переводить в двоичный код...

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 15:18 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Alm99 в сообщении #1447889 писал(а):
Правда есть проблема, у меня числа сгенерированные от 0 до 1, и они не в двоичной форме
Странная проблема. Вы разве не знаете, что в компьютере вообще всё представляется в двоичной системе? Независимо от того, хотите Вы этого или нет.

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 16:01 


17/03/20
183
Someone
Да нет, это и так понятно. Я думал для NIST надо преобразовывать, хотя не понимаю, с чего я это решил.
NIST если может работать с обычными числами, то хорошо. Я скачал с оф.сайта пакет просто, а там примеры работы показаны на бинарных числах.

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 16:33 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Alm99 в сообщении #1447913 писал(а):
Я думал для NIST надо преобразовывать, хотя не понимаю, с чего я это решил.
Может быть, Вы и правы, этого я не знаю. Там написано "Random Bit Generation". Ясно, что если напрямую рассматривать двоичный код числа с плавающей точкой как последовательность бит, то будет плохо, потому что там есть большая малослучайная часть — порядок. Ну, попробуйте взять мантиссу и сдвинуть её вправо в соответствии с порядком. Проще всего — умножить число на походящую степень двойки и преобразовать в целое число. Только надо разобраться с форматом представления числа в компьютере, там в некоторых форматах старший бит мантиссы может быть скрытым, потому что в нормализованном числе он всегда содержит единицу. Может быть, придётся пожертвовать младшим битом мантиссы.

В качестве альтернативы можно почитать, что написано о тестировании псевдослучайных последовательностей у Д. Кнута во втором томе "Искусства программирования на ЭВМ" (Donald E. Knuth, "The art of computer programming", Seminumerical algoritms, Third edition). Можно найти в интернете.

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 16:46 
Аватара пользователя


08/03/20

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

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 21:19 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Alm99
Наткнулся на статью о применении тестов NIST для проверки генераторов псевдослучайных чисел. Проверены $18$ генераторов.

 Профиль  
                  
 
 Re: Выбор критерия.
Сообщение28.03.2020, 22:24 


17/03/20
183
Someone
Почитал ее. Интересно, конечно все это...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: mihaild


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

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