[29] | 1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
---|
| 2 | |
---|
| 3 | <html> |
---|
| 4 | <head> |
---|
| 5 | <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> |
---|
| 6 | |
---|
| 7 | <title>Boost Random Number Library Generators</title> |
---|
| 8 | </head> |
---|
| 9 | |
---|
| 10 | <body bgcolor="#FFFFFF" text="#000000"> |
---|
| 11 | <h1>Random Number Library Generators</h1> |
---|
| 12 | |
---|
| 13 | <ul> |
---|
| 14 | <li><a href="#intro">Introduction</a></li> |
---|
| 15 | |
---|
| 16 | <li><a href="#synopsis">Synopsis</a></li> |
---|
| 17 | |
---|
| 18 | <li><a href="#const_mod">Class template |
---|
| 19 | <code>random::const_mod</code></a></li> |
---|
| 20 | |
---|
| 21 | <li><a href="#linear_congruential">Class template |
---|
| 22 | <code>random::linear_congruential</code></a></li> |
---|
| 23 | |
---|
| 24 | <li><a href="#rand48">Class <code>rand48</code></a></li> |
---|
| 25 | |
---|
| 26 | <li><a href="#additive_combine">Class template |
---|
| 27 | <code>random::additive_combined</code></a></li> |
---|
| 28 | |
---|
| 29 | <li><a href="#shuffle_output">Class template |
---|
| 30 | <code>random::shuffle_output</code></a></li> |
---|
| 31 | |
---|
| 32 | <li><a href="#inversive_congruential">Class template |
---|
| 33 | <code>random::inversive_congruential</code></a></li> |
---|
| 34 | |
---|
| 35 | <li><a href="#mersenne_twister">Class template |
---|
| 36 | <code>random::mersenne_twister</code></a></li> |
---|
| 37 | |
---|
| 38 | <li><a href="#lagged_fibonacci">Class template |
---|
| 39 | <code>random::lagged_fibonacci</code></a></li> |
---|
| 40 | |
---|
| 41 | <li><a href="#performance">Performance</a></li> |
---|
| 42 | </ul> |
---|
| 43 | |
---|
| 44 | <h2><a name="intro" id="intro">Introduction</a></h2> |
---|
| 45 | |
---|
| 46 | <p>This library provides several pseudo-random number generators. The |
---|
| 47 | quality of a pseudo-random number generator crucially depends on both the |
---|
| 48 | algorithm and its parameters. This library implements the algorithms as |
---|
| 49 | class templates with template value parameters, hidden in namespace |
---|
| 50 | <code>boost::random</code>. Any particular choice of parameters is |
---|
| 51 | represented as the appropriately specializing <code>typedef</code> in |
---|
| 52 | namespace <code>boost</code>.</p> |
---|
| 53 | |
---|
| 54 | <p>Pseudo-random number generators should not be constructed (initialized) |
---|
| 55 | frequently during program execution, for two reasons. First, initialization |
---|
| 56 | requires full initialization of the internal state of the generator. Thus, |
---|
| 57 | generators with a lot of internal state (see below) are costly to |
---|
| 58 | initialize. Second, initialization always requires some value used as a |
---|
| 59 | "seed" for the generated sequence. It is usually difficult to obtain |
---|
| 60 | several good seed values. For example, one method to obtain a seed is to |
---|
| 61 | determine the current time at the highest resolution available, e.g. |
---|
| 62 | microseconds or nanoseconds. When the pseudo-random number generator is |
---|
| 63 | initialized again with the then-current time as the seed, it is likely that |
---|
| 64 | this is at a near-constant (non-random) distance from the time given as the |
---|
| 65 | seed for first initialization. The distance could even be zero if the |
---|
| 66 | resolution of the clock is low, thus the generator re-iterates the same |
---|
| 67 | sequence of random numbers. For some applications, this is |
---|
| 68 | inappropriate.</p> |
---|
| 69 | |
---|
| 70 | <p>Note that all pseudo-random number generators described below are |
---|
| 71 | CopyConstructible and Assignable. Copying or assigning a generator will |
---|
| 72 | copy all its internal state, so the original and the copy will generate the |
---|
| 73 | identical sequence of random numbers. Often, such behavior is not wanted. |
---|
| 74 | In particular, beware of the algorithms from the standard library such as |
---|
| 75 | std::generate. They take a functor argument by value, thereby invoking the |
---|
| 76 | copy constructor when called.</p> |
---|
| 77 | |
---|
| 78 | <p>The following table gives an overview of some characteristics of the |
---|
| 79 | generators. The cycle length is a rough estimate of the quality of the |
---|
| 80 | generator; the approximate relative speed is a performance measure, higher |
---|
| 81 | numbers mean faster random number generation.</p> |
---|
| 82 | |
---|
| 83 | <table border="1" summary=""> |
---|
| 84 | <tr> |
---|
| 85 | <th>generator</th> |
---|
| 86 | |
---|
| 87 | <th>length of cycle</th> |
---|
| 88 | |
---|
| 89 | <th>approx. memory requirements</th> |
---|
| 90 | |
---|
| 91 | <th>approx. relative speed</th> |
---|
| 92 | |
---|
| 93 | <th>comment</th> |
---|
| 94 | </tr> |
---|
| 95 | |
---|
| 96 | <tr> |
---|
| 97 | <td><a href="#minstd_rand"><code>minstd_rand</code></a></td> |
---|
| 98 | |
---|
| 99 | <td>2<sup>31</sup>-2</td> |
---|
| 100 | |
---|
| 101 | <td><code>sizeof(int32_t)</code></td> |
---|
| 102 | |
---|
| 103 | <td>40</td> |
---|
| 104 | |
---|
| 105 | <td>-</td> |
---|
| 106 | </tr> |
---|
| 107 | |
---|
| 108 | <tr> |
---|
| 109 | <td><a href="#rand48"><code>rand48</code></a></td> |
---|
| 110 | |
---|
| 111 | <td>2<sup>48</sup>-1</td> |
---|
| 112 | |
---|
| 113 | <td><code>sizeof(uint64_t)</code></td> |
---|
| 114 | |
---|
| 115 | <td>80</td> |
---|
| 116 | |
---|
| 117 | <td>-</td> |
---|
| 118 | </tr> |
---|
| 119 | |
---|
| 120 | <tr> |
---|
| 121 | <td><code>lrand48</code> (C library)</td> |
---|
| 122 | |
---|
| 123 | <td>2<sup>48</sup>-1</td> |
---|
| 124 | |
---|
| 125 | <td>-</td> |
---|
| 126 | |
---|
| 127 | <td>20</td> |
---|
| 128 | |
---|
| 129 | <td>global state</td> |
---|
| 130 | </tr> |
---|
| 131 | |
---|
| 132 | <tr> |
---|
| 133 | <td><a href="#ecuyer1988"><code>ecuyer1988</code></a></td> |
---|
| 134 | |
---|
| 135 | <td>approx. 2<sup>61</sup></td> |
---|
| 136 | |
---|
| 137 | <td><code>2*sizeof(int32_t)</code></td> |
---|
| 138 | |
---|
| 139 | <td>20</td> |
---|
| 140 | |
---|
| 141 | <td>-</td> |
---|
| 142 | </tr> |
---|
| 143 | |
---|
| 144 | <tr> |
---|
| 145 | <td><code><a href="#kreutzer1986">kreutzer1986</a></code></td> |
---|
| 146 | |
---|
| 147 | <td>?</td> |
---|
| 148 | |
---|
| 149 | <td><code>1368*sizeof(uint32_t)</code></td> |
---|
| 150 | |
---|
| 151 | <td>60</td> |
---|
| 152 | |
---|
| 153 | <td>-</td> |
---|
| 154 | </tr> |
---|
| 155 | |
---|
| 156 | <tr> |
---|
| 157 | <td><code><a href="#hellekalek1995">hellekalek1995</a></code></td> |
---|
| 158 | |
---|
| 159 | <td>2<sup>31</sup>-1</td> |
---|
| 160 | |
---|
| 161 | <td><code>sizeof(int32_t)</code></td> |
---|
| 162 | |
---|
| 163 | <td>3</td> |
---|
| 164 | |
---|
| 165 | <td>good uniform distribution in several dimensions</td> |
---|
| 166 | </tr> |
---|
| 167 | |
---|
| 168 | <tr> |
---|
| 169 | <td><code><a href="#mt11213b">mt11213b</a></code></td> |
---|
| 170 | |
---|
| 171 | <td>2<sup>11213</sup>-1</td> |
---|
| 172 | |
---|
| 173 | <td><code>352*sizeof(uint32_t)</code></td> |
---|
| 174 | |
---|
| 175 | <td>100</td> |
---|
| 176 | |
---|
| 177 | <td>good uniform distribution in up to 350 dimensions</td> |
---|
| 178 | </tr> |
---|
| 179 | |
---|
| 180 | <tr> |
---|
| 181 | <td><code><a href="#mt19937">mt19937</a></code></td> |
---|
| 182 | |
---|
| 183 | <td>2<sup>19937</sup>-1</td> |
---|
| 184 | |
---|
| 185 | <td><code>625*sizeof(uint32_t)</code></td> |
---|
| 186 | |
---|
| 187 | <td>100</td> |
---|
| 188 | |
---|
| 189 | <td>good uniform distribution in up to 623 dimensions</td> |
---|
| 190 | </tr> |
---|
| 191 | |
---|
| 192 | <tr> |
---|
| 193 | <td><code><a href= |
---|
| 194 | "#lagged_fibonacci_spec">lagged_fibonacci607</a></code></td> |
---|
| 195 | |
---|
| 196 | <td>approx. 2<sup>32000</sup></td> |
---|
| 197 | |
---|
| 198 | <td><code>607*sizeof(double)</code></td> |
---|
| 199 | |
---|
| 200 | <td>150</td> |
---|
| 201 | |
---|
| 202 | <td>-</td> |
---|
| 203 | </tr> |
---|
| 204 | |
---|
| 205 | <tr> |
---|
| 206 | <td><code><a href= |
---|
| 207 | "#lagged_fibonacci_spec">lagged_fibonacci1279</a></code></td> |
---|
| 208 | |
---|
| 209 | <td>approx. 2<sup>67000</sup></td> |
---|
| 210 | |
---|
| 211 | <td><code>1279*sizeof(double)</code></td> |
---|
| 212 | |
---|
| 213 | <td>150</td> |
---|
| 214 | |
---|
| 215 | <td>-</td> |
---|
| 216 | </tr> |
---|
| 217 | |
---|
| 218 | <tr> |
---|
| 219 | <td><code><a href= |
---|
| 220 | "#lagged_fibonacci_spec">lagged_fibonacci2281</a></code></td> |
---|
| 221 | |
---|
| 222 | <td>approx. 2<sup>120000</sup></td> |
---|
| 223 | |
---|
| 224 | <td><code>2281*sizeof(double)</code></td> |
---|
| 225 | |
---|
| 226 | <td>150</td> |
---|
| 227 | |
---|
| 228 | <td>-</td> |
---|
| 229 | </tr> |
---|
| 230 | |
---|
| 231 | <tr> |
---|
| 232 | <td><code><a href= |
---|
| 233 | "#lagged_fibonacci_spec">lagged_fibonacci3217</a></code></td> |
---|
| 234 | |
---|
| 235 | <td>approx. 2<sup>170000</sup></td> |
---|
| 236 | |
---|
| 237 | <td><code>3217*sizeof(double)</code></td> |
---|
| 238 | |
---|
| 239 | <td>150</td> |
---|
| 240 | |
---|
| 241 | <td>-</td> |
---|
| 242 | </tr> |
---|
| 243 | |
---|
| 244 | <tr> |
---|
| 245 | <td><code><a href= |
---|
| 246 | "#lagged_fibonacci_spec">lagged_fibonacci4423</a></code></td> |
---|
| 247 | |
---|
| 248 | <td>approx. 2<sup>230000</sup></td> |
---|
| 249 | |
---|
| 250 | <td><code>4423*sizeof(double)</code></td> |
---|
| 251 | |
---|
| 252 | <td>150</td> |
---|
| 253 | |
---|
| 254 | <td>-</td> |
---|
| 255 | </tr> |
---|
| 256 | |
---|
| 257 | <tr> |
---|
| 258 | <td><code><a href= |
---|
| 259 | "#lagged_fibonacci_spec">lagged_fibonacci9689</a></code></td> |
---|
| 260 | |
---|
| 261 | <td>approx. 2<sup>510000</sup></td> |
---|
| 262 | |
---|
| 263 | <td><code>9689*sizeof(double)</code></td> |
---|
| 264 | |
---|
| 265 | <td>150</td> |
---|
| 266 | |
---|
| 267 | <td>-</td> |
---|
| 268 | </tr> |
---|
| 269 | |
---|
| 270 | <tr> |
---|
| 271 | <td><code><a href= |
---|
| 272 | "#lagged_fibonacci_spec">lagged_fibonacci19937</a></code></td> |
---|
| 273 | |
---|
| 274 | <td>approx. 2<sup>1050000</sup></td> |
---|
| 275 | |
---|
| 276 | <td><code>19937*sizeof(double)</code></td> |
---|
| 277 | |
---|
| 278 | <td>150</td> |
---|
| 279 | |
---|
| 280 | <td>-</td> |
---|
| 281 | </tr> |
---|
| 282 | |
---|
| 283 | <tr> |
---|
| 284 | <td><code><a href= |
---|
| 285 | "#lagged_fibonacci_spec">lagged_fibonacci23209</a></code></td> |
---|
| 286 | |
---|
| 287 | <td>approx. 2<sup>1200000</sup></td> |
---|
| 288 | |
---|
| 289 | <td><code>23209*sizeof(double)</code></td> |
---|
| 290 | |
---|
| 291 | <td>140</td> |
---|
| 292 | |
---|
| 293 | <td>-</td> |
---|
| 294 | </tr> |
---|
| 295 | |
---|
| 296 | <tr> |
---|
| 297 | <td><code><a href= |
---|
| 298 | "#lagged_fibonacci_spec">lagged_fibonacci44497</a></code></td> |
---|
| 299 | |
---|
| 300 | <td>approx. 2<sup>2300000</sup></td> |
---|
| 301 | |
---|
| 302 | <td><code>44497*sizeof(double)</code></td> |
---|
| 303 | |
---|
| 304 | <td>60</td> |
---|
| 305 | |
---|
| 306 | <td>-</td> |
---|
| 307 | </tr> |
---|
| 308 | </table> |
---|
| 309 | |
---|
| 310 | <p>As observable from the table, there is generally a |
---|
| 311 | quality/performance/memory trade-off to be decided upon when choosing a |
---|
| 312 | random-number generator. The multitude of generators provided in this |
---|
| 313 | library allows the application programmer to optimize the trade-off with |
---|
| 314 | regard to his application domain. Additionally, employing several |
---|
| 315 | fundamentally different random number generators for a given application of |
---|
| 316 | Monte Carlo simulation will improve the confidence in the results.</p> |
---|
| 317 | |
---|
| 318 | <p>If the names of the generators don't ring any bell and you have no idea |
---|
| 319 | which generator to use, it is reasonable to employ <code>mt19937</code> for |
---|
| 320 | a start: It is fast and has acceptable quality.</p> |
---|
| 321 | |
---|
| 322 | <p><em>Note:</em> These random number generators are not intended for use |
---|
| 323 | in applications where non-deterministic random numbers are required. See |
---|
| 324 | <a href="nondet_random.html">nondet_random.html</a> for a choice of |
---|
| 325 | (hopefully) non-deterministic random number generators.</p> |
---|
| 326 | |
---|
| 327 | <p>In this description, I have refrained from documenting those members in |
---|
| 328 | detail which are already defined in the <a href= |
---|
| 329 | "random-concepts.html">concept documentation</a>.</p> |
---|
| 330 | |
---|
| 331 | <h2><a name="synopsis" id="synopsis">Synopsis of the generators</a> |
---|
| 332 | available from header <code><boost/random.hpp></code></h2> |
---|
| 333 | <pre> |
---|
| 334 | namespace boost { |
---|
| 335 | namespace random { |
---|
| 336 | template<class IntType, IntType m> |
---|
| 337 | class const_mod; |
---|
| 338 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
| 339 | class linear_congruential; |
---|
| 340 | } |
---|
| 341 | class rand48; |
---|
| 342 | typedef random::linear_congruential< /* ... */ > minstd_rand0; |
---|
| 343 | typedef random::linear_congruential< /* ... */ > minstd_rand; |
---|
| 344 | |
---|
| 345 | namespace random { |
---|
| 346 | template<class DataType, int w, int n, int m, int r, DataType a, int u, |
---|
| 347 | int s, DataType b, int t, DataType c, int l, IntType val> |
---|
| 348 | class mersenne_twister; |
---|
| 349 | } |
---|
| 350 | typedef random::mersenne_twister< /* ... */ > mt11213b; |
---|
| 351 | typedef random::mersenne_twister< /* ... */ > mt19937; |
---|
| 352 | |
---|
| 353 | namespace random { |
---|
| 354 | template<class FloatType, unsigned int p, unsigned int q> |
---|
| 355 | class lagged_fibonacci; |
---|
| 356 | } |
---|
| 357 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci607; |
---|
| 358 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci1279; |
---|
| 359 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci2281; |
---|
| 360 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci3217; |
---|
| 361 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci4423; |
---|
| 362 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci9689; |
---|
| 363 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci19937; |
---|
| 364 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci23209; |
---|
| 365 | typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci44497; |
---|
| 366 | } // namespace boost |
---|
| 367 | </pre> |
---|
| 368 | |
---|
| 369 | <h2><a name="const_mod" id="const_mod">Class template |
---|
| 370 | <code>random::const_mod</code></a></h2> |
---|
| 371 | |
---|
| 372 | <h3>Synopsis</h3> |
---|
| 373 | <pre> |
---|
| 374 | template<class IntType, IntType m> |
---|
| 375 | class random::const_mod |
---|
| 376 | { |
---|
| 377 | public: |
---|
| 378 | template<IntType c> |
---|
| 379 | static IntType add(IntType x); |
---|
| 380 | |
---|
| 381 | template<IntType a> |
---|
| 382 | static IntType mult(IntType x); |
---|
| 383 | |
---|
| 384 | template<IntType a, IntType c> |
---|
| 385 | static IntType mult_add(IntType x); |
---|
| 386 | |
---|
| 387 | static IntType invert(IntType x); |
---|
| 388 | private: |
---|
| 389 | const_mod(); // don't instantiate |
---|
| 390 | }; |
---|
| 391 | </pre> |
---|
| 392 | |
---|
| 393 | <h3>Description</h3> |
---|
| 394 | |
---|
| 395 | <p>Class template <code>const_mod</code> provides functions performing |
---|
| 396 | modular arithmetic, carefully avoiding overflows. All member functions are |
---|
| 397 | static; there shall be no objects of type |
---|
| 398 | <code>const_mod<></code>.</p> |
---|
| 399 | |
---|
| 400 | <p>The template parameter <code>IntType</code> shall denote an integral |
---|
| 401 | type, <code>m</code> is the modulus.</p> |
---|
| 402 | |
---|
| 403 | <p><em>Note:</em> For modulo multiplications with large m, a trick allows |
---|
| 404 | fast computation under certain conditions, see</p> |
---|
| 405 | |
---|
| 406 | <blockquote> |
---|
| 407 | "A more portable FORTRAN random number generator", Linus Schrage, ACM |
---|
| 408 | Transactions on Mathematical Software, Vol. 5, No. 2, June 1979, pp. |
---|
| 409 | 132-138 |
---|
| 410 | </blockquote> |
---|
| 411 | |
---|
| 412 | <h3>Member functions</h3> |
---|
| 413 | <pre> |
---|
| 414 | template<IntType c> static IntType add(IntType x) |
---|
| 415 | </pre> |
---|
| 416 | |
---|
| 417 | <p><strong>Returns:</strong> (x+c) mod m</p> |
---|
| 418 | <pre> |
---|
| 419 | template<IntType a> static IntType mult(IntType x) |
---|
| 420 | </pre> |
---|
| 421 | |
---|
| 422 | <p><strong>Returns:</strong> (a*x) mod m</p> |
---|
| 423 | <pre> |
---|
| 424 | template<IntType a, IntType c> static IntType |
---|
| 425 | mult_add(IntType x) |
---|
| 426 | </pre> |
---|
| 427 | |
---|
| 428 | <p><strong>Returns:</strong> (a*x+c) mod m</p> |
---|
| 429 | <pre> |
---|
| 430 | static IntType invert(IntType x) |
---|
| 431 | </pre> |
---|
| 432 | |
---|
| 433 | <p><strong>Returns:</strong> i so that (a*i) mod m == 1<br> |
---|
| 434 | <strong>Precondition:</strong> m is prime</p> |
---|
| 435 | |
---|
| 436 | <h2><a name="linear_congruential" id="linear_congruential">Class template |
---|
| 437 | <code>random::linear_congruential</code></a></h2> |
---|
| 438 | |
---|
| 439 | <h3>Synopsis</h3> |
---|
| 440 | <pre> |
---|
| 441 | #include <<a href= |
---|
| 442 | "../../boost/random/linear_congruential.hpp">boost/random/linear_congruential.hpp</a>> |
---|
| 443 | |
---|
| 444 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
| 445 | class linear_congruential |
---|
| 446 | { |
---|
| 447 | public: |
---|
| 448 | typedef IntType result_type; |
---|
| 449 | static const IntType multiplier = a; |
---|
| 450 | static const IntType increment = c; |
---|
| 451 | static const IntType modulus = m; |
---|
| 452 | static const bool has_fixed_range = true; |
---|
| 453 | static const result_type min_value; |
---|
| 454 | static const result_type max_value; |
---|
| 455 | explicit linear_congruential_fixed(IntType x0 = 1); |
---|
| 456 | // compiler-generated copy constructor and assignment operator are fine |
---|
| 457 | void seed(IntType x0); |
---|
| 458 | IntType operator()(); |
---|
| 459 | }; |
---|
| 460 | |
---|
| 461 | typedef random::linear_congruential<long, 16807L, 0, 2147483647L, |
---|
| 462 | 1043618065L> minstd_rand0; |
---|
| 463 | typedef random::linear_congruential<long, 48271L, 0, 2147483647L, |
---|
| 464 | 399268537L> minstd_rand; |
---|
| 465 | </pre> |
---|
| 466 | |
---|
| 467 | <h3>Description</h3> |
---|
| 468 | |
---|
| 469 | <p>Instantiations of class template <code>linear_congruential</code> model |
---|
| 470 | a <a href="random-concepts.html#pseudo-rng">pseudo-random number |
---|
| 471 | generator</a>. Linear congruential pseudo-random number generators are |
---|
| 472 | described in:</p> |
---|
| 473 | |
---|
| 474 | <blockquote> |
---|
| 475 | "Mathematical methods in large-scale computing units", D. H. Lehmer, |
---|
| 476 | Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, Harvard |
---|
| 477 | University Press, 1951, pp. 141-146 |
---|
| 478 | </blockquote>Let x(n) denote the sequence of numbers returned by some |
---|
| 479 | pseudo-random number generator. Then for the linear congruential generator, |
---|
| 480 | x(n+1) := (a * x(n) + c) mod m. Parameters for the generator are x(0), a, |
---|
| 481 | c, m. The template parameter <code>IntType</code> shall denote an integral |
---|
| 482 | type. It must be large enough to hold values a, c, and m. The template |
---|
| 483 | parameters a and c must be smaller than m. |
---|
| 484 | |
---|
| 485 | <p><em>Note:</em> The quality of the generator crucially depends on the |
---|
| 486 | choice of the parameters. User code should use one of the sensibly |
---|
| 487 | parameterized generators such as <code>minstd_rand</code> instead.<br> |
---|
| 488 | For each choice of the parameters a, c, m, some distinct type is defined, |
---|
| 489 | so that the <code>static</code> members do not interfere with regard to the |
---|
| 490 | one definition rule.</p> |
---|
| 491 | |
---|
| 492 | <h3>Members</h3> |
---|
| 493 | <pre> |
---|
| 494 | explicit linear_congruential(IntType x0 = 1) |
---|
| 495 | </pre> |
---|
| 496 | |
---|
| 497 | <p><strong>Effects:</strong> Constructs a <code>linear_congruential</code> |
---|
| 498 | generator with x(0) := <code>x0</code>.</p> |
---|
| 499 | <pre> |
---|
| 500 | void seed(IntType x0) |
---|
| 501 | </pre> |
---|
| 502 | |
---|
| 503 | <p><strong>Effects:</strong> Changes the current value x(n) of the |
---|
| 504 | generator to <code>x0</code>.</p> |
---|
| 505 | |
---|
| 506 | <h3><a name="minstd_rand" id="minstd_rand">Specializations</a></h3> |
---|
| 507 | |
---|
| 508 | <p>The specialization <code>minstd_rand0</code> was originally suggested |
---|
| 509 | in</p> |
---|
| 510 | |
---|
| 511 | <blockquote> |
---|
| 512 | A pseudo-random number generator for the System/360, P.A. Lewis, A.S. |
---|
| 513 | Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, 1969, pp. |
---|
| 514 | 136-146 |
---|
| 515 | </blockquote>It is examined more closely together with |
---|
| 516 | <code>minstd_rand</code> in |
---|
| 517 | |
---|
| 518 | <blockquote> |
---|
| 519 | "Random Number Generators: Good ones are hard to find", Stephen K. Park |
---|
| 520 | and Keith W. Miller, Communications of the ACM, Vol. 31, No. 10, October |
---|
| 521 | 1988, pp. 1192-1201 |
---|
| 522 | </blockquote> |
---|
| 523 | |
---|
| 524 | <h2><a name="rand48" id="rand48">Class <code>rand48</code></a></h2> |
---|
| 525 | |
---|
| 526 | <h3>Synopsis</h3> |
---|
| 527 | <pre> |
---|
| 528 | #include <<a href= |
---|
| 529 | "../../boost/random/linear_congruential.hpp">boost/random/linear_congruential.hpp</a>> |
---|
| 530 | |
---|
| 531 | class rand48 |
---|
| 532 | { |
---|
| 533 | public: |
---|
| 534 | typedef int32_t result_type; |
---|
| 535 | static const bool has_fixed_range = true; |
---|
| 536 | static const int32_t min_value = 0; |
---|
| 537 | static const int32_t max_value = 0x7fffffff; |
---|
| 538 | |
---|
| 539 | explicit rand48(int32_t x0 = 1); |
---|
| 540 | explicit rand48(uint64_t x0); |
---|
| 541 | // compiler-generated copy ctor and assignment operator are fine |
---|
| 542 | void seed(int32_t x0); |
---|
| 543 | void seed(uint64_t x0); |
---|
| 544 | int32_t operator()(); |
---|
| 545 | }; |
---|
| 546 | </pre> |
---|
| 547 | |
---|
| 548 | <h3>Description</h3> |
---|
| 549 | |
---|
| 550 | <p>Class <code>rand48</code> models a <a href= |
---|
| 551 | "random-concepts.html#pseudo-rng">pseudo-random number generator</a>. It |
---|
| 552 | uses the linear congruential algorithm with the parameters a = 0x5DEECE66D, |
---|
| 553 | c = 0xB, m = 2**48. It delivers identical results to the |
---|
| 554 | <code>lrand48()</code> function available on some systems (assuming |
---|
| 555 | <code>lcong48</code> has not been called).</p> |
---|
| 556 | |
---|
| 557 | <p>It is only available on systems where <code>uint64_t</code> is provided |
---|
| 558 | as an integral type, so that for example static in-class constants and/or |
---|
| 559 | enum definitions with large <code>uint64_t</code> numbers work.</p> |
---|
| 560 | |
---|
| 561 | <h3>Constructors</h3> |
---|
| 562 | <pre> |
---|
| 563 | rand48(int32_t x0) |
---|
| 564 | </pre> |
---|
| 565 | |
---|
| 566 | <p><strong>Effects:</strong> Constructs a <code>rand48</code> generator |
---|
| 567 | with x(0) := (<code>x0</code> << 16) | 0x330e.</p> |
---|
| 568 | <pre> |
---|
| 569 | rand48(uint64_t x0) |
---|
| 570 | </pre> |
---|
| 571 | |
---|
| 572 | <p><strong>Effects:</strong> Constructs a <code>rand48</code> generator |
---|
| 573 | with x(0) := <code>x0</code>.</p> |
---|
| 574 | |
---|
| 575 | <h3>Seeding</h3> |
---|
| 576 | <pre> |
---|
| 577 | void seed(int32_t x0) |
---|
| 578 | </pre> |
---|
| 579 | |
---|
| 580 | <p><strong>Effects:</strong> Changes the current value x(n) of the |
---|
| 581 | generator to (<code>x0</code> << 16) | 0x330e.</p> |
---|
| 582 | <pre> |
---|
| 583 | void seed(uint64_t x0) |
---|
| 584 | </pre> |
---|
| 585 | |
---|
| 586 | <p><strong>Effects:</strong> Changes the current value x(n) of the |
---|
| 587 | generator to <code>x0</code>.</p> |
---|
| 588 | |
---|
| 589 | <h2><a name="additive_combine" id="additive_combine">Class template |
---|
| 590 | <code>random::additive_combine</code></a></h2> |
---|
| 591 | |
---|
| 592 | <h3>Synopsis</h3> |
---|
| 593 | <pre> |
---|
| 594 | #include <<a href= |
---|
| 595 | "../../boost/random/additive_combine.hpp">boost/random/additive_combine.hpp</a>> |
---|
| 596 | |
---|
| 597 | template<class MLCG1, class MLCG2, typename MLCG1::result_type val> |
---|
| 598 | class random::additive_combine |
---|
| 599 | { |
---|
| 600 | public: |
---|
| 601 | typedef MLCG1 first_base; |
---|
| 602 | typedef MLCG2 second_base; |
---|
| 603 | typedef typename MLCG1::result_type result_type; |
---|
| 604 | static const bool has_fixed_range = true; |
---|
| 605 | static const result_type min_value = 1; |
---|
| 606 | static const result_type max_value = MLCG1::max_value-1; |
---|
| 607 | additive_combine(); |
---|
| 608 | additive_combine(typename MLCG1::result_type seed1, |
---|
| 609 | typename MLCG2::result_type seed2); |
---|
| 610 | result_type operator()(); |
---|
| 611 | bool validation(result_type x) const; |
---|
| 612 | }; |
---|
| 613 | |
---|
| 614 | typedef random::additive_combine< |
---|
| 615 | random::linear_congruential<int32_t, 40014, 0, 2147483563, 0>, |
---|
| 616 | random::linear_congruential<int32_t, 40692, 0, 2147483399, 0>, |
---|
| 617 | /* unknown */ 0> ecuyer1988; |
---|
| 618 | |
---|
| 619 | </pre> |
---|
| 620 | |
---|
| 621 | <h3>Description</h3> |
---|
| 622 | |
---|
| 623 | <p>Instatiations of class template <code>additive_combine</code> model a |
---|
| 624 | <a href="random-concepts.html#pseudo-rng">pseudo-random number |
---|
| 625 | generator</a>. It combines two multiplicative linear congruential number |
---|
| 626 | generators, i.e. those with c = 0. It is described in</p> |
---|
| 627 | |
---|
| 628 | <blockquote> |
---|
| 629 | "Efficient and Portable Combined Random Number Generators", Pierre |
---|
| 630 | L'Ecuyer, Communications of the ACM, Vol. 31, No. 6, June 1988, pp. |
---|
| 631 | 742-749, 774 |
---|
| 632 | </blockquote>The template parameters <code>MLCG1</code> and |
---|
| 633 | <code>MLCG2</code> shall denote two different linear congruential number |
---|
| 634 | generators, each with c = 0. Each invocation returns a random number X(n) |
---|
| 635 | := (MLCG1(n) - MLCG2(n)) mod (m1 - 1), where m1 denotes the modulus of |
---|
| 636 | <code>MLCG1</code>. |
---|
| 637 | |
---|
| 638 | <p>The template parameter <code>val</code> is the validation value checked |
---|
| 639 | by <code>validation</code>.</p> |
---|
| 640 | |
---|
| 641 | <h3>Members</h3> |
---|
| 642 | <pre> |
---|
| 643 | additive_combine() |
---|
| 644 | </pre> |
---|
| 645 | |
---|
| 646 | <p><strong>Effects:</strong> Constructs an <code>additive_combine</code> |
---|
| 647 | generator using the default constructors of the two base generators.</p> |
---|
| 648 | <pre> |
---|
| 649 | additive_combine(typename MLCG1::result_type seed1, |
---|
| 650 | typename MLCG2::result_type seed2) |
---|
| 651 | </pre> |
---|
| 652 | |
---|
| 653 | <p><strong>Effects:</strong> Constructs an <code>additive_combine</code> |
---|
| 654 | generator, using <code>seed1</code> and <code>seed2</code> as the |
---|
| 655 | constructor argument to the first and second base generator, |
---|
| 656 | respectively.</p> |
---|
| 657 | |
---|
| 658 | <h3><a name="ecuyer1988" id="ecuyer1988">Specialization</a></h3> |
---|
| 659 | |
---|
| 660 | <p>The specialization <code>ecuyer1988</code> was suggested in the above |
---|
| 661 | paper.</p> |
---|
| 662 | |
---|
| 663 | <h2><a name="shuffle_output" id="shuffle_output">Class template |
---|
| 664 | <code>random::shuffle_output</code></a></h2> |
---|
| 665 | |
---|
| 666 | <h3>Synopsis</h3> |
---|
| 667 | <pre> |
---|
| 668 | #include <<a href= |
---|
| 669 | "../../boost/random/shuffle_output.hpp">boost/random/shuffle_output.hpp</a>> |
---|
| 670 | |
---|
| 671 | template<class UniformRandomNumberGenerator, int k, |
---|
| 672 | typename UniformRandomNumberGenerator::result_type val = 0> |
---|
| 673 | class random::shuffle_output |
---|
| 674 | { |
---|
| 675 | public: |
---|
| 676 | typedef UniformRandomNumberGenerator base_type; |
---|
| 677 | typedef typename base_type::result_type result_type; |
---|
| 678 | static const bool has_fixed_range = false; |
---|
| 679 | |
---|
| 680 | shuffle_output(); |
---|
| 681 | template<class T> explicit shuffle_output(T seed); |
---|
| 682 | explicit shuffle_output(const base_type & rng); |
---|
| 683 | template<class T> void seed(T s); |
---|
| 684 | |
---|
| 685 | result_type operator()(); |
---|
| 686 | result_type min() const; |
---|
| 687 | result_type max() const; |
---|
| 688 | bool validation(result_type) const; |
---|
| 689 | }; |
---|
| 690 | </pre> |
---|
| 691 | |
---|
| 692 | <h3>Description</h3> |
---|
| 693 | |
---|
| 694 | <p>Instatiations of class template <code>shuffle_output</code> model a |
---|
| 695 | <a href="random-concepts.html#pseudo-rng">pseudo-random number |
---|
| 696 | generator</a>. It mixes the output of some (usually linear congruential) |
---|
| 697 | uniform random number generator to get better statistical properties. |
---|
| 698 | According to Donald E. Knuth, "The Art of Computer Programming, Vol. 2", |
---|
| 699 | the algorithm is described in</p> |
---|
| 700 | |
---|
| 701 | <blockquote> |
---|
| 702 | "Improving a poor random number generator", Carter Bays and S.D. Durham, |
---|
| 703 | ACM Transactions on Mathematical Software, Vol. 2, 1979, pp. 59-64. |
---|
| 704 | </blockquote>The output of the base generator is buffered in an array of |
---|
| 705 | length k. Every output X(n) has a second role: It gives an index into the |
---|
| 706 | array where X(n+1) will be retrieved. Used array elements are replaced with |
---|
| 707 | fresh output from the base generator. |
---|
| 708 | |
---|
| 709 | <p>Template parameters are the base generator and the array length k, which |
---|
| 710 | should be around 100. The template parameter <code>val</code> is the |
---|
| 711 | validation value checked by <code>validation</code>.</p> |
---|
| 712 | |
---|
| 713 | <h3>Members</h3> |
---|
| 714 | <pre> |
---|
| 715 | shuffle_output() |
---|
| 716 | </pre> |
---|
| 717 | |
---|
| 718 | <p><strong>Effects:</strong> Constructs a <code>shuffle_output</code> |
---|
| 719 | generator by invoking the default constructor of the base generator.</p> |
---|
| 720 | |
---|
| 721 | <p><strong>Complexity:</strong> Exactly k+1 invocations of the base |
---|
| 722 | generator.</p> |
---|
| 723 | <pre> |
---|
| 724 | template<class T> explicit shuffle_output(T seed) |
---|
| 725 | </pre> |
---|
| 726 | |
---|
| 727 | <p><strong>Effects:</strong> Constructs a <code>shuffle_output</code> |
---|
| 728 | generator by invoking the one-argument constructor of the base generator |
---|
| 729 | with the parameter <code>seed</code>.</p> |
---|
| 730 | |
---|
| 731 | <p><strong>Complexity:</strong> Exactly k+1 invocations of the base |
---|
| 732 | generator.</p> |
---|
| 733 | <pre> |
---|
| 734 | explicit shuffle_output(const base_type & rng) |
---|
| 735 | </pre> |
---|
| 736 | |
---|
| 737 | <p><strong>Precondition:</strong> The template argument |
---|
| 738 | <code>UniformRandomNumberGenerator</code> shall denote a CopyConstructible |
---|
| 739 | type.</p> |
---|
| 740 | |
---|
| 741 | <p><strong>Effects:</strong> Constructs a <code>shuffle_output</code> |
---|
| 742 | generator by using a copy of the provided generator.</p> |
---|
| 743 | |
---|
| 744 | <p><strong>Complexity:</strong> Exactly k+1 invocations of the base |
---|
| 745 | generator.</p> |
---|
| 746 | <pre> |
---|
| 747 | template<class T> void seed(T s) |
---|
| 748 | </pre> |
---|
| 749 | |
---|
| 750 | <p><strong>Effects:</strong> Invokes the one-argument <code>seed</code> |
---|
| 751 | method of the base generator with the parameter <code>seed</code> and |
---|
| 752 | re-initializes the internal buffer array.</p> |
---|
| 753 | |
---|
| 754 | <p><strong>Complexity:</strong> Exactly k+1 invocations of the base |
---|
| 755 | generator.</p> |
---|
| 756 | |
---|
| 757 | <h3><a name="kreutzer1986" id="kreutzer1986">Specializations</a></h3> |
---|
| 758 | |
---|
| 759 | <p>According to Harry Erwin (private e-mail), the specialization |
---|
| 760 | <code>kreutzer1986</code> was suggested in:</p> |
---|
| 761 | |
---|
| 762 | <blockquote> |
---|
| 763 | "System Simulation: programming Styles and Languages (International |
---|
| 764 | Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December |
---|
| 765 | 1986. |
---|
| 766 | </blockquote> |
---|
| 767 | |
---|
| 768 | <h2><a name="inversive_congruential" id="inversive_congruential">Class |
---|
| 769 | template <code>random::inversive_congruential</code></a></h2> |
---|
| 770 | |
---|
| 771 | <h3>Synopsis</h3> |
---|
| 772 | <pre> |
---|
| 773 | #include <<a href= |
---|
| 774 | "../../boost/random/inversive_congruential.hpp">boost/random/inversive_congruential.hpp</a>> |
---|
| 775 | |
---|
| 776 | template<class IntType, IntType a, IntType b, IntType p> |
---|
| 777 | class random::inversive_congruential |
---|
| 778 | { |
---|
| 779 | public: |
---|
| 780 | typedef IntType result_type; |
---|
| 781 | static const bool has_fixed_range = true; |
---|
| 782 | static const result_type min_value = (b == 0 ? 1 : 0); |
---|
| 783 | static const result_type max_value = p-1; |
---|
| 784 | static const result_type multiplier = a; |
---|
| 785 | static const result_type increment = b; |
---|
| 786 | static const result_type modulus = p; |
---|
| 787 | explicit inversive_congruential(IntType y0 = 1); |
---|
| 788 | void seed(IntType y0); |
---|
| 789 | IntType operator()(); |
---|
| 790 | }; |
---|
| 791 | |
---|
| 792 | typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165, 2147483647> hellekalek1995; |
---|
| 793 | </pre> |
---|
| 794 | |
---|
| 795 | <h3>Description</h3> |
---|
| 796 | |
---|
| 797 | <p>Instantiations of class template <code>inversive_congruential</code> |
---|
| 798 | model a <a href="random-concepts.html#pseudo-rng">pseudo-random number |
---|
| 799 | generator</a>. It uses the inversive congruential algorithm (ICG) described |
---|
| 800 | in</p> |
---|
| 801 | |
---|
| 802 | <blockquote> |
---|
| 803 | "Inversive pseudorandom number generators: concepts, results and links", |
---|
| 804 | Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation |
---|
| 805 | Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman |
---|
| 806 | (editors), 1995, pp. 255-262. <a href= |
---|
| 807 | "ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps">ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps</a> |
---|
| 808 | </blockquote>The output sequence is defined by x(n+1) = (a*inv(x(n)) - b) |
---|
| 809 | (mod p), where x(0), a, b, and the prime number p are parameters of the |
---|
| 810 | generator. The expression inv(k) denotes the multiplicative inverse of k in |
---|
| 811 | the field of integer numbers modulo p, with inv(0) := 0. |
---|
| 812 | |
---|
| 813 | <p>The template parameter <code>IntType</code> shall denote a signed |
---|
| 814 | integral type large enough to hold p; a, b, and p are the parameters of the |
---|
| 815 | generators.</p> |
---|
| 816 | |
---|
| 817 | <p><em>Note:</em> The implementation currently uses the Euclidian Algorithm |
---|
| 818 | to compute the multiplicative inverse. Therefore, the inversive generators |
---|
| 819 | are about 10-20 times slower than the others (see section"<a href= |
---|
| 820 | "#performance">performance</a>"). However, the paper talks of only 3x |
---|
| 821 | slowdown, so the Euclidian Algorithm is probably not optimal for |
---|
| 822 | calculating the multiplicative inverse.</p> |
---|
| 823 | |
---|
| 824 | <h3>Members</h3> |
---|
| 825 | <pre> |
---|
| 826 | inversive_congruential(IntType y0 = 1) |
---|
| 827 | </pre> |
---|
| 828 | |
---|
| 829 | <p><strong>Effects:</strong> Constructs an |
---|
| 830 | <code>inversive_congruential</code> generator with <code>y0</code> as the |
---|
| 831 | initial state.</p> |
---|
| 832 | <pre> |
---|
| 833 | void seed(IntType y0) |
---|
| 834 | </pre> |
---|
| 835 | |
---|
| 836 | <p><strong>Effects:</strong> Changes the current state to |
---|
| 837 | <code>y0</code>.</p> |
---|
| 838 | |
---|
| 839 | <h3><a name="hellekalek1995" id="hellekalek1995">Specialization</a></h3> |
---|
| 840 | |
---|
| 841 | <p>The specialization <code>hellekalek1995</code> was suggested in the |
---|
| 842 | above paper.</p> |
---|
| 843 | |
---|
| 844 | <h2><a name="mersenne_twister" id="mersenne_twister">Class template |
---|
| 845 | <code>random::mersenne_twister</code></a></h2> |
---|
| 846 | |
---|
| 847 | <h3>Synopsis</h3> |
---|
| 848 | <pre> |
---|
| 849 | #include <<a href= |
---|
| 850 | "../../boost/random/mersenne_twister.hpp">boost/random/mersenne_twister.hpp</a>> |
---|
| 851 | |
---|
| 852 | template<class DataType, int w, int n, int m, int r, DataType a, int u, |
---|
| 853 | int s, DataType b, int t, DataType c, int l, IntType val> |
---|
| 854 | class random::mersenne_twister |
---|
| 855 | { |
---|
| 856 | public: |
---|
| 857 | typedef DataType result_type; |
---|
| 858 | static const bool has_fixed_range = true; |
---|
| 859 | static const result_type min_value; |
---|
| 860 | static const result_type max_value; |
---|
| 861 | mersenne_twister(); |
---|
| 862 | explicit mersenne_twister(DataType value); |
---|
| 863 | template<class Generator> explicit mersenne_twister(Generator & gen); |
---|
| 864 | // compiler-generated copy ctor and assignment operator are fine |
---|
| 865 | void seed(); |
---|
| 866 | void seed(DataType value); |
---|
| 867 | template<class Generator> void seed(Generator & gen); |
---|
| 868 | result_type operator()(); |
---|
| 869 | bool validation(result_type) const; |
---|
| 870 | }; |
---|
| 871 | |
---|
| 872 | typedef mersenne_twister<uint32_t,351,175,19,0xccab8ee7,11,7,0x31b6ab00,15,0xffe50000,17, /* unknown */ 0> mt11213b; |
---|
| 873 | typedef mersenne_twister<uint32_t,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937; |
---|
| 874 | </pre> |
---|
| 875 | |
---|
| 876 | <h3>Description</h3> |
---|
| 877 | |
---|
| 878 | <p>Instantiations of class template <code>mersenne_twister</code> model a |
---|
| 879 | <a href="random-concepts.html#pseudo-rng">pseudo-random number |
---|
| 880 | generator</a>. It uses the algorithm described in</p> |
---|
| 881 | |
---|
| 882 | <blockquote> |
---|
| 883 | "Mersenne Twister: A 623-dimensionally equidistributed uniform |
---|
| 884 | pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura, |
---|
| 885 | ACM Transactions on Modeling and Computer Simulation: Special Issue on |
---|
| 886 | Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30. |
---|
| 887 | <!-- <a href="http://www.math.keio.ac.jp/matumoto/emt.html">http://www.math.keio.ac.jp/matumoto/emt.html</a> --> |
---|
| 888 | </blockquote><em>Note:</em> The boost variant has been implemented from |
---|
| 889 | scratch and does not derive from or use mt19937.c provided on the above WWW |
---|
| 890 | site. However, it was verified that both produce identical output.<br> |
---|
| 891 | The seeding from an integer was changed in April 2005 to address a <a href= |
---|
| 892 | "http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>.<br> |
---|
| 893 | |
---|
| 894 | The quality of the generator crucially depends on the choice of the |
---|
| 895 | parameters. User code should employ one of the sensibly parameterized |
---|
| 896 | generators such as <code>mt19937</code> instead.<br> |
---|
| 897 | The generator requires considerable amounts of memory for the storage of |
---|
| 898 | its state array. For example, <code>mt11213b</code> requires about 1408 |
---|
| 899 | bytes and <code>mt19937</code> requires about 2496 bytes. |
---|
| 900 | |
---|
| 901 | <h3>Constructors</h3> |
---|
| 902 | <pre> |
---|
| 903 | mersenne_twister() |
---|
| 904 | </pre> |
---|
| 905 | |
---|
| 906 | <p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and |
---|
| 907 | calls <code>seed()</code>.</p> |
---|
| 908 | <pre> |
---|
| 909 | explicit mersenne_twister(result_type value) |
---|
| 910 | </pre> |
---|
| 911 | |
---|
| 912 | <p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and |
---|
| 913 | calls <code>seed(value)</code>.</p> |
---|
| 914 | <pre> |
---|
| 915 | template<class Generator> explicit mersenne_twister(Generator & gen) |
---|
| 916 | </pre> |
---|
| 917 | |
---|
| 918 | <p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and |
---|
| 919 | calls <code>seed(gen)</code>.</p> |
---|
| 920 | |
---|
| 921 | <p><em>Note:</em> When using direct-initialization syntax with an lvalue |
---|
| 922 | (e.g. in the variable definition <code>Gen gen2(gen);</code>), this |
---|
| 923 | templated constructor will be preferred over the compiler-generated copy |
---|
| 924 | constructor. For variable definitions which should copy the state of |
---|
| 925 | another <code>mersenne_twister</code>, use e.g. <code>Gen gen2 = |
---|
| 926 | gen;</code>, which is copy-initialization syntax and guaranteed to invoke |
---|
| 927 | the copy constructor.</p> |
---|
| 928 | |
---|
| 929 | <h3>Seeding</h3> |
---|
| 930 | <pre> |
---|
| 931 | void seed() |
---|
| 932 | </pre> |
---|
| 933 | |
---|
| 934 | <p><strong>Effects:</strong> Calls |
---|
| 935 | <code>seed(result_type(5489))</code>.</p> |
---|
| 936 | <pre> |
---|
| 937 | void seed(result_type value) |
---|
| 938 | </pre> |
---|
| 939 | |
---|
| 940 | <p><strong>Effects:</strong> Sets the state x(0) to v mod 2<sup>w</sup>. |
---|
| 941 | Then, iteratively,<br> |
---|
| 942 | sets x(i) to (i + 1812433253 * (x(i-1) <em>xor</em> (x(i-1) <em>rshift</em> |
---|
| 943 | w-2))) mod 2<sup>w</sup> for i = 1 .. n-1. x(n) is the first value to be |
---|
| 944 | returned by operator().</p> |
---|
| 945 | <pre> |
---|
| 946 | template<class Generator> void seed(Generator & gen) |
---|
| 947 | </pre> |
---|
| 948 | |
---|
| 949 | <p><strong>Effects:</strong> Sets the state of this |
---|
| 950 | <code>mersenne_twister</code> to the values returned by <code>n</code> |
---|
| 951 | invocations of <code>gen</code>.</p> |
---|
| 952 | |
---|
| 953 | <p><strong>Complexity:</strong> Exactly <code>n</code> invocations of |
---|
| 954 | <code>gen</code>.</p> |
---|
| 955 | |
---|
| 956 | <p><em>Note:</em> When invoking <code>seed</code> with an lvalue, overload |
---|
| 957 | resolution chooses the function template unless the type of the argument |
---|
| 958 | exactly matches <code>result_type</code>. For other integer types, you |
---|
| 959 | should convert the argument to <code>result_type</code> explicitly.</p> |
---|
| 960 | |
---|
| 961 | <h3><a name="mt11213b" id="mt11213b"></a><a name="mt19937" id= |
---|
| 962 | "mt19937">Specializations</a></h3> |
---|
| 963 | |
---|
| 964 | <p>The specializations <code>mt11213b</code> and <code>mt19937</code> are |
---|
| 965 | from the paper cited above.</p> |
---|
| 966 | |
---|
| 967 | <h2><a name="lagged_fibonacci" id="lagged_fibonacci">Class template |
---|
| 968 | <code>random::lagged_fibonacci</code></a></h2> |
---|
| 969 | |
---|
| 970 | <h3>Synopsis</h3> |
---|
| 971 | <pre> |
---|
| 972 | #include <<a href= |
---|
| 973 | "../../boost/random/lagged_fibonacci.hpp">boost/random/lagged_fibonacci.hpp</a>> |
---|
| 974 | |
---|
| 975 | template<class FloatType, unsigned int p, unsigned int q> |
---|
| 976 | class lagged_fibonacci |
---|
| 977 | { |
---|
| 978 | public: |
---|
| 979 | typedef FloatType result_type; |
---|
| 980 | static const bool has_fixed_range = false; |
---|
| 981 | static const unsigned int long_lag = p; |
---|
| 982 | static const unsigned int short_lag = q; |
---|
| 983 | result_type min() const { return 0.0; } |
---|
| 984 | result_type max() const { return 1.0; } |
---|
| 985 | lagged_fibonacci(); |
---|
| 986 | explicit lagged_fibonacci(uint32_t value); |
---|
| 987 | template<class Generator> |
---|
| 988 | explicit lagged_fibonacci(Generator & gen); |
---|
| 989 | // compiler-generated copy ctor and assignment operator are fine |
---|
| 990 | void seed(uint32_t value = 331u); |
---|
| 991 | template<class Generator> void seed(Generator & gen); |
---|
| 992 | result_type operator()(); |
---|
| 993 | bool validation(result_type x) const; |
---|
| 994 | }; |
---|
| 995 | |
---|
| 996 | typedef random::lagged_fibonacci<double, 607, 273> lagged_fibonacci607; |
---|
| 997 | typedef random::lagged_fibonacci<double, 1279, 418> lagged_fibonacci1279; |
---|
| 998 | typedef random::lagged_fibonacci<double, 2281, 1252> lagged_fibonacci2281; |
---|
| 999 | typedef random::lagged_fibonacci<double, 3217, 576> lagged_fibonacci3217; |
---|
| 1000 | typedef random::lagged_fibonacci<double, 4423, 2098> lagged_fibonacci4423; |
---|
| 1001 | typedef random::lagged_fibonacci<double, 9689, 5502> lagged_fibonacci9689; |
---|
| 1002 | typedef random::lagged_fibonacci<double, 19937, 9842> lagged_fibonacci19937; |
---|
| 1003 | typedef random::lagged_fibonacci<double, 23209, 13470> lagged_fibonacci23209; |
---|
| 1004 | typedef random::lagged_fibonacci<double, 44497, 21034> lagged_fibonacci44497; |
---|
| 1005 | </pre> |
---|
| 1006 | |
---|
| 1007 | <h3>Description</h3> |
---|
| 1008 | |
---|
| 1009 | <p>Instantiations of class template <code>lagged_fibonacci</code> model a |
---|
| 1010 | <a href="random-concepts.html#pseudo-rng">pseudo-random number |
---|
| 1011 | generator</a>. It uses a lagged Fibonacci algorithm with two lags p and q, |
---|
| 1012 | evaluated in floating-point arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with |
---|
| 1013 | p > q. See</p> |
---|
| 1014 | |
---|
| 1015 | <blockquote> |
---|
| 1016 | "Uniform random number generators for supercomputers", Richard Brent, |
---|
| 1017 | Proc. of Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, |
---|
| 1018 | pp. 704-706. |
---|
| 1019 | </blockquote> |
---|
| 1020 | |
---|
| 1021 | <p><em>Note:</em> The quality of the generator crucially depends on the |
---|
| 1022 | choice of the parameters. User code should employ one of the sensibly |
---|
| 1023 | parameterized generators such as <code>lagged_fibonacci607</code> |
---|
| 1024 | instead.<br> |
---|
| 1025 | The generator requires considerable amounts of memory for the storage of |
---|
| 1026 | its state array. For example, <code>lagged_fibonacci607</code> requires |
---|
| 1027 | about 4856 bytes and <code>lagged_fibonacci44497</code> requires about 350 |
---|
| 1028 | KBytes.</p> |
---|
| 1029 | |
---|
| 1030 | <h3>Constructors</h3> |
---|
| 1031 | <pre> |
---|
| 1032 | lagged_fibonacci() |
---|
| 1033 | </pre> |
---|
| 1034 | |
---|
| 1035 | <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code> |
---|
| 1036 | generator and calls <code>seed()</code>.</p> |
---|
| 1037 | <pre> |
---|
| 1038 | explicit lagged_fibonacci(uint32_t value) |
---|
| 1039 | </pre> |
---|
| 1040 | |
---|
| 1041 | <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code> |
---|
| 1042 | generator and calls <code>seed(value)</code>.</p> |
---|
| 1043 | <pre> |
---|
| 1044 | template<class Generator> explicit lagged_fibonacci(Generator & gen) |
---|
| 1045 | </pre> |
---|
| 1046 | |
---|
| 1047 | <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code> |
---|
| 1048 | generator and calls <code>seed(gen)</code>.</p> |
---|
| 1049 | |
---|
| 1050 | <h3>Seeding</h3> |
---|
| 1051 | <pre> |
---|
| 1052 | void seed() |
---|
| 1053 | </pre> |
---|
| 1054 | |
---|
| 1055 | <p><strong>Effects:</strong> Calls <code>seed(331u)</code>.</p> |
---|
| 1056 | <pre> |
---|
| 1057 | void seed(uint32_t value) |
---|
| 1058 | </pre> |
---|
| 1059 | |
---|
| 1060 | <p><strong>Effects:</strong> Constructs a <code>minstd_rand0</code> |
---|
| 1061 | generator with the constructor parameter <code>value</code> and calls |
---|
| 1062 | <code>seed</code> with it.</p> |
---|
| 1063 | <pre> |
---|
| 1064 | template<class Generator> void seed(Generator & gen) |
---|
| 1065 | </pre> |
---|
| 1066 | |
---|
| 1067 | <p><strong>Effects:</strong> Sets the state of this |
---|
| 1068 | <code>lagged_fibonacci</code> to the values returned by <code>p</code> |
---|
| 1069 | invocations of <code>uniform_01<gen, FloatType></code>.<br> |
---|
| 1070 | <strong>Complexity:</strong> Exactly <code>p</code> invocations of |
---|
| 1071 | <code>gen</code>.</p> |
---|
| 1072 | |
---|
| 1073 | <h3><a name="lagged_fibonacci_spec" id= |
---|
| 1074 | "lagged_fibonacci_spec"></a>Specializations</h3> |
---|
| 1075 | |
---|
| 1076 | <p>The specializations <code>lagged_fibonacci607</code> ... |
---|
| 1077 | <code>lagged_fibonacci44497</code> (see above) use well tested lags. |
---|
| 1078 | (References will be added later.)</p> |
---|
| 1079 | |
---|
| 1080 | <h2><a name="performance" id="performance">Performance</a></h2> |
---|
| 1081 | |
---|
| 1082 | <p>The test program <a href="random_speed.cpp">random_speed.cpp</a> |
---|
| 1083 | measures the execution times of the <a href= |
---|
| 1084 | "../../boost/random.hpp">random.hpp</a> implementation of the above |
---|
| 1085 | algorithms in a tight loop. The performance has been evaluated on a Pentium |
---|
| 1086 | Pro 200 MHz with gcc 2.95.2, Linux 2.2.13, glibc 2.1.2.</p> |
---|
| 1087 | |
---|
| 1088 | <table border="1" summary=""> |
---|
| 1089 | <tr> |
---|
| 1090 | <th>class</th> |
---|
| 1091 | |
---|
| 1092 | <th>time per invocation [usec]</th> |
---|
| 1093 | </tr> |
---|
| 1094 | |
---|
| 1095 | <tr> |
---|
| 1096 | <td>rand48</td> |
---|
| 1097 | |
---|
| 1098 | <td>0.096</td> |
---|
| 1099 | </tr> |
---|
| 1100 | |
---|
| 1101 | <tr> |
---|
| 1102 | <td>rand48 run-time configurable</td> |
---|
| 1103 | |
---|
| 1104 | <td>0.697</td> |
---|
| 1105 | </tr> |
---|
| 1106 | |
---|
| 1107 | <tr> |
---|
| 1108 | <td>lrand48 glibc 2.1.2</td> |
---|
| 1109 | |
---|
| 1110 | <td>0.844</td> |
---|
| 1111 | </tr> |
---|
| 1112 | |
---|
| 1113 | <tr> |
---|
| 1114 | <td>minstd_rand</td> |
---|
| 1115 | |
---|
| 1116 | <td>0.174</td> |
---|
| 1117 | </tr> |
---|
| 1118 | |
---|
| 1119 | <tr> |
---|
| 1120 | <td>ecuyer1988</td> |
---|
| 1121 | |
---|
| 1122 | <td>0.445</td> |
---|
| 1123 | </tr> |
---|
| 1124 | |
---|
| 1125 | <tr> |
---|
| 1126 | <td>kreutzer1986</td> |
---|
| 1127 | |
---|
| 1128 | <td>0.249</td> |
---|
| 1129 | </tr> |
---|
| 1130 | |
---|
| 1131 | <tr> |
---|
| 1132 | <td>hellekalek1995 (inversive)</td> |
---|
| 1133 | |
---|
| 1134 | <td>4.895</td> |
---|
| 1135 | </tr> |
---|
| 1136 | |
---|
| 1137 | <tr> |
---|
| 1138 | <td>mt11213b</td> |
---|
| 1139 | |
---|
| 1140 | <td>0.165</td> |
---|
| 1141 | </tr> |
---|
| 1142 | |
---|
| 1143 | <tr> |
---|
| 1144 | <td>mt19937</td> |
---|
| 1145 | |
---|
| 1146 | <td>0.165</td> |
---|
| 1147 | </tr> |
---|
| 1148 | |
---|
| 1149 | <tr> |
---|
| 1150 | <td>mt19937 original</td> |
---|
| 1151 | |
---|
| 1152 | <td>0.185</td> |
---|
| 1153 | </tr> |
---|
| 1154 | |
---|
| 1155 | <tr> |
---|
| 1156 | <td>lagged_fibonacci607</td> |
---|
| 1157 | |
---|
| 1158 | <td>0.111</td> |
---|
| 1159 | </tr> |
---|
| 1160 | |
---|
| 1161 | <tr> |
---|
| 1162 | <td>lagged_fibonacci4423</td> |
---|
| 1163 | |
---|
| 1164 | <td>0.112</td> |
---|
| 1165 | </tr> |
---|
| 1166 | |
---|
| 1167 | <tr> |
---|
| 1168 | <td>lagged_fibonacci19937</td> |
---|
| 1169 | |
---|
| 1170 | <td>0.113</td> |
---|
| 1171 | </tr> |
---|
| 1172 | |
---|
| 1173 | <tr> |
---|
| 1174 | <td>lagged_fibonacci23209</td> |
---|
| 1175 | |
---|
| 1176 | <td>0.122</td> |
---|
| 1177 | </tr> |
---|
| 1178 | |
---|
| 1179 | <tr> |
---|
| 1180 | <td>lagged_fibonacci44497</td> |
---|
| 1181 | |
---|
| 1182 | <td>0.263</td> |
---|
| 1183 | </tr> |
---|
| 1184 | </table> |
---|
| 1185 | |
---|
| 1186 | <p>The measurement error is estimated at +/- 10 nsec.</p> |
---|
| 1187 | <hr> |
---|
| 1188 | |
---|
| 1189 | <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= |
---|
| 1190 | "http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional" |
---|
| 1191 | height="31" width="88"></a></p> |
---|
| 1192 | |
---|
| 1193 | <p>Revised |
---|
| 1194 | <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05 |
---|
| 1195 | December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p> |
---|
| 1196 | |
---|
| 1197 | <p><i>Copyright © 2000-2005 <a href= |
---|
| 1198 | "../../people/jens_maurer.htm">Jens Maurer</a></i></p> |
---|
| 1199 | |
---|
| 1200 | <p><i>Distributed under the Boost Software License, Version 1.0. (See |
---|
| 1201 | accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or |
---|
| 1202 | copy at <a href= |
---|
| 1203 | "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> |
---|
| 1204 | </body> |
---|
| 1205 | </html> |
---|