stringtranslate.com

Жесткие тесты

Тесты diehard представляют собой набор статистических тестов для измерения качества генератора случайных чисел . Они были разработаны Джорджем Марсальей в течение нескольких лет и впервые опубликованы в 1995 году на CD-ROM случайных чисел. [1] В 2006 году оригинальные тесты diehard были расширены до dieharderтестов. [2]

История

Первоначальный набор тестов на случайность для ГСЧ был предложен в первом издании « Искусства программирования» Дональда Кнута 1969 года (том 2, глава 3.3: статистические тесты). Затем тесты Кнута были вытеснены тестами Diehard Джорджа Марсальи (1995), состоящими из пятнадцати различных тестов. Невозможность изменять параметры теста или добавлять новые тесты привела к разработке библиотеки TestU01 , представленной в 2007 году Пьером Л'Экюйером и Ричардом Симардом из Монреальского университета .

Обзор теста

Интервалы между днями рождения
Выбрать случайные точки на большом интервале. Расстояния между точками должны быть распределены асимптотически экспоненциально . [3] Название основано на парадоксе дней рождения .
Перекрывающиеся перестановки
Проанализируйте последовательности из пяти последовательных случайных чисел. 120 возможных упорядочений должны происходить со статистически равной вероятностью.
Ранги матриц
Выберите некоторое количество бит из некоторого количества случайных чисел, чтобы сформировать матрицу над {0,1}, затем определите ранг матрицы. Подсчитайте ранги.
Тесты на обезьянах
Рассматривать последовательности некоторого количества бит как «слова». Подсчитывать перекрывающиеся слова в потоке. Количество «слов», которые не появляются, должно соответствовать известному распределению. Название основано на теореме о бесконечной обезьяне .
Посчитайте единицы
Подсчитайте биты 1 в каждом из последовательных или выбранных байтов. Преобразуйте счетчики в «буквы» и подсчитайте вхождения пятибуквенных «слов».
Тест на парковке
Случайным образом разместите единичные круги в квадрате 100×100. Круг успешно припаркован, если он не перекрывает существующий успешно припаркованный. После 12 000 попыток количество успешно припаркованных кругов должно следовать определенному нормальному распределению .
Тест на минимальное расстояние
Случайным образом разместите 8000 точек в квадрате 10000×10000, затем найдите минимальное расстояние между парами. Квадрат этого расстояния должен быть экспоненциально распределен с определенным средним.
Тест случайных сфер
Случайным образом выберите 4000 точек в кубе с ребром 1000. Центрируйте сферу в каждой точке, радиус которой равен минимальному расстоянию до другой точки. Наименьший объем сферы должен быть распределен экспоненциально с определенным средним.
Тест на сжатие
Умножьте 2 31 на случайные числа с плавающей точкой на ( 0,1 ) до тех пор, пока не получите 1. Повторите это 100000 раз. Количество чисел с плавающей точкой, необходимое для получения 1, должно соответствовать определенному распределению.
Тест перекрывающихся сумм
Сгенерируйте длинную последовательность случайных чисел с плавающей точкой на ( 0,1 ). Добавьте последовательности из 100 последовательных чисел с плавающей точкой. Суммы должны быть нормально распределены с характерным средним значением и дисперсией.
Тест запуска
Сгенерировать длинную последовательность случайных чисел с плавающей точкой ( 0,1 ). Подсчитать восходящие и нисходящие серии. Подсчеты должны следовать определенному распределению.
Тест на кости
Сыграйте 200000 игр в крэпс , подсчитывая выигрыши и количество бросков за игру. Каждый подсчет должен следовать определенному распределению.

Описания тестов

