Тестирование качества ГПСЧ

Я играю с ГПСЧ (например, Мерсенн Твистер и rand() функция stdlib), и мне нужен хороший тест, который помог бы мне определить качество случайных данных, создаваемых ГПСЧ. Я вычислил значение Пи, используя случайные числа, сгенерированные ГПСЧ, и считаю, что rand() и Мерсенн Твистер очень близки, чтобы предложить различие (нужно ли мне тщательно исследовать после 10 десятичных знаков?).

Я не очень разбираюсь в симуляциях Монте-Карло; пожалуйста, дайте мне знать о каком-то алгоритме / приложении (возможно, о чем-то простом, но с тем, чтобы сделать выводы), которые помогут мне различать их с точки зрения качества.


ИЗМЕНИТЬ 1: я раньше не замечал, но есть похожая тема: Как проверить случайные числа?

РЕДАКТИРОВАТЬ 2: Я не могу интерпретировать результаты NIST, как указано в одном из комментариев. У меня появилась идея визуальной интерпретации шаблона (если есть) из random.org, и я следую этому из-за его простоты. Буду очень рад, если кто-нибудь прокомментирует процесс моего тестирования:

  1. Сгенерируйте N случайных чисел из [0,1] с помощью rand () и MT1997
  2. если (round(genrand_real1() / rand_0_1())) то красный пиксель, иначе черный

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


person Sayan    schedule 20.03.2012    source источник
comment
я не уверен в получении каких-либо случайных данных от генераторов псевдослучайных чисел, но я думаю, что вы могли бы реализовать en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin с ними ..   -  person Aprillion    schedule 20.03.2012
comment
Вы говорите так, потому что значения, генерируемые ГПСЧ, предсказуемы? Спасибо   -  person Sayan    schedule 20.03.2012
comment
да, в этом и заключается различие - это было просто напоминанием о том, что вам нужно проверить, подходит ли PRNG для вашего приложения, и вам не нужен TRNG, например random.org   -  person Aprillion    schedule 20.03.2012


Ответы (3)


Есть два стандартных набора тестов для проверки случайных чисел.

  1. Набор тестов NIST. У них есть реализация на C.
  2. Diehard Test Suite (разработанный Джорджем Марсалья). Существует реализация этих тестов в библиотеке C.

Существует интерфейс R для библиотеки Dieharder, который называется RDieHarder. Эта библиотека предоставляет интерфейс как для тестов NIST, так и для наборов тестов Diehard.

person csgillespie    schedule 20.03.2012
comment
Я использую NIST, но думаю, что, хотя мой тест прошел успешно, есть проблема; не могли бы вы помочь? - Я сгенерировал длинные случайные значения, преобразовал их в двоичные и сохранил в файле. Скажем, в файле 100 случайных чисел, я оцениваю 100 и следую шагам в разделе «Запуск тестового кода» документа (выберите сгенерированные битовые потоки равными 10, как в документе). Но я вижу, что мой finalAnalysisReport.txt для тестового примера по умолчанию почти не содержит информации. - person Sayan; 21.03.2012
comment
Лучше всего задать другой вопрос. - person csgillespie; 22.03.2012
comment
Это был хороший ответ, но сейчас он устарел. См. Другой ответ для обновления (TL; DR: L'Ecuyer's TestU01 или PractRand). - person Fab; 05.07.2016

Доступно несколько наборов статистических тестов. Я написал, скопировал и иным образом собрал 120 ГПСЧ и протестировал каждый с помощью различных наборов тестов, давая 4 часа на каждый ГПСЧ на набор тестов:

  • PractRand (стандартный, 1 терабайт) обнаружил смещение в 78 ГПСЧ
  • TestU01 (BigCrush) обнаружил смещение в 50 ГПСЧ
  • RaBiGeTe (расширенный, 512 мегабит, x1) обнаружил смещение в 40 ГПСЧ
  • Dieharder (настраиваемые параметры командной строки) обнаружил смещение в 25 ГПСЧ
  • Dieharder (параметр командной строки) обнаружил смещение в 13 ГПСЧ
  • NIST STS (по умолчанию, 64 мегабит x128) обнаружил смещение в 11 ГПСЧ

