Как unit test генератор псевдослучайных чисел?

У меня есть класс генерации псевдослучайных чисел (PRNG), который я хочу unit test. Существует два подхода:

напишите тестовый пример, который принимает большое количество образцов и проверяет, правильно ли они распределены. Такой подход может привести к довольно длительному времени выполнения для тестового примера;
вычислить небольшую серию образцов "вручную" и проверить, воспроизводит ли алгоритм PRNG. Такой подход может привести к созданию не случайной последовательности, не будучи замеченной;

Я бы сказал, что первый подход не является модульным тестированием, потому что он не выполняет тест белого ящика генератора, но, с другой стороны, он правильно проверяет ответственность класса. Второй подход больше похож на реальный unit test, сфокусированный на алгоритме, но он не дает столько доказательств, что класс выполняет свою ответственность.

Какой подход вы предпочитаете и почему?

Ответ 1

Получите еще одну реализацию одного и того же алгоритма PRNG, создайте небольшое количество длинных тестовых примеров на основе известных семян и убедитесь, что ваша реализация алгоритма соответствует всем остальным реализациям. Чем больше данных вы тестируете, тем больше шансов. Если вы хотите быть серьезным, посмотрите, как выполняется проверка FIPS для алгоритма.

Нет необходимости проверять, является ли вывод случайным, поскольку гораздо больше исследований было сделано по алгоритму другими, чем вы способны воспроизводить.

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

Ответ 2

Для тестирования PRNG я бы использовал ENT, который представляет собой набор статистических тестов, которые расскажут вам, насколько хорошо работает ваш PRNG. Я полагаю, что это подход 1.

Ответ 3

Я бы предположил, что в конечном итоге вам понадобятся оба теста - потому что вы хотите быть уверенными в том, что выполняются следующие условия:

(1) номера правильно распределены и (2) конкретный алгоритм работает как ожидалось.

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

Ответ 4

Я полагаю, что ваша первая точка (№ 1) получает больше от тестирования качества генерируемых случайных чисел, что определяется используемым алгоритмом. Вторая точка (№ 2) получает больше от тестирования реализации алгоритма. Если вы разработали алгоритм, оба теста важны. Если вы реализовали алгоритм продемонстрированной производительности, № 2 должно быть достаточно. Хотя, вероятно, я бы испытал больше, чем несколько семян, и последовательности, которые привели к некоторому знанию структуры вашего конкретного генератора.

Ответ 5

"Случайность" в генераторе псевдослучайных чисел обычно выражается как среднее число итераций до повторения числа. Существует множество алгоритмов, которые имеют разную "случайность" и производительность. Random.org имеет хорошее объяснение некоторого анализа, выполненного по их алгоритмам. Посмотрите фотографии примерно на половину страницы. Легко видеть в статических изображениях, насколько случайны оба алгоритма.

Одна особенность PRNG (истинная функция, а не ошибка, замаскированная под функцию) заключается в том, что она предсказуема. Для данного семени необходимо создать такую же последовательность чисел. Это чрезвычайно важно и необходимо для тестирования и отладки программ, использующих стохастические (ака, случайные) методы.

Последовательность чисел должна аппроксимировать определенное статистическое распределение. Проверьте свой PRNG, создав большую последовательность (например, 10 ^ 6 номеров) и выполните несколько статистических тестов в последовательности, в частности, тест Chi-Squared (если распределение является нормальным). Сделайте гистограмму своего образца и посмотрите, похоже ли оно, как вы ожидаете.

Если вы определяете, как задается семя, генерируемая последовательность должна быть одинаковой каждый раз, что подходит для тестирования белого ящика. При выполнении тестов также рекомендуется "разогреть" генератор, запустив его на 100 итераций или около того, прежде чем собирать ваш образец.

Ответ 6

Здесь статья CodeProject, которая включает в себя реализацию теста Колмогорова-Смирнова, упомянутого в томе 2 Дональда Кнут, Seminumerical Algorithms. Как упоминалось выше в InSciTek Jeff, есть две проблемы: тестирование алгоритма и тестирование вашей реализации алгоритма. Тест K-S, вероятно, обнаружит ошибки в реализации, и это хороший старт для тестирования качества самого алгоритма.

Ответ 7

Plesae должен знать: если вы "изобрели" ваш PRNG, вы, вероятно, ошибетесь и произведете что-то, что имеет менее оптимальное распределение. Основным критерием того, насколько случайным является ваш генератор, является тест Chi-Square

Ответ 8

Вы можете найти ответы на этот вопрос полезным.

В принципе, вы не можете "доказать", что RNG случайный, но вы можете выполнять различные тесты, чтобы повысить свою уверенность в том, что это так. Эти тесты различаются по сложности. Diehard является исчерпывающим, но на самом деле он не предлагает ответ "да/нет", более похожий на пару сотен "майнов". На другом конце спектра довольно просто создать последовательность значений (по меньшей мере, 10 000), а затем проверить, являются ли средние и стандартные отклонения/дисперсии как ожидалось.

Ответ 9

Строго говоря, нет способа проверить, действительно ли случайный генератор является случайным:-) Первый подход дает вам знания о том, может ли он правильно распределять keed или нет только для фиксированного количества выборок, независимо от того, насколько велика эта величина. Второй подход может помочь узнать, ведет ли он себя как алгоритм, но опять же для фиксированного количества выборок.

Лучшее, что вы можете сделать - используйте оба.

Ответ 10

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

Я получил яркое представление о двух случайных числах и их графике (x, y). Удивительно, как человеческий мозг может обнаружить неслучайные картины. ( "Случайный шаблон" является оксюмороном.)

Я подкрепил PRNG, чтобы удалить страты и звездообразования, появившиеся на графике, затем построил график (log (x), log (y)) для новой перспективы и повторил процесс.

Позже я был вынужден взять статистику и узнал, что вы можете сделать странную математику для количественной оценки случайности.

Ответ 11

Random.org использует этот тест: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

Вы можете загрузить программное обеспечение (unix и mac os x) в: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/sts-2.1.1.zip

Документация находится здесь: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

Ответ 12

Один из способов заключается в том, чтобы передать его вывод в PractRand.

Если PractRand говорит, что вывод PRNG в порядке, PRNG действительно ОК? Я не могу судить, но я могу сказать, что PRNG достаточно требователен, что он считает неудовлетворительным вывод различных LFSR и алгоритмов xor-and-shift, которые я нашел в литературе или в Интернете, и считал, что это нормально. от RP Brent xorgens.

Ответ 13

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

Если вы реализуете известный алгоритм, проверьте, что первые несколько тысяч номеров соответствуют полученным им результатам, учитывая набор семян. нет никакого способа быть уверенным, хотя, поскольку количество возможных семян бесконечно.

Вы даже не можете математически предсказать, что последовательность чисел случайна...

XKCD

Дилберта

Получает модификацию вниз...