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

Question

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

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

---

EDIT 1: я не замечал раньше, но есть аналогичные нити: How to test random numbers?

EDIT 2: Я не в состоянии интерпретировать результаты NIST, как указано в один из комментариев. Я получил эту идею визуально интерпретировать шаблон (если есть) от random.org и следую за этим из-за его простоты. Я был бы очень рад, если кто-то может прокомментировать процесс моего тестирования:

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

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

Answer 1

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

1. NIST набор тестов. У них есть implementation in C.
2. Diehard Test Suite (разработан Джорджем Марсалья). Выполнение этих тестов осуществляется C library.

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

Answer 2

Лучше всего смотреть в volume 2 of the Knuth's series.

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

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

Answer 3

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

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

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

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

Одним словом, стоит использовать только PractRand, TestU01 и, возможно, RaBiGeTe.

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

Разное Преимущества:

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

Разные Недостатки:

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

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

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

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