Как количественно оценить качество генератора псевдослучайных чисел? - PullRequest
Новая
       24

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

5 голосов
/ 07 февраля 2009

Это основано на этом вопросе . Был предложен ряд ответов, которые генерируют неравномерное распределение, и я начал задаваться вопросом, как количественно оценить неравномерность выходных данных. Я не ищу проблемы с шаблонами, а просто аспекты с одним значением.

Какие процедуры принимаются?

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

Мои опасения

  1. Это правильно?
  2. Как вычислить эти значения без потери точности?

Для # 1 мне интересно, правильно ли я понял.

Для # 2 проблема в том, что я буду обрабатывать числа с величинами, такими как 1/7 +/- 1e-18, и я беспокоюсь, что ошибки с плавающей запятой убьют меня для любых, кроме самых маленьких проблем. Точная форма вычислений может привести к некоторым существенным различиям здесь, и я, кажется, напоминаю, что есть некоторые опции ASM для некоторых особых случаев регистрации, но я не могу найти документы по этому поводу.

В этом случае используется «хороший» PRNG для диапазона [1,n] и генерация SRNG для диапазона [1,m]. Вопрос в том, насколько результаты хуже, чем ввод?

То, что у меня есть, - это ожидаемые частоты появления для каждого выходного значения.

Ответы [ 3 ]

4 голосов
/ 07 февраля 2009

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 полная, хотя и несколько плотная.

-Adam

1 голос
/ 07 февраля 2009

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

0 голосов
/ 04 мая 2011

TestU01 имеет еще более точный набор тестов, чем Dieharder. Самый большой набор тестов называется «BigCrush», но его выполнение занимает много времени, поэтому существуют также подмножества, называемые просто «Crush» и «SmallCrush». Идея состоит в том, чтобы сначала попробовать SmallCrush, и если PRNG это пройдет, попробуйте Crush, а если он пройдет это, BigCrush. Если и это пройдет, это должно быть достаточно хорошо.

Вы можете получить TestU01 здесь .

...