ceph/src/boost/libs/random/doc/concepts.qbk

   1 [/
   2  / Copyright (c) 2009 Steven Watanabe
   3  /
   4  / Distributed under the Boost Software License, Version 1.0. (See
   5  / accompanying file LICENSE_1_0.txt or copy at
   6  / http://www.boost.org/LICENSE_1_0.txt)
   7 ]
   8
   9 [section Introduction]
  10
  11 Random numbers are required in a number of different problem domains, such as
  12
  13 * numerics (simulation, Monte-Carlo integration)
  14 * games (non-deterministic enemy behavior)
  15 * security (key generation)
  16 * testing (random coverage in white-box tests)
  17
  18 The Boost Random Number Generator Library provides a framework for random
  19 number generators with well-defined properties so that the generators can be
  20 used in the demanding numerics and security domains. For a general
  21 introduction to random numbers in numerics, see
  22
  23 [:"Numerical Recipes in C: The art of scientific computing", William H. Press,
  24 Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992,
  25 pp. 274-328]
  26
  27 Depending on the requirements of the problem domain, different variations of
  28 random number generators are appropriate:
  29
  30 * non-deterministic random number generator
  31 * pseudo-random number generator
  32 * quasi-random number generator
  33
  34 All variations have some properties in common, the concepts (in the STL
  35 sense) is called __UniformRandomNumberGenerator. This
  36 concept will be defined in a subsequent section.
  37
  38 The goals for this library are the following:
  39
  40 * allow easy integration of third-party random-number generators
  41 * provide easy-to-use front-end classes which model popular distributions
  42 * provide maximum efficiency
  43
  44 [endsect]
  45
  46 [section Uniform Random Number Generator]
  47
  48 A uniform random number generator provides a
  49 sequence of random numbers uniformly distributed on a given range. The
  50 range can be compile-time fixed or available (only) after run-time construction
  51 of the object.
  52
  53 The /tight lower bound/ of some (finite) set S is the (unique) member l in S, so
  54 that for all v in S, l <= v holds. Likewise, the /tight upper bound/ of some
  55 (finite) set S is the (unique) member u in S, so that for all v in S, v <= u
  56 holds.
  57
  58 In the following table, X denotes a number generator class returning objects
  59 of type T, and v is a const value of X.
  60
  61 [table UniformRandomNumberGenerator requirements
  62   [[expression] [return type] [pre/post-condition]]
  63   [[`X::result_type`] [`T`] [`std::numeric_limits<T>::is_specialized` is
  64                              `true`, `T` is __LessThanComparable]]
  65   [[`u.operator()()`] [`T`] [-]]
  66   [[`v.min()`] [`T`] [tight lower bound on the set of all values returned by
  67                       `operator()`. The return value of this function shall not
  68                       change during the lifetime of the object.]]
  69   [[`v.max()`] [`T`] [if `std::numeric_limits<T>::is_integer`, tight upper
  70                       bound on the set of all values returned by `operator()`,
  71                       otherwise, the smallest representable number larger than
  72                       the tight upper bound on the set of all values returned
  73                       by `operator()`.  In any case, the return value of this
  74                       function shall not change during the lifetime of the
  75                       object.]]
  76 ]
  77
  78 The member functions `min`, `max`, and `operator()` shall have amortized
  79 constant time complexity.
  80
  81 [note For integer generators (i.e. integer `T`), the generated values `x`
  82 fulfill `min() <= x <= max()`, for non-integer generators (i.e. non-integer
  83 `T`), the generated values `x` fulfill `min() <= x < max()`.
  84
  85 Rationale: The range description with min and max serves two purposes. First,
  86 it allows scaling of the values to some canonical range, such as [0..1).
  87 Second, it describes the significant bits of the values, which may be
  88 relevant for further processing.
  89
  90 The range is a closed interval \[min,max\] for integers, because the underlying
  91 type may not be able to represent the half-open interval \[min,max+1). It is
  92 a half-open interval \[min, max) for non-integers, because this is much more
  93 practical for borderline cases of continuous distributions.]
  94
  95 [note The __UniformRandomNumberGenerator concept does not require
  96 `operator()(long)` and thus it does not fulfill the `RandomNumberGenerator`
  97 (std:25.2.11 \[lib.alg.random.shuffle\]) requirements. Use the
  98 __random_number_generator adapter for that.
  99
 100 Rationale: `operator()(long)` is not provided, because mapping the output of
 101 some generator with integer range to a different integer range is not trivial.]
 102
 103 [endsect]
 104
 105 [section Non-deterministic Uniform Random Number Generator]
 106
 107 A non-deterministic uniform random number generator is a
 108 __UniformRandomNumberGenerator that is based on some stochastic process.
 109 Thus, it provides a sequence of truly-random numbers. Examples for such
 110 processes are nuclear decay, noise of a Zehner diode, tunneling of quantum
 111 particles, rolling a die, drawing from an urn, and tossing a coin. Depending
 112 on the environment, inter-arrival times of network packets or keyboard events
 113 may be close approximations of stochastic processes.
 114
 115 The class __random_device is a model for a non-deterministic random number
 116 generator.
 117
 118 [note This type of random-number generator is useful for security
 119 applications, where it is important to prevent an outside attacker from
 120 guessing the numbers and thus obtaining your encryption or authentication key.
 121 Thus, models of this concept should be cautious not to leak any information,
 122 to the extent possible by the environment. For example, it might be advisable
 123 to explicitly clear any temporary storage as soon as it is no longer needed.]
 124
 125 [endsect]
 126
 127 [section Pseudo-Random Number Generator]
 128
 129 A pseudo-random number generator is a __UniformRandomNumberGenerator which
 130 provides a deterministic sequence of pseudo-random numbers, based on some
 131 algorithm and internal state.
 132 [classref boost::random::linear_congruential_engine
 133 Linear congruential] and [classref boost::random::inversive_congruential_engine
 134 inversive congruential] generators are examples of such [prng pseudo-random
 135 number generators]. Often, these generators are very sensitive to their
 136 parameters. In order to prevent wrong implementations from being used, an
 137 external testsuite should check that the generated sequence and the validation
 138 value provided do indeed match.
 139
 140 Donald E. Knuth gives an extensive overview on pseudo-random number generation
 141 in his book "The Art of Computer Programming, Vol. 2, 3rd edition,
 142 Addison-Wesley, 1997". The descriptions for the specific generators contain
 143 additional references.
 144
 145 [note Because the state of a pseudo-random number generator is necessarily
 146 finite, the sequence of numbers returned by the generator will loop
 147 eventually.]
 148
 149 In addition to the __UniformRandomNumberGenerator requirements,
 150 a pseudo-random number generator has some additional requirements. In the
 151 following table, `X` denotes a pseudo-random number generator class,
 152 `u` is a value of `X`, `i` is a value of integral type, `s` is a value
 153 of a type which models __SeedSeq, and `j` a value of
 154 type `unsigned long long`.
 155
 156 [table PseudoRandomNumberGenerator requirements
 157   [[expression] [return type] [pre/post-condition]]
 158   [[`X()`] [-] [creates a generator with a default seed.]]
 159   [[`X(i)`] [-] [creates a generator seeding it with the integer `i`.]]
 160   [[`X(s)`] [-] [creates a generator setting its initial state from the
 161                  __SeedSeq `s`.]]
 162   [[`u.seed(...)`] [`void`] [sets the current state to be identical to the
 163                              state that would be created by the corresponding
 164                              constructor.]]
 165   [[`u.discard(j)`] [`void`] [Advances the generator by `j` steps as if by
 166                               `j` calls to `u()`.]]
 167 ]
 168
 169 Classes which model a pseudo-random number generator shall also model
 170 __EqualityComparable, i.e. implement `operator==`. Two pseudo-random number
 171 generators are defined to be /equivalent/ if they both return an identical
 172 sequence of numbers starting from a given state.
 173
 174 Classes which model a pseudo-random number generator shall also model the
 175 __Streamable concept, i.e. implement `operator<<` and `operator>>`.
 176 `operator<<` writes all current state of the pseudo-random number generator
 177 to the given `ostream` so that `operator>>` can restore the state at a later
 178 time. The state shall be written in a platform-independent manner, but it is
 179 assumed that the `locales` used for writing and reading be the same. The
 180 pseudo-random number generator with the restored state and the original at
 181 the just-written state shall be equivalent.
 182
 183 Classes which model a pseudo-random number generator should also model the
 184 __CopyConstructible and __Assignable concepts. However, note that the
 185 sequences of the original and the copy are strongly correlated (in fact,
 186 they are identical), which may make them unsuitable for some problem domains.
 187 Thus, copying pseudo-random number generators is discouraged; they should
 188 always be passed by (non-const) reference.
 189
 190 The classes __rand48, __minstd_rand, and __mt19937 are models for a
 191 pseudo-random number generator.
 192
 193 [note This type of random-number generator is useful for numerics, games and
 194 testing. The non-zero arguments constructor(s) and the `seed()` member
 195 function(s) allow for a user-provided state to be installed in the generator.
 196 This is useful for debugging Monte-Carlo algorithms and analyzing particular
 197 test scenarios. The __Streamable concept allows to save/restore the state of
 198 the generator, for example to re-run a test suite at a later time.]
 199
 200 [endsect]
 201
 202 [section Seed Sequence]
 203
 204 A SeedSeq represents a sequence of values that can be used to
 205 set the initial state of a __PseudoRandomNumberGenerator.
 206 `i` and `j` are RandomAccessIterators whose `value_type` is
 207 an unsigned integer type with at least 32 bits.
 208
 209 [table SeedSeq requirements
 210   [[expression] [return type] [pre/post-condition] [complexity]]
 211   [[`s.generate(i, j)`] [void] [stores 32-bit values to all the elements
 212                                 in the iterator range defined by `i` and `j`]
 213                                [O(j - i)]]
 214 ]
 215
 216 The class __seed_seq and every __UniformRandomNumberGenerator
 217 provided by the library are models of __SeedSeq.
 218
 219 [endsect]
 220
 221 [section Random Distribution]
 222
 223 A random distribution produces random numbers distributed according to some
 224 distribution, given uniformly distributed random values as input. In the
 225 following table, `X` denotes a random distribution class returning objects of
 226 type `T`, `u` is a value of `X`, `x` and `y` are (possibly const) values of
 227 `X`, `P` is the `param_type` of the distribution, `p` is a value of `P`, and
 228 `e` is an lvalue of an arbitrary type that meets the requirements of a
 229 __UniformRandomNumberGenerator, returning values of type `U`.
 230
 231 [table Random distribution requirements (in addition to CopyConstructible, and Assignable)
 232   [[expression] [return type] [pre/post-condition] [complexity]]
 233   [[`X::result_type`] [`T`] [-] [compile-time]]
 234   [[`X::param_type`] [`P`] [A type that stores the parameters of the
 235                             distribution, but not any of the state used to
 236                             generate random variates.  `param_type` provides
 237                             the same set of constructors and accessors as
 238                             the distribution.]
 239                            [compile-time]]
 240   [[`X(p)`] [`X`] [Initializes a distribution from its parameters]
 241                   [O(size of state)]]
 242   [[`u.reset()`] [`void`] [subsequent uses of `u` do not depend on values
 243                            produced by any engine prior to invoking `reset`.]
 244                          [constant]]
 245   [[`u(e)`] [`T`] [the sequence of numbers returned by successive invocations
 246                    with the same object `e` is randomly distributed with the
 247                    probability density function of the distribution]
 248                   [amortized constant number of invocations of `e`]]
 249   [[`u(e, p)`] [`T`] [Equivalent to X(p)(e), but may use a different (and
 250                       presumably more efficient) implementation]
 251                      [amortized constant number of invocations of `e` +
 252                       O(size of state)]]
 253   [[`x.param()`] [`P`] [Returns the parameters of the distribution]
 254                        [O(size of state)]]
 255   [[`x.param(p)`] [void] [Sets the parameters of the distribution]
 256                          [O(size of state)]]
 257   [[`x.min()`] [`T`] [returns the minimum value of the distribution] [constant]]
 258   [[`x.max()`] [`T`] [returns the maximum value of the distribution] [constant]]
 259   [[`x == y`] [`bool`] [Indicates whether the two distributions will produce
 260                         identical sequences of random variates if given
 261                         equal generators]
 262                        [O(size of state)]]
 263   [[`x != y`] [`bool`] [`!(x == y)`] [O(size of state)]]
 264   [[`os << x`] [`std::ostream&`] [writes a textual representation for the
 265                                   parameters and additional internal data of
 266                                   the distribution `x` to `os`.
 267                                   post: The `os.fmtflags` and fill character
 268                                   are unchanged.]
 269                                  [O(size of state)]]
 270   [[`is >> u`] [`std::istream&`] [restores the parameters and additional
 271                                   internal data of the distribution `u`.
 272                                   pre: `is` provides a textual representation
 273                                   that was previously written by `operator<<`
 274                                   post: The `is.fmtflags` are unchanged.]
 275                                  [O(size of state)]]
 276 ]
 277
 278 Additional requirements: The sequence of numbers produced by repeated
 279 invocations of `x(e)` does not change whether or not `os << x` is invoked
 280 between any of the invocations `x(e)`. If a textual representation is written
 281 using `os << x` and that representation is restored into the same or a
 282 different object `y` of the same type using `is >> y`, repeated invocations
 283 of `y(e)` produce the same sequence of random numbers as would repeated
 284 invocations of `x(e)`.
 285
 286 [endsect]