Введение
Случайные числа требуются при решении различных задач в нескольких областях, таких как:
Библиотека Boost.Random содержит набор инструментов построения генераторов случайных чисел с определенными свойствами, которые могут быть использованы в разных областях. Для более детального знакомства с применением случайных чисел в численных методах см.
"Numerical Recipes in C: The art of scientific computing", William H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992, pp. 274-328
В зависимости от потребностей конкретной области применения могут понадобиться разные виду генераторов:
При всем разнообразии все генераторы имеют некоторые общие свойства. Эти общие свойства (концепции в смысле STL) собраны в классы NumberGenerator и UniformRandomNumberGenerator. Каждая концепция будет описана в последующих разделах.
Далее приведен краткий список целей при создании библиотеки Boost.Random:
Генератор чисел это функциональный объект (std:20.3
[lib.function.objects]), который получает 0 аргументов. Каждый вызов
operator() возвращает число. В следующей таблице X
обозначает класс генератора чисел, возвращающий объект типа
T, и u является объектом класса
X.
NumberGenerator
requirements | ||
|---|---|---|
| выражение | возвращаемый тип | пред- и послеусловия |
X::result_type | T | std::numeric_limits<T>::is_specialized is true,
T is LessThanComparable |
u.operator()() | T | - |
Замечание: Требования к классу NumberGenerator не подразумевают какие-либо ограничения на характеристики возвращаемых чисел.
Генератор равномерно распределенных чисел
Генератор равномерно распределенных чисел это реализация NumberGenerator, которая возвращает последовательность случайных чисел, распределенных равномерно в заданном диапазоне. Диапазон может задаваться либо константой при компиляции, либо определяться динамически после создания объекта класса генератора.
Закрытой (tight) нижней границей некоторого (конечного) множества S называется единственный член l множества S, такой, что для всех v, принадлежащих S, справедливо условие l <= v. Аналогично, зарытой верхней границей некоторого (конечного) множества S называется член u множества S, такой что для всех членов множества справедливо условие l<=u.
В следующей таблице X обозначает класс генератора чисел, возвращающий объекты типа T, v означает константный объект класса X.
Требования к UniformRandomNumberGenerator
| ||
|---|---|---|
| выражение | возвращаемое значение | пред- и послеусловия |
X::has_fixed_range | bool | константа времени исполнения; если true, то диапазон, в котором равномерно распределяются случайные числа, известен на стадии компиляции, и члены класса min_value и max_value существуют. Замечание: этот флаг может также быть false по причине накладываемых компилятором ограничений. |
X::min_value | T | константа времени компиляции; min_value равна v.min() |
X::max_value | T | константа времени исполнения; max_value равна v.max() |
v.min() | T | закрытая нижняя граница множества возвращаемых методом operator() значений. Возвращаемое этим методом значение не меняется все время существования объекта. |
v.max() | T | если std::numeric_limits<T>::is_integer равно true, то возвращается верхняя закрытая граница множества всех значений, возвращаемых методом operator(), в противном случае возвращается наименьшее представимое число, большее чем верхняя закрытая граница всех возвращаемых методом operator() значений. В любом случае, возвращаемое значение не меняется в течение всего времени жизни объекта генератора. |
Функции-члены min, max, и operator() должны иметь вычислительную сложность o(n).
Замечание: для целочисленных генераторов (то есть когда
T - целый тип),
генерируемые значения
x заполняют диапазон min() <= x <= max(),
для генераторов с плавающей точкой (то есть когда
T - тип с плавающей точкой) генерируемые
значения x
заполняют диапазон min() <= x < max().
Данное ослабление требований для целочисленных генераторов продиктовано
исключительно требованиями счетной эффективности - в силу характера алгоритмов
отсекать максимальные значения пришлось бы с помощью условного оператора,
который исполнялся бы чрезвычайно редко, а для
современных процессоров условный оператор часто означает сильное падение
эффективности кэша кода.
Rationale: Описание диапазона с помощью методов
min и max преследует две цели.
Во-первых, это позволяет масштабировать генерируемые
значения на некоторый канонический диапазон, такой как
[0..1). Во-вторых, так описывается число значащих битов в генерируемых
числах, что может иметь значение для дальнейших
вычислений.
Диапазон является закрытым для целочисленных генераторов [min,max], потому что тип генерируемых чисел может быть неспособен представить значение для полуоткрытого интервала [min,max+1). Для действительных случайных чисел диапазон представимых значений является полуоткрытым [min, max), так как это удобнее иметь границу для непрерывного распределения.
Замечание: Концепция UniformRandomNumberGenerator
не требует реализации оператора
operator()(long) и поэтому она не соответствует требованиям класса
RandomNumberGenerator
(std:25.2.11 [lib.alg.random.shuffle]). Класс-адаптер
random_number_generator
устраняет это несоответствие.
Rationale: operator()(long) не реализован, потому что отображение выходных значений некоторых целочисленных генераторов на другой целый тип является нетривиальной задачей.
Стохастические генераторы равномерно распределенных случайных чисел
Недетерминистский генератор равномерно распределенных чисел является реализацией концепции UniformRandomNumberGenerator, базирующейся на каком-либо стохастическом процессе. Таким образом, этот генератор возвращает последовательность истинно случайных чисел. Примерами таких процессов являются ядерный распад, белый шум, производимый некоторыми полупроводниковыми приборами, квантовые эффекты туннелирования, вращение рулетки, вынимание из урны, подкидывание монеты. В зависимости от свойств платформы, внутреннее время доставки пакетов в сети или клавиатурные события могут быть достаточно близкими приближениями стохастических процессов.
Класс random_device
представляет из себя модель недетерминированного генератора равномерно
распределенных чисел.
Замечание: Этот тип генератора случайных чисел полезен для приложений в области безопасности, где важно предотвратить возможность для внешнего злоумышленника подобрать набор чисел и таким образом получить ключ шифрования или аутентификации. В итоге, генераторы данного вида должны не допускать возможную утечку информации, в пределах, допускаемых платформой. К примеру, можено посоветовать очищать временное хранилище сразу после того, как необходимость в нем отпала.
Генератор псевдослучайных чисел
Генератор псевдослучайных чисел это UniformRandomNumberGenerator, который детерминированную последовательность псевдослучайных чисел, используя некоторый алгоритм и скрытые параметры (внутренее состояние). Линейный конгруентный и обращаемый конгруентный (inversive congruential) генераторы являются примерами генерторов псевдослучайных чисел. Зачастую эти генераторы очень чувствительны к значениям параметров алгоритма. Для того, чтобы предотвратить возможность некорректной реализации, следует использовать внешний набор тестов, которые проверят генерируемые последовательности чисел.
Дональд Кнут (Donald E. Knuth) сделал широкий обзор методов генерации псевдослучайных чисел в книге "The Art of Computer Programming, Том 2. Описания некоторых реализаций генераторов содержат ссылки на использованную литературу.
Замечание: Так как число состояний генераторов псевдослучайных чисел естественно ограничено, то последовательность возвращаемых генератором чисел рано или поздно повторяется.
В дополнение к требованиям UniformRandomNumberGenerator, любой генератор
псевдослучайных чисел имеет некоторые дополнительные требования.
В следующей таблице
X обозначает класс генератора псевдослучайных чисел,
возвращающий объекты типа T,
x является объектом типа T,
u является
объектом типа
X, и v является константным объектом типа
X.
PseudoRandomNumberGenerator
requirements | ||
|---|---|---|
| выражение | возвращаемое значение | пред- и послеусловия |
X() | -d>- | создается генератор в некотором предустановленном состоянии. Замечание: некоторые генераторы, созданные таким образом, могут производить коррелированные либо идентичные последовательности чисел. |
explicit X(...) | - | создается генератор в состоянии, зависящем от указанных пользователем параметров; список аргументов зависит от конкретной реализации. |
u.seed(...) | void | переводит генератор в состояние, определяемое указанными аргументами; по меньшей мере один метод с тем же списком аргументов, что и не-дефолтный конструктор, должен быть объявлен. |
X::validation(x) | bool | сравнивает предварительно вычисленное и закодированное в реализации 10001-ое
значение в последовательности со значением x. Чтобы проверка данным
методом имела смысл, генератор должен
быть создан конструктором по умолчанию, и для него не
должен вызываться метод seed.
|
Замечание: Метод seed похож на метод assign у STL контейнеров. Однако такое название метода не кажется подходящим.
Классы, которые моделируют генераторы псевдослучайных чисел, также моделируют EqualityComparable, то есть реализуют метод operator==. Два генератора псевдослучайных чисел считаются эквивалентными, если они оба возвращают идентичные последовательности чисел, начав с одинакового состояния.
Классы, которые моделируют генераторы псевдослучайных
чисел, также должны моделировать концепцию
Streamable, то есть реализовывать методы
operator<<
и operator>>. В данном случае,
operator<< записывает полное внутренее состояние генератора
псевдослучайных чисел в заданный поток ostream,
так что метод operator>> может восстановить это
состояние позднее. Состояние генератора должно быть записано в
платформо-независимом виде, но подразумевается,
что локаль при записи и считывании должна быть одинаковой. Генератор
псевдослучайных чисел с восстановленным состоянием и исходный генератор должны
быть эквивалентными.
Классы, которые моделируют генератор псевдослучайных чисел, также могут моделировать концепции CopyConstructible и Assignable. Однако, заметим что последовательность чисел, возвращаемая исходным генератором и копией сильно коррелированы (фактически, они идентичны), что может сделать копирование генераторов бесполезным для некоторых приложений. Таким образом, не следует допускать копирование генераторов псевдослучайных чисел; объекты генераторов всегда следует передавать ссылками.
Классы
rand48,
minstd_rand,
и
mt19937
являются моделями генераторов псевдослучайных чисел.
Замечание: Этот тип генераторов случайных чисел используется в численных методах, в играх и при тестировании. Конструкторы с аргументами и метод seed() позволяют установить необходимое начальное состояние генераторов. Это полезно при отладке различных реализаций метода Монте-Карло и при анализе некоторых конкретных сценариев тестирования. Концепция Streamable позволяет сохранять и восстанавливать состояние генератора, чтобы, к примеру, перезапустить набор тестов позднее.
Распределения случайных величин
Классы прспределений позволяют получать случайных числа с
заданным аналитически распределением из подаваемых на вход равномерно
распределенных чисел. В следующей таблице X
обозначает класс генератора случайных чисел,
возвращающий объекты типа T, u является объектом типа X,
x это объект (возможно константный) типа X, и e
это
lvalue произвольного типа, который удовлетворяет
требованиям генератора равномерно распределенных случайных чисел,
возвращающего объекты типа U.
Требования случайных распределений (добавочные к генераторам чисел,
CopyConstructible, и Assignable) |
|||
|---|---|---|---|
| выражение | возвращаемый тип | пред- и послеусловия | сложность |
X::input_type |
U | - | расчет выполняется во время компиляции |
u.reset() |
void |
последовательные использования u не зависят от величин, сгенерированных e перед вызовом reset. | константа |
u(e) |
T |
последовательность чисел, возвращаемых последовательными вызовами с тем же самым объектом e, имеет распределение с плотностью вероятности p(x) | константа * число вызовов
e |
os << x |
std::ostream& |
записывает текстовое представление параметров и дополнительных внутренних
данных описания распределения x
в поток os.
послеусловие: os.fmtflags и символ-заполнитель не изменяются. |
O(размер описания состояния) |
is >> u |
std::istream& |
восстанавливает параметры и дополнительные внутренние данные описания
распределения u из
потока is.
предусловие: is возвращает текстовое представление, которое ранее было записано в поток методом operator<< послеусловие: is.fmtflagsgs неизменилось. |
O(размер описания состояния) |
Дополнительные требования: последовательность возвращаемых повторяющимися вызовами x(e) чисел не меняется, если между вызовами был вызван метод os << x. Если текстовое представление записано с помощью os << x и это представление загружается в тот же или другой объект того же типа с помощью вызова is >> y, повторяющиеся вызовы y(e) генерируют ту же последовательность случайных чисел, что и вызовы исходного объекта.
Генераторы квази-случайных чисел
Генератор квазислучайных чисел это реализация NumberGenerator, которая обеспечивает детерминированную последовательность чисел, используя некоторый алгоритм и внутреннее состояние. Эти числа не имеют статистические характеристики.
Замечание: генераторы квази-случайных чисел применяются в некоторых реализациях метода Монте-Карло, в которых специальным образом сконструированные последовательности чисел улучшают сходимость вычислений. В качестве примера можно привести так называемые ЛПt последовательности.и.
Jens Maurer, 2001-08-31
Последняя правка: 10.05.2005
библиотека BOOST C++
http://www.boost.org
перевод
Elijah Koziev
www.solarix.ru
