ТестU01

Коллекция утилит для эмпирического тестирования случайности

TestU01 — это программная библиотека , реализованная на языке ANSI C , которая предлагает набор утилит для эмпирического тестирования случайности генераторов случайных чисел (ГСЧ). ^[1] Библиотека была впервые представлена в 2007 году Пьером Л'Экюйером и Ричардом Симаром из Монреальского университета . ^[2]

Библиотека реализует несколько типов генераторов случайных чисел, включая некоторые из предложенных в литературе и некоторые из широко используемых программных продуктов. Она предоставляет общие реализации классических статистических тестов для генераторов случайных чисел, а также несколько других, предложенных в литературе, и некоторые оригинальные. Эти тесты могут быть применены к генераторам, предопределенным в библиотеке, генераторам, определенным пользователем, и потокам случайных чисел, сохраненных в файлах. Также доступны специальные наборы тестов для последовательностей равномерных случайных чисел в [0,1] или битовых последовательностей. Также предоставляются основные инструменты для построения векторов точек, созданных генераторами.

История

Первоначальный набор тестов на случайность для ГСЧ был предложен в первом издании « Искусства программирования» Дональда Кнута в 1969 году . Тесты Кнута затем были вытеснены тестами Diehard Джорджа Марсальи (1996), состоящими из пятнадцати различных тестов. Невозможность изменять параметры теста или добавлять новые тесты привела к разработке библиотеки TestU01.

Функции

TestU01 предлагает четыре группы модулей для анализа ГСЧ:

Внедрение (заранее запрограммированных) ГСЧ;
Реализация конкретных статистических тестов;
Реализация комплексов статистических тестов;
Применение тестов ко всем семействам ГСЧ.

Когда определенный тест применяется к выборке размера n, созданной ГСЧ, p -значение теста обычно остается разумным по мере увеличения размера выборки, пока размер выборки не достигнет n ₀ , скажем. После этого p -значение расходится к 0 или 1 с экспоненциальной скоростью. Модуль 4 позволяет исследователю изучать взаимодействие между определенным тестом и структурой точечных множеств, созданных данным семейством ГСЧ. Этот метод можно использовать для определения того, насколько большим должен быть размер выборки в зависимости от длины периода генератора, прежде чем генератор начнет систематически проваливать тест.

TESTU01 предлагает несколько батарей тестов, включая «Small Crush» (состоящий из 10 тестов), «Crush» (96 тестов) и «Big Crush» (106 тестов). Конкретные тесты, применяемые каждой батареей, подробно описаны в руководстве пользователя. ^[3] На 1,7 ГГц Pentium 4 под управлением Red Hat Linux 9.0 для простого ГСЧ Small Crush занимает около 2 минут. Crush занимает около 1,7 часа. Big Crush занимает около 4 часов. Для более сложного ГСЧ все эти времена увеличиваются в два раза или более. Для сравнения, тесты Diehard выполняются около 15 секунд.

Ограничения

TestU01 принимает только 32-битные входные данные и интерпретирует их как значения в диапазоне [0, 1]. Это делает его более чувствительным к дефектам в старших битах, чем в младших. Важно тестировать универсальные генераторы в бит-реверсивной форме, чтобы проверить их пригодность для приложений, использующих младшие биты. ^[4]^{: 4}

Генераторы, которые выдают 64 бита выходных данных, дополнительно требуют отдельных тестов для своих высоких и низких половин. ^[5]^{: 51}

Смотрите также

Ссылки

^ Веб-сайт TestU01.
^ Пьер Л'Экюйер и Ричард Симар (2007), «TestU01: программная библиотека на языке ANSI C для эмпирического тестирования генераторов случайных чисел», ACM Transactions on Mathematical Software , 33: 22.
^ Руководство пользователя TestU01.
^ Винья, Себастьяно (июль 2016 г.). «Экспериментальное исследование генераторов ксоршифта Марсальи, скремблированное» (PDF) . ACM Transactions on Mathematical Software . 42 (4): 30. arXiv : 1402.6246 . doi :10.1145/2845077. S2CID 13936073.
^ О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: Семейство простых быстрых и эффективных по объему статистически хороших алгоритмов для генерации случайных чисел (PDF) (Технический отчет). Колледж Харви Мадда . HMC-CS-2014-0905.

[TestU01-1] Веб-сайт TestU01.

[Original_Paper-2] Пьер Л'Экюйер и Ричард Симар (2007), «TestU01: программная библиотека на языке ANSI C для эмпирического тестирования генераторов случайных чисел», ACM Transactions on Mathematical Software , 33: 22.

[User_Guide-3] Руководство пользователя TestU01.

[vigna-4] Винья, Себастьяно (июль 2016 г.). «Экспериментальное исследование генераторов ксоршифта Марсальи, скремблированное» (PDF) . ACM Transactions on Mathematical Software . 42 (4): 30. arXiv : 1402.6246 . doi :10.1145/2845077. S2CID 13936073.

[5] О'Нил, Мелисса Э. (5 сентября 2014 г.). PCG: Семейство простых быстрых и эффективных по объему статистически хороших алгоритмов для генерации случайных чисел (PDF) (Технический отчет). Колледж Харви Мадда . HMC-CS-2014-0905.