TestU01

TestU01 впервые был реализован в 1985 году на языке Pascal и содержал тесты, предложенные Дональдом Кнутом во втором издании второго тома Искусства программирования[2]. Четыре года спустя был повторно реализован на языке Modula-2 в виде пакета с модульным дизайном. Тогда вместе с новыми тестами были добавлены некоторые наиболее часто используемые ГПСЧ. В период с 1990 по 2001 годы пакет периодически пополнялся новыми генераторами и тестами, а руководство пользователя своевременно обновлялось (на французском). ${\displaystyle f}$ модули, содержащие инструменты для тестирования семейств генераторов, впервые были представлены в 1997 году. В 2002 году Пьер Л`Экуйе и Ричард Симард переработали библиотеку, реализовали её на языке C и перевели руководство на английский язык.

ГПСЧ в основном предназначены для хорошей имитации последовательности независимых случайных величин, обычно в действительном интервале ${\displaystyle (0,1)}$ или в двоичном наборе ${\displaystyle [0,1]}$. В первом случае гипотеза ${\displaystyle \mathrm {H} }$₀^A гласит, что числа ${\displaystyle u}$₀, ${\displaystyle u}$₁, ${\displaystyle u}$₂, ${\displaystyle u}$₃... – независимые величины из равномерного распределения в интервале ${\displaystyle (0,1)}$[3]. Во втором, ${\displaystyle \mathrm {H} }$₀^B гласит, что имеется последовательность независимых случайных бит, каждый из которых принимает значение ${\displaystyle 0}$ или ${\displaystyle 1}$ с равной вероятностью[3].

${\displaystyle \mathrm {H} }$₀^A эквивалентно высказыванию, что для любого целого ${\displaystyle t}$ вектор (${\displaystyle u}$₀, ..., ${\displaystyle u}$_{${\displaystyle t-1}$}) равномерно распределён в ${\displaystyle t}$-мерном кубе ${\displaystyle (0,1)}$^{${\displaystyle t}$}. Для алгоритмических ГПСЧ утверждение является неверным, т.к. векторы в них берут свои значения из конечного числа ${\displaystyle \Psi }$_{${\displaystyle t}$} всех ${\displaystyle t}$-мерных векторов, которые способен выдать генератор[3].

Для последовательности бит гипотеза ${\displaystyle \mathrm {H} }$₀^B тоже не может формально называться истинной в случае, когда длина ${\displaystyle t}$ последовательности превышает количество ${\displaystyle b}$ бит состояний генератора, потому что количество производимых возможных последовательностей не может превышать ${\displaystyle 2}$^{${\displaystyle b}$}[3]. Задача генератора состоит в том, чтобы убедиться в равномерном распределении последовательностей в поле всех возможных последовательностей в ${\displaystyle 2}$^{${\displaystyle t}$}.

Другой критерий качества для ГПСЧ используется в криптологии и в азартных игровых автоматах. Здесь, вдобавок ко всему вышеперечисленному, отдельное внимание уделяется непредсказуемости последующих чисел[3].

TestU01 предлагает четыре группы модулей для работы с генераторами:

1. реализация заранее запрограммированного генератора (модуль ${\displaystyle u}$);
2. реализация специальных статистических тестов (модуль ${\displaystyle s}$);
3. реализация батарей статистических тестов (модуль ${\displaystyle b}$);
4. применение тестов на целых семействах генераторов (модуль ${\displaystyle f}$).

Когда конкретный тест применяется на выходных данных генератора размера ${\displaystyle n}$ , p-значение теста обычно остается разумным до тех пор, пока размер данных не достигнет определенного значения ${\displaystyle n_{0}}$. После этого p-значение расходится к ${\displaystyle 0}$ или ${\displaystyle 1}$ с экспоненциальной скоростью. Модуль ${\displaystyle f}$ позволяет исследователю изучить связь между специальным тестом и структурой множества точек, полученных с помощью определенного семейства генераторов. Эта техника может быть использована для определения размера проверяемых данных в зависимости от длины периода генератора до того, как генератор не начнет систематически проваливать тесты.

TestU01 предлагает несколько батарей тестов, таких как SmallCrush (состоит из 10 тестов), Crush (96 тестов) и BigCrush (106 тестов). На компьютере на базе процессора Pentium 4 и с операционной системой Linux для простого генератора время работы батареи тестов SmallCrush занимает несколько минут, Crush — порядка часа, BigCrush — порядка десятка часов[3].

Батарея Alphabit создавалась для тестирования аппаратных генераторов случайных чисел. Проводит девять последовательных тестов, перед каждым переписывая входные данные.

Rabbit – батарея, больше сфокусированная на тестировании двоичных данных, но некоторые тесты проходят с фиксированными параметрами, какого бы размера ни были входные данные. Поэтому данные, размер которых превышает 64 мегабайта, приводит к ошибке в одном из тестов и приводит к переполнению оперативной памяти.[7]

SmallCrush, маленькая и быстрая батарея тестов, считывает генератор как файл, содержащий числа с плавающей точкой в пределах ${\displaystyle [0,1)}$. Ограничение на файл чуть менее 51320000 случайных чисел. Файл будет переписан в начале каждого теста. Некоторые тесты требуют чтобы генератор возвращал как минимум 30 бит решения, в противном случае генератор с большой вероятностью провалит их. Обычно используется для проверки целесообразности проведения тестов на более строгих батареях[7].

Crush – Батарея из строгих статистических тестов. Включает в себя как классические тесты Кнута, так и множество других. Некоторые из этих тестов предполагают, что генератор возвращает как минимум 30 бит решения, в противном случае тесты будут считаться проваленными. Один из тестов требует 31 бит данных. Батарея использует примерно 2³⁵ случайных чисел[7].

BigCrush – батарея самых строгих статистических тестов. Так же как и в остальных батареях, некоторые тесты требуют как минимум 30 бит входных данных, иначе тесты будут провалены. Так же один из тестов требует 31 бит данных. Батарея использует почти 2³⁸ случайных чисел. Когда BigCrush впервые появился, даже считавшиеся хорошими ГПСЧ с трудом его проходили[7].

Тесты батареи SmallCrush

Вот некоторые примеры тестов батареи SmallCrush[1].

BirthdaySpasings	Тест, основанный на парадоксе дней рождения. Выбираются случайные точки на большом интервале, расстояния между которыми должны быть асимптотически распределены по Пуассону.
Gap	Тест, использующийся для определения интервала между повторениями одной и той же цифры.
CouponCollector	Пусть ${\displaystyle \xi _{1},\xi _{2},\dots ,\xi _{n}}$ последовательность длины n и размерности m. Исследуются последовательности определенной длины, которые содержат m-разрядное число.
MatrixRank	Тест выбирает определённое количество бит из некоторого количества случайных чисел чтобы сформировать матрицу над {0,1}. Затем определяется ранг матрицы.

• Pierre L’Ecuyer, Richard Simard. TestU01: A C Library for Empirical Testing of Random Number Generators. — D´epartement d’Informatique et de Recherche Op´erationnelleUniversit´e de Montr´eal: ACM Transactions on Mathematical Software, 2007. — 40 с.
• Knuth D.E. The Art of Computer Programming volume 2, — ISBN 0-201-89684-2.

• The TestU01 Site. (неопр.).
• TestU01. A Software Library in ANSI C for Empirical Testing of Random Number Generators. (неопр.).