TestU01 - TestU01

TestU01 это библиотека программного обеспечения, реализованный в ANSI C язык, который предлагает набор утилит для эмпирический проверка на случайность из генераторы случайных чисел (ГСЧ).[1] Библиотека была впервые представлена ​​в 2007 году Пьером Л’Экуайером и Ричардом Симаром из Université de Montréal.[2]

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

История

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

Функции

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

  1. Внедрение (предварительно запрограммированных) ГСЧ;
  2. Проведение специальных статистических тестов;
  3. Внедрение батарей статистических тестов;
  4. Применение тестов ко всем семействам ГСЧ.

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

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

Ограничения

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

Генераторы, которые выдают 64-битный выходной сигнал, дополнительно требуют отдельных тестов для их верхней и нижней половин.[5]:51

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

Рекомендации

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