Тестирование качества PRNG

Question

Я играю с PRNG (например, Mersenne Twister и rand() функция stdlib), и мне нужен хороший тест, который помог бы мне выяснить качество случайных данных, генерируемых PRNG.Я вычислил значение Pi, используя случайные числа, сгенерированные PRNG, и нахожу, что rand() и Mersenne Twister очень близки, чтобы предложить различие (нужно ли мне исследовать после 10 десятичных знаков?).

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

---

РЕДАКТИРОВАТЬ 1: Iраньше не замечал, но есть похожая тема: Как проверить случайные числа?

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

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

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

Answer 1

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

• PractRand (стандартно, 1 терабайт) найдено смещение в 78 PRNG
• TestU01 (BigCrush) найдено смещение в 50 PRNG
• RaBiGeTe (расширенный, 512 мегабит, x1) найдено смещениев 40 PRNG
• Dieharder (пользовательские параметры командной строки) обнаружил смещение в 25 PRNG *
• Dieharder (-a опция командной строки) обнаружил смещение в13 PRNG
• NIST STS (по умолчанию, 64 мегабит x128) обнаружили смещение в 11 PRNG

Сколько из них было в PRNG, что другоевсе комплекты тестов пропущены?

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

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

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

Разные преимущества:

• 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 типа ксоршифинга, 2 PRNG типа ксорвау, 3 других не вполне-LFSRPRNGs.Он включает в себя 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) были небольшими государственными хаотическими PRNG, из которых 10 использовали умножение, а остальные были ограничены арифметической и побитовой логикой.

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

Кроме того, все протестированные PRNG включены в качестве рекомендуемых PRNG в PractRand.

Answer 2

Существует два стандартных набора тестов для тестирования случайных чисел.

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

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

Answer 3

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

. Для краткого прочтения посмотрите соответствующую главу «Числовые рецепты».

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