Как количественно оценить качество генератора псевдослучайных чисел?
Это основано на этом вопросе. Был предложен ряд ответов, которые генерируют неравномерное распределение, и я начал задаваться вопросом, как количественно оценить неравномерность выходных данных. Я не ищу проблемы с шаблонами, а просто аспекты с одним значением.
Каковы принятые процедуры?
В настоящее время я думаю о том, чтобы вычислить среднюю энтропию Шеннона на один вызов, вычислив энтропию каждого значения и взяв средневзвешенное значение. Затем это может быть сопоставлено с ожидаемым значением.
Мои опасения
- Это правильно?
- Как вычислить эти значения без потери точности?
Для #1 мне интересно, правильно ли я понял.
Для #2 проблема в том, что я буду обрабатывать числа с величинами, такими как 1/7 +/- 1e-18, и я беспокоюсь, что ошибки с плавающей запятой убьют меня для любых, кроме самых маленьких проблем. Точная форма вычисления может привести к некоторым существенным различиям здесь, и я, кажется, напоминаю, что есть некоторые опции ASM для некоторых особых случаев регистрации, но я не могу найти документы по этому поводу.
В этом случае использовать "хороший" PRNG для диапазона [1,n] и создать SRNG для диапазона [1,m], Вопрос в том, насколько хуже результаты, чем вход?
То, что у меня есть, это ожидаемые показатели появления для каждого выходного значения
3 ответа
В NIST есть набор документов и инструментов для статистического анализа генераторов случайных чисел по различным показателям.
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html
Многие из этих тестов также включены в набор тестов Dieharder PRNG.
http://www.phy.duke.edu/~rgb/General/rand_rate.php
Существует множество различных метрик, потому что есть много, много разных способов использования PRNG. Вы не можете анализировать PRNG в вакууме - вы должны понимать вариант использования. Эти инструменты и документы предоставляют много информации, чтобы помочь вам в этом, но в конце концов вам все равно придется понять, что вам действительно нужно, прежде чем вы сможете определить подходящий алгоритм. Документация NIST является полной, хотя и несколько плотной.
-Адам
На этой странице обсуждается один способ проверки, если вы получаете неправильное распределение: построение псевдослучайных значений в поле, а затем просто просмотр их.
TestU01 имеет еще более точный набор тестов, чем Dieharder. Самый большой набор тестов называется "BigCrush", но его выполнение занимает много времени, поэтому существуют также подмножества, называемые просто "Crush" и "SmallCrush". Идея состоит в том, чтобы сначала попробовать SmallCrush, и, если PRNG это пройдет, попробуйте Crush, а если это пройдет, BigCrush. Если и это пройдет, это должно быть достаточно хорошо.
Вы можете получить TestU01 здесь.