EQ2EMu/EQ2/source/depends/boost_1_72_0/libs/random/doc/concepts.qbk

[/
 / 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]