Сколько из них было в ГПСЧ, чего не было в других наборах тестов?

  • PractRand (стандартный, 1 терабайт) обнаружил 22 уникальных смещения в самых разных категориях.
  • RaBiGeTe (расширенный, 512 мегабит, x1) обнаружил 5 уникальных смещений, все в LCG и комбинированных LCG.
  • TestU01 BigCrush обнаружил 2 уникальных смещения, оба в небольших хаотических ГПСЧ.
    Ни один другой набор тестов не обнаружил каких-либо уникальных смещений.

Короче говоря, стоит использовать только PractRand, TestU01 и, возможно, RaBiGeTe.

Полное раскрытие информации: я написал PractRand, поэтому либо набор ГПСЧ, либо любой другой некачественный показатель может быть смещен в его пользу.

Прочие преимущества:

  • На мой взгляд, метод PractRand и TestU01, как правило, легче всего интерпретировать.
  • Я думаю, что PractRand и Dieharder, как правило, легче всего автоматизировать с помощью интерфейса командной строки.
  • PractRand и RaBiGeTe были единственными, кто поддерживал многопоточное тестирование.

Прочие недостатки:

  • PractRand требовал большего количества входных битов для тестирования, чем другие наборы тестов - это могло быть проблемой, если ваш ГСЧ очень медленный или иным образом ограничен по объему производимых данных.
  • У RaBiGeTe и NIST STS есть проблемы с интерфейсом.
  • У Dieharder и NIST STS есть ложные срабатывания.
  • На мой взгляд, у NIST STS был худший интерфейс.
  • Я не мог заставить Dieharder скомпилировать в Windows. Мне удалось скомпилировать TestU01 в Windows, но это потребовало некоторой работы.
  • Последние версии RaBiGeTe имеют закрытый исходный код и предназначены только для окон.

Набор протестированных PRNG: набор PRNG включает 1 большой GFSR, 1 большой LFSR, 4 PRNG типа xorshift, 2 PRNG типа xorwow, 3 других PRNG не совсем LFSR. Он включает в себя 10 простых LCG по модулю степени 2 (которые отбрасывают младшие биты для достижения приемлемых уровней качества), 10 не совсем LCG по модулю степени 2 и 9 комбинированных генераторов, основанных в основном на LCG и не совсем LCG. . Он включает 19 версий CSPRNG с пониженной прочностью, а также одну CSPRNG полной прочности. Из них 14 были основаны на косвенных / динамических s-блоках (например, RC4, ISAAC), четыре были параметризацией ChaCha / Salsa, а остальные 2 были вариантами Trivium. Он включает 11 PRNG, которые в целом можно классифицировать как LFib-типа или аналогичные, не считая LFSR / GFSR. Остальные (около 35) были небольшими государственными хаотическими ГПСЧ, из которых 10 использовали умножение, а остальные были ограничены арифметикой и побитовой логикой.

Изменить: также есть набор тестов в gjrand, который очень неясен и немного странно, но на самом деле очень хорошо.

Кроме того, все протестированные ГПСЧ включены в PractRand как не рекомендуемые ГПСЧ.

person user3535668    schedule 26.11.2014
comment
Я счастлив порекомендовать ваш ответ, однако, как написано, нет никаких доказательств. Можете ли вы предоставить ссылки на документы, подтверждающие ваше утверждение? Или несколько инструкций о том, как повторить ваши эксперименты. - person csgillespie; 06.07.2016
comment
Никаких доказательств! DieHarder имеет около 106 тестов. PractRand и TestU01 написаны на C и C ++ и требуют от пользователя интеграции своего генератора! Самыми простыми в использовании являются DieHarder (пакет ubuntu) и NIST STS (пользовательский интерфейс и реализация python)! Я твердо верю, что вы предвзято относитесь к своей работе, и, действительно, как @csgillespie упомянул в своем комментарии, вам необходимо предоставить документ, который поддерживает ваши утверждения! - person Yahya; 07.01.2020

Вам лучше изучить том 2 книги Кнута серия.

Для более короткого чтения найдите соответствующую главу Числовых рецептов.

Если вас интересует только своего рода базовая линия для моделирования MC - линейных конгруэнтных генераторов лучше избегать, Mersenne Twister достаточно хорош в подавляющем большинстве случаев.

person ev-br    schedule 20.03.2012
comment
Не могли бы вы дать ссылку на подтверждение утверждения, что при моделировании Монте-Карло лучше избегать LGC? - person ziggystar; 19.08.2013
comment
@ziggystar: ну ты можешь поискать в Кнута. Или числовые рецепты. Или введите в Google результаты стандартных наборов тестов, например, из ответа csgillespie. - person ev-br; 21.09.2013