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