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 11Random 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 18The Boost Random Number Generator Library provides a framework for random 19number generators with well-defined properties so that the generators can be 20used in the demanding numerics and security domains. For a general 21introduction to random numbers in numerics, see 22 23[:"Numerical Recipes in C: The art of scientific computing", William H. Press, 24Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992, 25pp. 274-328] 26 27Depending on the requirements of the problem domain, different variations of 28random number generators are appropriate: 29 30* non-deterministic random number generator 31* pseudo-random number generator 32* quasi-random number generator 33 34All variations have some properties in common, the concepts (in the STL 35sense) is called __UniformRandomNumberGenerator. This 36concept will be defined in a subsequent section. 37 38The 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 48A uniform random number generator provides a 49sequence of random numbers uniformly distributed on a given range. The 50range can be compile-time fixed or available (only) after run-time construction 51of the object. 52 53The /tight lower bound/ of some (finite) set S is the (unique) member l in S, so 54that 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 56holds. 57 58In the following table, X denotes a number generator class returning objects 59of 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 78The member functions `min`, `max`, and `operator()` shall have amortized 79constant time complexity. 80 81[note For integer generators (i.e. integer `T`), the generated values `x` 82fulfill `min() <= x <= max()`, for non-integer generators (i.e. non-integer 83`T`), the generated values `x` fulfill `min() <= x < max()`. 84 85Rationale: The range description with min and max serves two purposes. First, 86it allows scaling of the values to some canonical range, such as [0..1). 87Second, it describes the significant bits of the values, which may be 88relevant for further processing. 89 90The range is a closed interval \[min,max\] for integers, because the underlying 91type may not be able to represent the half-open interval \[min,max+1). It is 92a half-open interval \[min, max) for non-integers, because this is much more 93practical 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 100Rationale: `operator()(long)` is not provided, because mapping the output of 101some 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 107A non-deterministic uniform random number generator is a 108__UniformRandomNumberGenerator that is based on some stochastic process. 109Thus, it provides a sequence of truly-random numbers. Examples for such 110processes are nuclear decay, noise of a Zehner diode, tunneling of quantum 111particles, rolling a die, drawing from an urn, and tossing a coin. Depending 112on the environment, inter-arrival times of network packets or keyboard events 113may be close approximations of stochastic processes. 114 115The class __random_device is a model for a non-deterministic random number 116generator. 117 118[note This type of random-number generator is useful for security 119applications, where it is important to prevent an outside attacker from 120guessing the numbers and thus obtaining your encryption or authentication key. 121Thus, models of this concept should be cautious not to leak any information, 122to the extent possible by the environment. For example, it might be advisable 123to explicitly clear any temporary storage as soon as it is no longer needed.] 124 125[endsect] 126 127[section Pseudo-Random Number Generator] 128 129A pseudo-random number generator is a __UniformRandomNumberGenerator which 130provides a deterministic sequence of pseudo-random numbers, based on some 131algorithm and internal state. 132[classref boost::random::linear_congruential_engine 133Linear congruential] and [classref boost::random::inversive_congruential_engine 134inversive congruential] generators are examples of such [prng pseudo-random 135number generators]. Often, these generators are very sensitive to their 136parameters. In order to prevent wrong implementations from being used, an 137external testsuite should check that the generated sequence and the validation 138value provided do indeed match. 139 140Donald E. Knuth gives an extensive overview on pseudo-random number generation 141in his book "The Art of Computer Programming, Vol. 2, 3rd edition, 142Addison-Wesley, 1997". The descriptions for the specific generators contain 143additional references. 144 145[note Because the state of a pseudo-random number generator is necessarily 146finite, the sequence of numbers returned by the generator will loop 147eventually.] 148 149In addition to the __UniformRandomNumberGenerator requirements, 150a pseudo-random number generator has some additional requirements. In the 151following 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 153of a type which models __SeedSeq, and `j` a value of 154type `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 169Classes which model a pseudo-random number generator shall also model 170__EqualityComparable, i.e. implement `operator==`. Two pseudo-random number 171generators are defined to be /equivalent/ if they both return an identical 172sequence of numbers starting from a given state. 173 174Classes 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 177to the given `ostream` so that `operator>>` can restore the state at a later 178time. The state shall be written in a platform-independent manner, but it is 179assumed that the `locales` used for writing and reading be the same. The 180pseudo-random number generator with the restored state and the original at 181the just-written state shall be equivalent. 182 183Classes which model a pseudo-random number generator should also model the 184__CopyConstructible and __Assignable concepts. However, note that the 185sequences of the original and the copy are strongly correlated (in fact, 186they are identical), which may make them unsuitable for some problem domains. 187Thus, copying pseudo-random number generators is discouraged; they should 188always be passed by (non-const) reference. 189 190The classes __rand48, __minstd_rand, and __mt19937 are models for a 191pseudo-random number generator. 192 193[note This type of random-number generator is useful for numerics, games and 194testing. The non-zero arguments constructor(s) and the `seed()` member 195function(s) allow for a user-provided state to be installed in the generator. 196This is useful for debugging Monte-Carlo algorithms and analyzing particular 197test scenarios. The __Streamable concept allows to save/restore the state of 198the generator, for example to re-run a test suite at a later time.] 199 200[endsect] 201 202[section Quasi-Random Number Generator] 203 204A quasi-random number generator is a __UniformRandomNumberGenerator which 205provides a deterministic sequence of quasi-random numbers, based on some 206algorithm and internal state. [classref boost::random::niederreiter_base2_engine 207Niederreiter base 2] generator is an example of such a [qrng quasi-random 208number generator]. The "quasi" modifier is used to denote more clearly that the 209values produced by such a generator are neither random nor pseudo-random, but 210they form a low discrepancy sequence. The intuitive idea is that a low discrepancy 211sequence is more evenly distributed than a pseudo random sequence would be. 212For example, if we generate a low discrepancy sequence of 2D points on a square, 213this square would be covered more evenly, and the number of points falling to any 214part of the square would be proportional to the number of points in the whole square. 215Such sequences share some properties of random variables and in certain applications 216such as the quasi-Monte Carlo method their lower discrepancy is an important advantage. 217 218[note The quasi-Monte Carlo method uses a low-discrepancy sequence such as the 219Niederreiter base 2 sequence, the Sobol sequence, or the Faure sequence among the others. 220The advantage of using low-discrepancy sequences is a probabilistically faster rate of 221convergence. Quasi-Monte Carlo has a rate of convergence O(log(N)[sup s]/N), 222whereas the rate of convergence for the Monte Carlo method, which uses a pseudo-random sequence, 223is O(N[sup -0.5]).] 224 225Harold Niederreiter gives an extensive overview on random number generation 226and quasi-Monte Carlo methods in his book "Random number generation and 227quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, 1992". 228 229In addition to the __UniformRandomNumberGenerator requirements, 230a quasi-random number generator has some additional requirements. In the 231following table, `X` denotes a quasi-random number generator class, `u` is a value of `X`, 232`v` is a const value of `X`, and `j` a value of type `unsigned long long`. 233 234[table QuasiRandomNumberGenerator requirements 235 [[expression] [return type] [pre/post-condition]] 236 [[`X(s)`] [-] [creates an `s`-dimensional generator with a default seed. Dimension `s` is an integer no less than 1.]] 237 [[`v.dimension()`] [std::size_t] [the dimension of quasi-random domain.]] 238 [[`u.seed(i)`] [`void`] [seeds the generator with the integer `i`.]] 239 [[`u.discard(j)`] [`void`] [Advances the generator by `j` steps as if by 240 `j` calls to `u()`.]] 241 ] 242 243[note The `operator()` returns a successive element of an `s`-dimensional (`s` = `v.dimension()`) vector 244at each invocation. When all elements are exhausted, `operator()` begins anew with the starting 245element of a subsequent `s`-dimensional vector.] 246 247Classes which model a quasi-random number generator shall also model 248__EqualityComparable, i.e. implement `operator==`. Two quasi-random number 249generators are defined to be /equivalent/ if they both return an identical 250sequence of numbers starting from a given state. 251 252Classes which model a quasi-random number generator shall also model the 253__Streamable concept, i.e. implement `operator<<` and `operator>>`. 254`operator<<` writes all current state of the quasi-random number generator 255to the given `ostream` so that `operator>>` can restore the state at a later 256time. The state shall be written in a platform-independent manner, but it is 257assumed that the `locales` used for writing and reading be the same. The 258quasi-random number generator with the restored state and the original at 259the just-written state shall be equivalent. 260 261Classes which model a quasi-random number generator should also model the 262__CopyConstructible and __Assignable concepts. However, note that the 263sequences of the original and the copy are strongly correlated (in fact, 264they are identical), which may make them unsuitable for some problem domains. 265Thus, copying quasi-random number generators is discouraged; they should 266always be passed by (non-const) reference. 267 268The classes __niederreiter_base2, __sobol, __faure are models for a quasi-random number generator. 269 270[endsect] 271 272[section Seed Sequence] 273 274A SeedSeq represents a sequence of values that can be used to 275set the initial state of a __PseudoRandomNumberGenerator. 276`i` and `j` are RandomAccessIterators whose `value_type` is 277an unsigned integer type with at least 32 bits. 278 279[table SeedSeq requirements 280 [[expression] [return type] [pre/post-condition] [complexity]] 281 [[`s.generate(i, j)`] [void] [stores 32-bit values to all the elements 282 in the iterator range defined by `i` and `j`] 283 [O(j - i)]] 284] 285 286The class __seed_seq and every __UniformRandomNumberGenerator 287provided by the library are models of __SeedSeq. 288 289[endsect] 290 291[section Random Distribution] 292 293A random distribution produces random numbers distributed according to some 294distribution, given uniformly distributed random values as input. In the 295following table, `X` denotes a random distribution class returning objects of 296type `T`, `u` is a value of `X`, `x` and `y` are (possibly const) values of 297`X`, `P` is the `param_type` of the distribution, `p` is a value of `P`, and 298`e` is an lvalue of an arbitrary type that meets the requirements of a 299__UniformRandomNumberGenerator, returning values of type `U`. 300 301[table Random distribution requirements (in addition to CopyConstructible, and Assignable) 302 [[expression] [return type] [pre/post-condition] [complexity]] 303 [[`X::result_type`] [`T`] [-] [compile-time]] 304 [[`X::param_type`] [`P`] [A type that stores the parameters of the 305 distribution, but not any of the state used to 306 generate random variates. `param_type` provides 307 the same set of constructors and accessors as 308 the distribution.] 309 [compile-time]] 310 [[`X(p)`] [`X`] [Initializes a distribution from its parameters] 311 [O(size of state)]] 312 [[`u.reset()`] [`void`] [subsequent uses of `u` do not depend on values 313 produced by any engine prior to invoking `reset`.] 314 [constant]] 315 [[`u(e)`] [`T`] [the sequence of numbers returned by successive invocations 316 with the same object `e` is randomly distributed with the 317 probability density function of the distribution] 318 [amortized constant number of invocations of `e`]] 319 [[`u(e, p)`] [`T`] [Equivalent to X(p)(e), but may use a different (and 320 presumably more efficient) implementation] 321 [amortized constant number of invocations of `e` + 322 O(size of state)]] 323 [[`x.param()`] [`P`] [Returns the parameters of the distribution] 324 [O(size of state)]] 325 [[`x.param(p)`] [void] [Sets the parameters of the distribution] 326 [O(size of state)]] 327 [[`x.min()`] [`T`] [returns the minimum value of the distribution] [constant]] 328 [[`x.max()`] [`T`] [returns the maximum value of the distribution] [constant]] 329 [[`x == y`] [`bool`] [Indicates whether the two distributions will produce 330 identical sequences of random variates if given 331 equal generators] 332 [O(size of state)]] 333 [[`x != y`] [`bool`] [`!(x == y)`] [O(size of state)]] 334 [[`os << x`] [`std::ostream&`] [writes a textual representation for the 335 parameters and additional internal data of 336 the distribution `x` to `os`. 337 post: The `os.fmtflags` and fill character 338 are unchanged.] 339 [O(size of state)]] 340 [[`is >> u`] [`std::istream&`] [restores the parameters and additional 341 internal data of the distribution `u`. 342 pre: `is` provides a textual representation 343 that was previously written by `operator<<` 344 post: The `is.fmtflags` are unchanged.] 345 [O(size of state)]] 346] 347 348Additional requirements: The sequence of numbers produced by repeated 349invocations of `x(e)` does not change whether or not `os << x` is invoked 350between any of the invocations `x(e)`. If a textual representation is written 351using `os << x` and that representation is restored into the same or a 352different object `y` of the same type using `is >> y`, repeated invocations 353of `y(e)` produce the same sequence of random numbers as would repeated 354invocations of `x(e)`. 355 356[endsect] 357