357 lines
18 KiB
Plaintext
357 lines
18 KiB
Plaintext
[/
|
|
/ Copyright (c) 2009 Steven Watanabe
|
|
/
|
|
/ Distributed under the Boost Software License, Version 1.0. (See
|
|
/ accompanying file LICENSE_1_0.txt or copy at
|
|
/ http://www.boost.org/LICENSE_1_0.txt)
|
|
]
|
|
|
|
[section Introduction]
|
|
|
|
Random numbers are required in a number of different problem domains, such as
|
|
|
|
* numerics (simulation, Monte-Carlo integration)
|
|
* games (non-deterministic enemy behavior)
|
|
* security (key generation)
|
|
* testing (random coverage in white-box tests)
|
|
|
|
The Boost Random Number Generator Library provides a framework for random
|
|
number generators with well-defined properties so that the generators can be
|
|
used in the demanding numerics and security domains. For a general
|
|
introduction to random numbers in numerics, see
|
|
|
|
[:"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]
|
|
|
|
Depending on the requirements of the problem domain, different variations of
|
|
random number generators are appropriate:
|
|
|
|
* non-deterministic random number generator
|
|
* pseudo-random number generator
|
|
* quasi-random number generator
|
|
|
|
All variations have some properties in common, the concepts (in the STL
|
|
sense) is called __UniformRandomNumberGenerator. This
|
|
concept will be defined in a subsequent section.
|
|
|
|
The goals for this library are the following:
|
|
|
|
* allow easy integration of third-party random-number generators
|
|
* provide easy-to-use front-end classes which model popular distributions
|
|
* provide maximum efficiency
|
|
|
|
[endsect]
|
|
|
|
[section Uniform Random Number Generator]
|
|
|
|
A uniform random number generator provides a
|
|
sequence of random numbers uniformly distributed on a given range. The
|
|
range can be compile-time fixed or available (only) after run-time construction
|
|
of the object.
|
|
|
|
The /tight lower bound/ of some (finite) set S is the (unique) member l in S, so
|
|
that for all v in S, l <= v holds. Likewise, the /tight upper bound/ of some
|
|
(finite) set S is the (unique) member u in S, so that for all v in S, v <= u
|
|
holds.
|
|
|
|
In the following table, X denotes a number generator class returning objects
|
|
of type T, and v is a const value of X.
|
|
|
|
[table UniformRandomNumberGenerator requirements
|
|
[[expression] [return type] [pre/post-condition]]
|
|
[[`X::result_type`] [`T`] [`std::numeric_limits<T>::is_specialized` is
|
|
`true`, `T` is __LessThanComparable]]
|
|
[[`u.operator()()`] [`T`] [-]]
|
|
[[`v.min()`] [`T`] [tight lower bound on the set of all values returned by
|
|
`operator()`. The return value of this function shall not
|
|
change during the lifetime of the object.]]
|
|
[[`v.max()`] [`T`] [if `std::numeric_limits<T>::is_integer`, tight upper
|
|
bound on the set of all values returned by `operator()`,
|
|
otherwise, the smallest representable number larger than
|
|
the tight upper bound on the set of all values returned
|
|
by `operator()`. In any case, the return value of this
|
|
function shall not change during the lifetime of the
|
|
object.]]
|
|
]
|
|
|
|
The member functions `min`, `max`, and `operator()` shall have amortized
|
|
constant time complexity.
|
|
|
|
[note For integer generators (i.e. integer `T`), the generated values `x`
|
|
fulfill `min() <= x <= max()`, for non-integer generators (i.e. non-integer
|
|
`T`), the generated values `x` fulfill `min() <= x < max()`.
|
|
|
|
Rationale: The range description with min and max serves two purposes. First,
|
|
it allows scaling of the values to some canonical range, such as [0..1).
|
|
Second, it describes the significant bits of the values, which may be
|
|
relevant for further processing.
|
|
|
|
The range is a closed interval \[min,max\] for integers, because the underlying
|
|
type may not be able to represent the half-open interval \[min,max+1). It is
|
|
a half-open interval \[min, max) for non-integers, because this is much more
|
|
practical for borderline cases of continuous distributions.]
|
|
|
|
[note The __UniformRandomNumberGenerator concept does not require
|
|
`operator()(long)` and thus it does not fulfill the `RandomNumberGenerator`
|
|
(std:25.2.11 \[lib.alg.random.shuffle\]) requirements. Use the
|
|
__random_number_generator adapter for that.
|
|
|
|
Rationale: `operator()(long)` is not provided, because mapping the output of
|
|
some generator with integer range to a different integer range is not trivial.]
|
|
|
|
[endsect]
|
|
|
|
[section Non-deterministic Uniform Random Number Generator]
|
|
|
|
A non-deterministic uniform random number generator is a
|
|
__UniformRandomNumberGenerator that is based on some stochastic process.
|
|
Thus, it provides a sequence of truly-random numbers. Examples for such
|
|
processes are nuclear decay, noise of a Zehner diode, tunneling of quantum
|
|
particles, rolling a die, drawing from an urn, and tossing a coin. Depending
|
|
on the environment, inter-arrival times of network packets or keyboard events
|
|
may be close approximations of stochastic processes.
|
|
|
|
The class __random_device is a model for a non-deterministic random number
|
|
generator.
|
|
|
|
[note This type of random-number generator is useful for security
|
|
applications, where it is important to prevent an outside attacker from
|
|
guessing the numbers and thus obtaining your encryption or authentication key.
|
|
Thus, models of this concept should be cautious not to leak any information,
|
|
to the extent possible by the environment. For example, it might be advisable
|
|
to explicitly clear any temporary storage as soon as it is no longer needed.]
|
|
|
|
[endsect]
|
|
|
|
[section Pseudo-Random Number Generator]
|
|
|
|
A pseudo-random number generator is a __UniformRandomNumberGenerator which
|
|
provides a deterministic sequence of pseudo-random numbers, based on some
|
|
algorithm and internal state.
|
|
[classref boost::random::linear_congruential_engine
|
|
Linear congruential] and [classref boost::random::inversive_congruential_engine
|
|
inversive congruential] generators are examples of such [prng pseudo-random
|
|
number generators]. Often, these generators are very sensitive to their
|
|
parameters. In order to prevent wrong implementations from being used, an
|
|
external testsuite should check that the generated sequence and the validation
|
|
value provided do indeed match.
|
|
|
|
Donald E. Knuth gives an extensive overview on pseudo-random number generation
|
|
in his book "The Art of Computer Programming, Vol. 2, 3rd edition,
|
|
Addison-Wesley, 1997". The descriptions for the specific generators contain
|
|
additional references.
|
|
|
|
[note Because the state of a pseudo-random number generator is necessarily
|
|
finite, the sequence of numbers returned by the generator will loop
|
|
eventually.]
|
|
|
|
In addition to the __UniformRandomNumberGenerator requirements,
|
|
a pseudo-random number generator has some additional requirements. In the
|
|
following table, `X` denotes a pseudo-random number generator class,
|
|
`u` is a value of `X`, `i` is a value of integral type, `s` is a value
|
|
of a type which models __SeedSeq, and `j` a value of
|
|
type `unsigned long long`.
|
|
|
|
[table PseudoRandomNumberGenerator requirements
|
|
[[expression] [return type] [pre/post-condition]]
|
|
[[`X()`] [-] [creates a generator with a default seed.]]
|
|
[[`X(i)`] [-] [creates a generator seeding it with the integer `i`.]]
|
|
[[`X(s)`] [-] [creates a generator setting its initial state from the
|
|
__SeedSeq `s`.]]
|
|
[[`u.seed(...)`] [`void`] [sets the current state to be identical to the
|
|
state that would be created by the corresponding
|
|
constructor.]]
|
|
[[`u.discard(j)`] [`void`] [Advances the generator by `j` steps as if by
|
|
`j` calls to `u()`.]]
|
|
]
|
|
|
|
Classes which model a pseudo-random number generator shall also model
|
|
__EqualityComparable, i.e. implement `operator==`. Two pseudo-random number
|
|
generators are defined to be /equivalent/ if they both return an identical
|
|
sequence of numbers starting from a given state.
|
|
|
|
Classes which model a pseudo-random number generator shall also model the
|
|
__Streamable concept, i.e. implement `operator<<` and `operator>>`.
|
|
`operator<<` writes all current state of the pseudo-random number generator
|
|
to the given `ostream` so that `operator>>` can restore the state at a later
|
|
time. The state shall be written in a platform-independent manner, but it is
|
|
assumed that the `locales` used for writing and reading be the same. The
|
|
pseudo-random number generator with the restored state and the original at
|
|
the just-written state shall be equivalent.
|
|
|
|
Classes which model a pseudo-random number generator should also model the
|
|
__CopyConstructible and __Assignable concepts. However, note that the
|
|
sequences of the original and the copy are strongly correlated (in fact,
|
|
they are identical), which may make them unsuitable for some problem domains.
|
|
Thus, copying pseudo-random number generators is discouraged; they should
|
|
always be passed by (non-const) reference.
|
|
|
|
The classes __rand48, __minstd_rand, and __mt19937 are models for a
|
|
pseudo-random number generator.
|
|
|
|
[note This type of random-number generator is useful for numerics, games and
|
|
testing. The non-zero arguments constructor(s) and the `seed()` member
|
|
function(s) allow for a user-provided state to be installed in the generator.
|
|
This is useful for debugging Monte-Carlo algorithms and analyzing particular
|
|
test scenarios. The __Streamable concept allows to save/restore the state of
|
|
the generator, for example to re-run a test suite at a later time.]
|
|
|
|
[endsect]
|
|
|
|
[section Quasi-Random Number Generator]
|
|
|
|
A quasi-random number generator is a __UniformRandomNumberGenerator which
|
|
provides a deterministic sequence of quasi-random numbers, based on some
|
|
algorithm and internal state. [classref boost::random::niederreiter_base2_engine
|
|
Niederreiter base 2] generator is an example of such a [qrng quasi-random
|
|
number generator]. The "quasi" modifier is used to denote more clearly that the
|
|
values produced by such a generator are neither random nor pseudo-random, but
|
|
they form a low discrepancy sequence. The intuitive idea is that a low discrepancy
|
|
sequence is more evenly distributed than a pseudo random sequence would be.
|
|
For example, if we generate a low discrepancy sequence of 2D points on a square,
|
|
this square would be covered more evenly, and the number of points falling to any
|
|
part of the square would be proportional to the number of points in the whole square.
|
|
Such sequences share some properties of random variables and in certain applications
|
|
such as the quasi-Monte Carlo method their lower discrepancy is an important advantage.
|
|
|
|
[note The quasi-Monte Carlo method uses a low-discrepancy sequence such as the
|
|
Niederreiter base 2 sequence, the Sobol sequence, or the Faure sequence among the others.
|
|
The advantage of using low-discrepancy sequences is a probabilistically faster rate of
|
|
convergence. Quasi-Monte Carlo has a rate of convergence O(log(N)[sup s]/N),
|
|
whereas the rate of convergence for the Monte Carlo method, which uses a pseudo-random sequence,
|
|
is O(N[sup -0.5]).]
|
|
|
|
Harold Niederreiter gives an extensive overview on random number generation
|
|
and quasi-Monte Carlo methods in his book "Random number generation and
|
|
quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, 1992".
|
|
|
|
In addition to the __UniformRandomNumberGenerator requirements,
|
|
a quasi-random number generator has some additional requirements. In the
|
|
following table, `X` denotes a quasi-random number generator class, `u` is a value of `X`,
|
|
`v` is a const value of `X`, and `j` a value of type `unsigned long long`.
|
|
|
|
[table QuasiRandomNumberGenerator requirements
|
|
[[expression] [return type] [pre/post-condition]]
|
|
[[`X(s)`] [-] [creates an `s`-dimensional generator with a default seed. Dimension `s` is an integer no less than 1.]]
|
|
[[`v.dimension()`] [std::size_t] [the dimension of quasi-random domain.]]
|
|
[[`u.seed(i)`] [`void`] [seeds the generator with the integer `i`.]]
|
|
[[`u.discard(j)`] [`void`] [Advances the generator by `j` steps as if by
|
|
`j` calls to `u()`.]]
|
|
]
|
|
|
|
[note The `operator()` returns a successive element of an `s`-dimensional (`s` = `v.dimension()`) vector
|
|
at each invocation. When all elements are exhausted, `operator()` begins anew with the starting
|
|
element of a subsequent `s`-dimensional vector.]
|
|
|
|
Classes which model a quasi-random number generator shall also model
|
|
__EqualityComparable, i.e. implement `operator==`. Two quasi-random number
|
|
generators are defined to be /equivalent/ if they both return an identical
|
|
sequence of numbers starting from a given state.
|
|
|
|
Classes which model a quasi-random number generator shall also model the
|
|
__Streamable concept, i.e. implement `operator<<` and `operator>>`.
|
|
`operator<<` writes all current state of the quasi-random number generator
|
|
to the given `ostream` so that `operator>>` can restore the state at a later
|
|
time. The state shall be written in a platform-independent manner, but it is
|
|
assumed that the `locales` used for writing and reading be the same. The
|
|
quasi-random number generator with the restored state and the original at
|
|
the just-written state shall be equivalent.
|
|
|
|
Classes which model a quasi-random number generator should also model the
|
|
__CopyConstructible and __Assignable concepts. However, note that the
|
|
sequences of the original and the copy are strongly correlated (in fact,
|
|
they are identical), which may make them unsuitable for some problem domains.
|
|
Thus, copying quasi-random number generators is discouraged; they should
|
|
always be passed by (non-const) reference.
|
|
|
|
The classes __niederreiter_base2, __sobol, __faure are models for a quasi-random number generator.
|
|
|
|
[endsect]
|
|
|
|
[section Seed Sequence]
|
|
|
|
A SeedSeq represents a sequence of values that can be used to
|
|
set the initial state of a __PseudoRandomNumberGenerator.
|
|
`i` and `j` are RandomAccessIterators whose `value_type` is
|
|
an unsigned integer type with at least 32 bits.
|
|
|
|
[table SeedSeq requirements
|
|
[[expression] [return type] [pre/post-condition] [complexity]]
|
|
[[`s.generate(i, j)`] [void] [stores 32-bit values to all the elements
|
|
in the iterator range defined by `i` and `j`]
|
|
[O(j - i)]]
|
|
]
|
|
|
|
The class __seed_seq and every __UniformRandomNumberGenerator
|
|
provided by the library are models of __SeedSeq.
|
|
|
|
[endsect]
|
|
|
|
[section Random Distribution]
|
|
|
|
A random distribution produces random numbers distributed according to some
|
|
distribution, given uniformly distributed random values as input. In the
|
|
following table, `X` denotes a random distribution class returning objects of
|
|
type `T`, `u` is a value of `X`, `x` and `y` are (possibly const) values of
|
|
`X`, `P` is the `param_type` of the distribution, `p` is a value of `P`, and
|
|
`e` is an lvalue of an arbitrary type that meets the requirements of a
|
|
__UniformRandomNumberGenerator, returning values of type `U`.
|
|
|
|
[table Random distribution requirements (in addition to CopyConstructible, and Assignable)
|
|
[[expression] [return type] [pre/post-condition] [complexity]]
|
|
[[`X::result_type`] [`T`] [-] [compile-time]]
|
|
[[`X::param_type`] [`P`] [A type that stores the parameters of the
|
|
distribution, but not any of the state used to
|
|
generate random variates. `param_type` provides
|
|
the same set of constructors and accessors as
|
|
the distribution.]
|
|
[compile-time]]
|
|
[[`X(p)`] [`X`] [Initializes a distribution from its parameters]
|
|
[O(size of state)]]
|
|
[[`u.reset()`] [`void`] [subsequent uses of `u` do not depend on values
|
|
produced by any engine prior to invoking `reset`.]
|
|
[constant]]
|
|
[[`u(e)`] [`T`] [the sequence of numbers returned by successive invocations
|
|
with the same object `e` is randomly distributed with the
|
|
probability density function of the distribution]
|
|
[amortized constant number of invocations of `e`]]
|
|
[[`u(e, p)`] [`T`] [Equivalent to X(p)(e), but may use a different (and
|
|
presumably more efficient) implementation]
|
|
[amortized constant number of invocations of `e` +
|
|
O(size of state)]]
|
|
[[`x.param()`] [`P`] [Returns the parameters of the distribution]
|
|
[O(size of state)]]
|
|
[[`x.param(p)`] [void] [Sets the parameters of the distribution]
|
|
[O(size of state)]]
|
|
[[`x.min()`] [`T`] [returns the minimum value of the distribution] [constant]]
|
|
[[`x.max()`] [`T`] [returns the maximum value of the distribution] [constant]]
|
|
[[`x == y`] [`bool`] [Indicates whether the two distributions will produce
|
|
identical sequences of random variates if given
|
|
equal generators]
|
|
[O(size of state)]]
|
|
[[`x != y`] [`bool`] [`!(x == y)`] [O(size of state)]]
|
|
[[`os << x`] [`std::ostream&`] [writes a textual representation for the
|
|
parameters and additional internal data of
|
|
the distribution `x` to `os`.
|
|
post: The `os.fmtflags` and fill character
|
|
are unchanged.]
|
|
[O(size of state)]]
|
|
[[`is >> u`] [`std::istream&`] [restores the parameters and additional
|
|
internal data of the distribution `u`.
|
|
pre: `is` provides a textual representation
|
|
that was previously written by `operator<<`
|
|
post: The `is.fmtflags` are unchanged.]
|
|
[O(size of state)]]
|
|
]
|
|
|
|
Additional requirements: The sequence of numbers produced by repeated
|
|
invocations of `x(e)` does not change whether or not `os << x` is invoked
|
|
between any of the invocations `x(e)`. If a textual representation is written
|
|
using `os << x` and that representation is restored into the same or a
|
|
different object `y` of the same type using `is >> y`, repeated invocations
|
|
of `y(e)` produce the same sequence of random numbers as would repeated
|
|
invocations of `x(e)`.
|
|
|
|
[endsect]
|