Тест на интервалы между днями рождения
Выберите m дней рождения в году из n дней. Перечислите интервалы между днями рождения. Если j — это количество значений, которые встречаются в этом списке более одного раза, то j асимптотически распределено по Пуассону со средним значением m 3 / (4 n ) . Опыт показывает, что n должно быть довольно большим, скажем, n ≥ 2 18 , для сравнения результатов с распределением Пуассона с этим средним значением. Этот тест использует n = 2 24 и m = 2 9 , так что базовое распределение для j принимается как пуассоновское с λ = 2 27 / 2 26 = 2 . Берется выборка из 500 j s, и тест согласия хи-квадрат дает значение p . Первый тест использует биты 1–24 (считая слева) из целых чисел в указанном файле. Затем файл закрывается и открывается снова. Далее биты 2–25 используются для предоставления дней рождения, затем 3–26 и так далее до битов 9–32. Каждый набор бит предоставляет p -значение, а девять p -значений предоставляют выборку для KSTEST.
Тест на перекрывающиеся 5-перестановки
Это тест OPERM5. Он рассматривает последовательность из одного миллиона 32-битных случайных целых чисел. Каждый набор из пяти последовательных целых чисел может находиться в одном из 120 состояний для 5! возможных порядков пяти чисел. Таким образом, 5-е, 6-е, 7-е, ... числа каждое обеспечивает состояние. Поскольку наблюдаются тысячи переходов состояний, производятся кумулятивные подсчеты числа появлений каждого состояния. Затем квадратичная форма в слабой обратной ковариационной матрице 120×120 дает тест, эквивалентный тесту отношения правдоподобия, что 120 подсчетов ячеек произошли из указанного (асимптотически) нормального распределения с указанной ковариационной матрицей 120×120 (с рангом 99). Эта версия использует 1000000 целых чисел дважды. Этот тест может иметь нерешенные ошибки, приводящие к постоянно плохим p-значениям. [4]
Тест двоичного ранга для матриц 31×31
Самые левые 31 бит из 31 случайных целых чисел из тестовой последовательности используются для формирования двоичной матрицы 31×31 над полем {0,1}. Ранг определяется. Этот ранг может быть от 0 до 31, но ранги < 28 редки, и их подсчеты объединяются с рангом 28. Ранги находятся для 40000 таких случайных матриц, и тест хи-квадрат выполняется для подсчетов для рангов 31, 30, 29 и ≤ 28.
Тест двоичного ранга для матриц 32×32
Формируется случайная двоичная матрица 32×32, каждая строка — случайное 32-битное целое число. Определяется ранг. Этот ранг может быть от 0 до 32, ранги менее 29 редки, и их подсчеты объединяются с рангом 29. Ранги находятся для 40000 таких случайных матриц, и тест хи-квадрат выполняется для подсчетов для рангов 32, 31, 30 и ≤ 29.
Тест двоичного ранга для матриц 6×8
Из каждого из шести случайных 32-битных целых чисел из тестируемого генератора выбирается указанный байт, и полученные шесть байтов образуют двоичную матрицу 6×8, ранг которой определяется. Этот ранг может быть от 0 до 6, но ранги 0, 1, 2, 3 встречаются редко; их подсчеты объединяются с рангом 4. Ранги находятся для 100000 случайных матриц, и тест хи-квадрат выполняется для подсчетов для рангов 6, 5 и ≤ 4.
Тест битстрима
Тестируемый файл рассматривается как поток битов. Назовем их b 1 , b 2 , ... . Рассмотрим алфавит с двумя «буквами», 0 и 1, и представим поток битов как последовательность 20-буквенных «слов», перекрывающихся друг друга. Таким образом, первое слово — b 1 b 2 ...b 20 , второе — b 2 b 3 ...b 21 и т. д. Тест потока битов подсчитывает количество пропущенных 20-буквенных (20-битных) слов в строке из 2 21 перекрывающихся 20-буквенных слов. Существует 2 20 возможных 20-буквенных слов. Для действительно случайной строки из 2 21 + 19 бит число пропущенных слов j должно быть (очень близко к) нормально распределено со средним значением 141 909 и сигмой 428. Таким образом, ( j −141909) / 428 должно быть стандартной нормальной переменной ( оценкой z ), которая приводит к равномерному [0,1) значению p . Тест повторяется двадцать раз.
Тесты OPSO, OQSO и DNA
OPSO означает перекрывающиеся пары-разреженное-занятие. Тест OPSO рассматривает 2-буквенные слова из алфавита из 1024 букв. Каждая буква определяется указанными десятью битами из 32-битного целого числа в последовательности, которая должна быть протестирована. OPSO генерирует 2 21 (перекрывающихся) 2-буквенных слов (из 2 21 + 1 «нажатия клавиш») и подсчитывает количество пропущенных слов – то есть 2-буквенных слов, которые не появляются во всей последовательности. Это количество должно быть очень близко к нормальному распределению со средним значением 141909, сигма 290. Таким образом, (missingwrds-141909) / 290 должно быть стандартной нормальной переменной. Тест OPSO берет 32 бита за раз из тестового файла и использует назначенный набор из десяти последовательных битов. Затем он перезапускает файл для следующих назначенных 10 бит и так далее. OQSO означает перекрывающиеся-четверки-разреженные-занятия. Тестовый OQSO похож, за исключением того, что он рассматривает 4-буквенные слова из алфавита из 32 букв, каждая буква определяется назначенной строкой из 5 последовательных бит из тестового файла, элементы которого предполагаются 32-битными случайными целыми числами. Среднее количество пропущенных слов в последовательности из 2 21 четырехбуквенных слов (2 21 + 3 "нажатия клавиш") снова равно 141909, с сигмой = 295. Среднее значение основано на теории; сигма получается из обширного моделирования. Тест ДНК рассматривает алфавит из 4 букв C, G, A, T, определяемый двумя назначенными битами в последовательности случайных целых чисел, которые тестируются. Он рассматривает 10-буквенные слова, так что, как и в OPSO и OQSO, существует 2 20 возможных слов, а среднее количество пропущенных слов из строки из 2 21 (перекрывающихся) 10-буквенных слов (2 21 + 9 «нажатий клавиш») составляет 141909. Стандартное отклонение сигма = 339 было определено, как и для OQSO, путем моделирования. (Сигма для OPSO, 290, является истинным значением (до трех знаков), а не определяется путем моделирования.
Тест подсчета единиц в потоке байтов
Рассмотрим тестируемый файл как поток байтов (четыре на 32-битное целое число). Каждый байт может содержать от нуля до восьми единиц с вероятностями 1, 8, 28, 56, 70, 56, 28, 8, 1 на 256. Теперь пусть поток байтов предоставляет строку перекрывающихся 5-буквенных слов, каждая «буква» принимает значения A, B, C, D, E. Буквы определяются количеством единиц в байте: 0, 1 или 2 дают A, 3 дают B, 4 дают C, 5 дают D и 6, 7 или 8 дают E. Таким образом, у нас есть обезьяна за пишущей машинкой, нажимающая пять клавиш с различными вероятностями (37, 56, 70, 56, 37 на 256). Существует 5 5 возможных 5-буквенных слов, и из строки из 256000 (перекрывающихся) 5-буквенных слов подсчеты производятся по частотам для каждого слова. Квадратичная форма в слабой обратной матрице ковариации количества ячеек обеспечивает хи-квадрат тест Q5–Q4, разницу наивных сумм Пирсона (OBS-EXP) 2 / EXP по подсчетам для 5- и 4-буквенных подсчетов ячеек.
Тест подсчета единиц для определенных байтов
Рассмотрим тестируемый файл как поток 32-битных целых чисел. Из каждого целого числа выбирается определенный байт, скажем, самые левые биты от 1 до 8. Каждый байт может содержать от 0 до 8 единиц с вероятностями 1, 8, 28, 56, 70, 56, 28, 8, 1 на 256. Теперь пусть указанные байты из последовательных целых чисел образуют строку (перекрывающихся) 5-буквенных слов, где каждая «буква» принимает значения A, B, C, D, E. Буквы определяются количеством единиц в этом байте 0, 1 или 2 → A, 3 → B, 4 → C, 5 → D и 6, 7 или 8 → E. Таким образом, у нас есть обезьяна за пишущей машинкой, нажимающая пять клавиш с различными вероятностями 37, 56, 70, 56, 37 на 256. Существует 5 5 возможных 5-буквенные слова, и из строки из 256000 (перекрывающихся) 5-буквенных слов, подсчеты производятся по частотам для каждого слова. Квадратичная форма в слабой обратной ковариационной матрице подсчетов ячеек обеспечивает критерий хи-квадрат Q5 – Q4, разность наивных сумм Пирсона (OBS − EXP) 2 / EXP по подсчетам для 5- и 4-буквенных подсчетов ячеек.
Тест на парковке
В квадрате со стороной 100 случайным образом «припаркуйте» автомобиль – круг радиусом 1. Затем попробуйте припарковать второй, третий и так далее, каждый раз паркуясь «на слух». То есть, если попытка припарковать автомобиль приводит к столкновению с уже припаркованным автомобилем, попробуйте еще раз в новом случайном месте. (Чтобы избежать проблем с траекторией, рассмотрите парковку вертолетов, а не автомобилей.) Каждая попытка приводит либо к столкновению, либо к успеху, последний сопровождается увеличением списка уже припаркованных автомобилей. Если мы построим график n : количество попыток, в зависимости от k – количество успешно припаркованных автомобилей, мы получим кривую, которая должна быть похожа на те, которые предоставляет идеальный генератор случайных чисел. Теория поведения такой случайной кривой кажется недостижимой, и поскольку графические дисплеи недоступны для этой серии тестов, используется простая характеристика случайного эксперимента: k , количество автомобилей, успешно припаркованных после n = 12000 попыток. Моделирование показывает, что k должно быть в среднем 3523 с сигмой 21,9 и очень близко к нормальному распределению. Таким образом, ( k − 3523) / 21,9 должна быть стандартной нормальной переменной, которая, преобразованная в равномерную переменную, обеспечивает входные данные для KSTEST на основе выборки из 10.
Тест на минимальное расстояние
Он делает это 100 раз, выбирая n = 8000 случайных точек в квадрате со стороной 10000. Найдите d , минимальное расстояние между ( n 2 − n ) / 2 парами точек. Если точки действительно независимы и равномерны, то d 2 , квадрат минимального расстояния, должен быть (очень близок к) экспоненциально распределен со средним значением 0,995. Таким образом, 1 − exp(− d 2 / 0,995) должен быть равномерным на [0,1), а KSTEST для полученных 100 значений служит тестом равномерности для случайных точек в квадрате. Выводятся тестовые числа = 0 mod 5, но KSTEST основан на полном наборе из 100 случайных выборов 8000 точек в квадрате 10000×10000.
Тест 3D-сфер
Выберите 4000 случайных точек в кубе с ребром 1000. В каждой точке поместите в центр сферу, достаточно большую, чтобы достичь следующей ближайшей точки. Тогда объем наименьшей такой сферы будет (очень близок к) экспоненциально распределен со средним значением 120 π / 3. Таким образом, радиус в кубе будет экспоненциальным со средним значением 30. (Среднее значение получено путем обширного моделирования). Тест 3D-сфер генерирует 4000 таких сфер 20 раз. Каждый минимальный радиус в кубе приводит к однородной переменной с помощью 1 − exp(− r 3 / 30) , затем KSTEST выполняется на 20 p -значениях.
Тест на сжатие
Случайные целые числа плавают, чтобы получить униформы на [0,1). Начиная с k = 2 31 = 2147483648, тест находит j , количество итераций, необходимых для уменьшения k до 1, используя уменьшение k = ceiling( k × U ), где U предоставляется плавающими целыми числами из тестируемого файла. Такие j s находятся 100000 раз, затем подсчитывается количество раз, когда j было ≤ 6, 7, ..., 47, ≥ 48, что используется для обеспечения теста хи-квадрат для частот ячеек.
Тест перекрывающихся сумм
Целые числа плавают, чтобы получить последовательность U (1), U (2), ... равномерных [0,1) переменных. Затем формируются перекрывающиеся суммы, S (1) = U (1) + ... + U (100), S (2) = U (2) + ... + U (101), .... S s являются практически нормальными с определенной ковариационной матрицей. Линейное преобразование S s преобразует их в последовательность независимых стандартных нормалей, которые преобразуются в равномерные переменные для KSTEST. P -значения из десяти KSTEST задаются еще одним KSTEST.
Тестовые запуски
Он подсчитывает прогоны вверх и вниз в последовательности равномерных переменных [0,1), полученных путем плавающего 32-битного целого числа в указанном файле. Этот пример показывает, как подсчитываются прогоны: 0.123, 0.357, 0.789, 0.425, 0.224, 0.416, 0.95 содержит прогон вверх длиной 3, прогон вниз длиной 2 и прогон вверх (по крайней мере) 2, в зависимости от следующих значений. Матрицы ковариации для прогонов вверх и вниз хорошо известны, что приводит к тестам хи-квадрат для квадратичных форм в слабых обратных матрицах ковариации. Прогоны подсчитываются для последовательностей длиной 10000. Это делается десять раз. Затем повторяется.
Тест на кости
Он играет в 200000 игр в крэпс, находит количество побед и количество бросков, необходимых для завершения каждой игры. Количество побед должно быть (очень близко к) нормальному со средним значением 200000 p и дисперсией 200000 p (1 − p ) , где p = 244 / 495 . Броски, необходимые для завершения игры, могут варьироваться от 1 до бесконечности, но подсчеты для всех > 21 объединяются с 21. Проводится тест хи-квадрат на подсчетах ячеек количества бросков. Каждое 32-битное целое число из тестового файла дает значение для броска игральной кости путем плавающего значения [0,1), умножения на 6 и взятия 1 плюс целая часть результата.

Большинство тестов в DIEHARD возвращают p -значение, которое должно быть равномерным на [0,1), если входной файл содержит действительно независимые случайные биты. Эти p -значения получаются из p = F ( X ), где F — предполагаемое распределение случайной величины выборки X — часто нормальное. Но это предполагаемое F — всего лишь асимптотическое приближение, для которого соответствие будет наихудшим в хвостах. Таким образом, вас не должны удивлять случайные p -значения около 0 или 1, такие как 0,0012 или 0,9983. Когда поток битов действительно СИЛЬНО НЕ ПРОХОДИТ, вы получите p s от 0 или 1 до шести или более знаков. Поскольку существует много тестов, вполне вероятно, что p < 0,025 или p > 0,975 означает, что ГСЧ «провалил тест на уровне 0,05». Мы ожидаем, что среди сотен событий, которые выдает DIEHARD, произойдет несколько таких событий p s, даже при условии идеальности генератора случайных чисел.

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

Ссылки

  1. ^ "CDROM Marsaglia Random Number, включающий Diehard Battery of Tests of Randomness". Университет штата Флорида . 1995. Архивировано из оригинала 25.01.2016.
  2. ^ Браун, Роберт Г. "dieharder" . Получено 25.09.2023 .
  3. ^ Реньи, 1953, стр. 194
  4. ^ "Страница общих инструментов Роберта Г. Брауна". Архивировано из оригинала 2017-07-03.

Дальнейшее чтение

Внешние ссылки