[29] | 1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
---|
| 2 | |
---|
| 3 | <html> |
---|
| 4 | <head> |
---|
| 5 | <meta http-equiv="Content-Language" content="en-us"> |
---|
| 6 | <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> |
---|
| 7 | |
---|
| 8 | <title>Boost Random Number Library Concepts</title> |
---|
| 9 | </head> |
---|
| 10 | |
---|
| 11 | <body bgcolor="#FFFFFF" text="#000000"> |
---|
| 12 | <h1>Random Number Generator Library Concepts</h1> |
---|
| 13 | |
---|
| 14 | <h2>Introduction</h2> |
---|
| 15 | |
---|
| 16 | <p>Random numbers are required in a number of different problem domains, |
---|
| 17 | such as</p> |
---|
| 18 | |
---|
| 19 | <ul> |
---|
| 20 | <li>numerics (simulation, Monte-Carlo integration)</li> |
---|
| 21 | |
---|
| 22 | <li>games (non-deterministic enemy behavior)</li> |
---|
| 23 | |
---|
| 24 | <li>security (key generation)</li> |
---|
| 25 | |
---|
| 26 | <li>testing (random coverage in white-box tests)</li> |
---|
| 27 | </ul>The Boost Random Number Generator Library provides a framework for |
---|
| 28 | random number generators with well-defined properties so that the |
---|
| 29 | generators can be used in the demanding numerics and security domains. For |
---|
| 30 | a general introduction to random numbers in numerics, see |
---|
| 31 | |
---|
| 32 | <blockquote> |
---|
| 33 | "Numerical Recipes in C: The art of scientific computing", William H. |
---|
| 34 | Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd |
---|
| 35 | ed., 1992, pp. 274-328 |
---|
| 36 | </blockquote>Depending on the requirements of the problem domain, different |
---|
| 37 | variations of random number generators are appropriate: |
---|
| 38 | |
---|
| 39 | <ul> |
---|
| 40 | <li>non-deterministic random number generator</li> |
---|
| 41 | |
---|
| 42 | <li>pseudo-random number generator</li> |
---|
| 43 | |
---|
| 44 | <li>quasi-random number generator</li> |
---|
| 45 | </ul>All variations have some properties in common, these concepts (in the |
---|
| 46 | STL sense) are called NumberGenerator and UniformRandomNumberGenerator. |
---|
| 47 | Each concept will be defined in a subsequent section. |
---|
| 48 | |
---|
| 49 | <p>The goals for this library are the following:</p> |
---|
| 50 | |
---|
| 51 | <ul> |
---|
| 52 | <li>allow easy integration of third-party random-number generators</li> |
---|
| 53 | |
---|
| 54 | <li>define a validation interface for the generators</li> |
---|
| 55 | |
---|
| 56 | <li>provide easy-to-use front-end classes which model popular |
---|
| 57 | distributions</li> |
---|
| 58 | |
---|
| 59 | <li>provide maximum efficiency</li> |
---|
| 60 | |
---|
| 61 | <li>allow control on quantization effects in front-end processing (not |
---|
| 62 | yet done)</li> |
---|
| 63 | </ul> |
---|
| 64 | |
---|
| 65 | <h2><a name="number_generator" id="number_generator">Number |
---|
| 66 | Generator</a></h2> |
---|
| 67 | |
---|
| 68 | <p>A number generator is a <em>function object</em> (std:20.3 |
---|
| 69 | [lib.function.objects]) that takes zero arguments. Each call to |
---|
| 70 | <code>operator()</code> returns a number. In the following table, |
---|
| 71 | <code>X</code> denotes a number generator class returning objects of type |
---|
| 72 | <code>T</code>, and <code>u</code> is a value of <code>X</code>.</p> |
---|
| 73 | |
---|
| 74 | <table border="1"> |
---|
| 75 | <tr> |
---|
| 76 | <th colspan="3" align="center"><code>NumberGenerator</code> |
---|
| 77 | requirements</th> |
---|
| 78 | </tr> |
---|
| 79 | |
---|
| 80 | <tr> |
---|
| 81 | <td>expression</td> |
---|
| 82 | |
---|
| 83 | <td>return type</td> |
---|
| 84 | |
---|
| 85 | <td>pre/post-condition</td> |
---|
| 86 | </tr> |
---|
| 87 | |
---|
| 88 | <tr> |
---|
| 89 | <td><code>X::result_type</code></td> |
---|
| 90 | |
---|
| 91 | <td>T</td> |
---|
| 92 | |
---|
| 93 | <td><code>std::numeric_limits<T>::is_specialized</code> is true, |
---|
| 94 | <code>T</code> is <code>LessThanComparable</code></td> |
---|
| 95 | </tr> |
---|
| 96 | |
---|
| 97 | <tr> |
---|
| 98 | <td><code>u.operator()()</code></td> |
---|
| 99 | |
---|
| 100 | <td>T</td> |
---|
| 101 | |
---|
| 102 | <td>-</td> |
---|
| 103 | </tr> |
---|
| 104 | </table> |
---|
| 105 | |
---|
| 106 | <p><em>Note:</em> The NumberGenerator requirements do not impose any |
---|
| 107 | restrictions on the characteristics of the returned numbers.</p> |
---|
| 108 | |
---|
| 109 | <h2><a name="uniform-rng" id="uniform-rng">Uniform Random Number |
---|
| 110 | Generator</a></h2> |
---|
| 111 | |
---|
| 112 | <p>A uniform random number generator is a NumberGenerator that provides a |
---|
| 113 | sequence of random numbers uniformly distributed on a given range. The |
---|
| 114 | range can be compile-time fixed or available (only) after run-time |
---|
| 115 | construction of the object.</p> |
---|
| 116 | |
---|
| 117 | <p>The <em>tight lower bound</em> of some (finite) set S is the (unique) |
---|
| 118 | member l in S, so that for all v in S, l <= v holds. Likewise, the |
---|
| 119 | <em>tight upper bound</em> of some (finite) set S is the (unique) member u |
---|
| 120 | in S, so that for all v in S, v <= u holds.</p> |
---|
| 121 | |
---|
| 122 | <p>In the following table, <code>X</code> denotes a number generator class |
---|
| 123 | returning objects of type <code>T</code>, and <code>v</code> is a const |
---|
| 124 | value of <code>X</code>.</p> |
---|
| 125 | |
---|
| 126 | <table border="1"> |
---|
| 127 | <tr> |
---|
| 128 | <th colspan="3" align="center"> |
---|
| 129 | <code>UniformRandomNumberGenerator</code> requirements</th> |
---|
| 130 | </tr> |
---|
| 131 | |
---|
| 132 | <tr> |
---|
| 133 | <td>expression</td> |
---|
| 134 | |
---|
| 135 | <td>return type</td> |
---|
| 136 | |
---|
| 137 | <td>pre/post-condition</td> |
---|
| 138 | </tr> |
---|
| 139 | |
---|
| 140 | <tr> |
---|
| 141 | <td><code>X::has_fixed_range</code></td> |
---|
| 142 | |
---|
| 143 | <td><code>bool</code></td> |
---|
| 144 | |
---|
| 145 | <td>compile-time constant; if <code>true</code>, the range on which the |
---|
| 146 | random numbers are uniformly distributed is known at compile-time and |
---|
| 147 | members <code>min_value</code> and <code>max_value</code> exist. |
---|
| 148 | <em>Note:</em> This flag may also be <code>false</code> due to compiler |
---|
| 149 | limitations.</td> |
---|
| 150 | </tr> |
---|
| 151 | |
---|
| 152 | <tr> |
---|
| 153 | <td><code>X::min_value</code></td> |
---|
| 154 | |
---|
| 155 | <td><code>T</code></td> |
---|
| 156 | |
---|
| 157 | <td>compile-time constant; <code>min_value</code> is equal to |
---|
| 158 | <code>v.min()</code></td> |
---|
| 159 | </tr> |
---|
| 160 | |
---|
| 161 | <tr> |
---|
| 162 | <td><code>X::max_value</code></td> |
---|
| 163 | |
---|
| 164 | <td><code>T</code></td> |
---|
| 165 | |
---|
| 166 | <td>compile-time constant; <code>max_value</code> is equal to |
---|
| 167 | <code>v.max()</code></td> |
---|
| 168 | </tr> |
---|
| 169 | |
---|
| 170 | <tr> |
---|
| 171 | <td><code>v.min()</code></td> |
---|
| 172 | |
---|
| 173 | <td><code>T</code></td> |
---|
| 174 | |
---|
| 175 | <td>tight lower bound on the set of all values returned by |
---|
| 176 | <code>operator()</code>. The return value of this function shall not |
---|
| 177 | change during the lifetime of the object.</td> |
---|
| 178 | </tr> |
---|
| 179 | |
---|
| 180 | <tr> |
---|
| 181 | <td><code>v.max()</code></td> |
---|
| 182 | |
---|
| 183 | <td><code>T</code></td> |
---|
| 184 | |
---|
| 185 | <td>if <code>std::numeric_limits<T>::is_integer</code>, tight |
---|
| 186 | upper bound on the set of all values returned by |
---|
| 187 | <code>operator()</code>, otherwise, the smallest representable number |
---|
| 188 | larger than the tight upper bound on the set of all values returned by |
---|
| 189 | <code>operator()</code>. In any case, the return value of this function |
---|
| 190 | shall not change during the lifetime of the object.</td> |
---|
| 191 | </tr> |
---|
| 192 | </table> |
---|
| 193 | |
---|
| 194 | <p>The member functions <code>min</code>, <code>max</code>, and |
---|
| 195 | <code>operator()</code> shall have amortized constant time complexity.</p> |
---|
| 196 | |
---|
| 197 | <p><em>Note:</em> For integer generators (i.e. integer <code>T</code>), the |
---|
| 198 | generated values <code>x</code> fulfill <code>min() <= x <= |
---|
| 199 | max()</code>, for non-integer generators (i.e. non-integer <code>T</code>), |
---|
| 200 | the generated values <code>x</code> fulfill <code>min() <= x < |
---|
| 201 | max()</code>.<br> |
---|
| 202 | <em>Rationale:</em> The range description with <code>min</code> and |
---|
| 203 | <code>max</code> serves two purposes. First, it allows scaling of the |
---|
| 204 | values to some canonical range, such as [0..1). Second, it describes the |
---|
| 205 | significant bits of the values, which may be relevant for further |
---|
| 206 | processing.<br> |
---|
| 207 | The range is a closed interval [min,max] for integers, because the |
---|
| 208 | underlying type may not be able to represent the half-open interval |
---|
| 209 | [min,max+1). It is a half-open interval [min, max) for non-integers, |
---|
| 210 | because this is much more practical for borderline cases of continuous |
---|
| 211 | distributions.</p> |
---|
| 212 | |
---|
| 213 | <p><em>Note:</em> The UniformRandomNumberGenerator concept does not require |
---|
| 214 | <code>operator()(long)</code> and thus it does not fulfill the |
---|
| 215 | RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]) requirements. |
---|
| 216 | Use the <a href= |
---|
| 217 | "random-misc.html#random_number_generator"><code>random_number_generator</code></a> |
---|
| 218 | adapter for that.<br> |
---|
| 219 | <em>Rationale:</em> <code>operator()(long)</code> is not provided, because |
---|
| 220 | mapping the output of some generator with integer range to a different |
---|
| 221 | integer range is not trivial.</p> |
---|
| 222 | |
---|
| 223 | <h2><a name="nondet-rng" id="nondet-rng">Non-deterministic Uniform Random |
---|
| 224 | Number Generator</a></h2> |
---|
| 225 | |
---|
| 226 | <p>A non-deterministic uniform random number generator is a |
---|
| 227 | UniformRandomNumberGenerator that is based on some stochastic process. |
---|
| 228 | Thus, it provides a sequence of truly-random numbers. Examples for such |
---|
| 229 | processes are nuclear decay, noise of a Zehner diode, tunneling of quantum |
---|
| 230 | particles, rolling a die, drawing from an urn, and tossing a coin. |
---|
| 231 | Depending on the environment, inter-arrival times of network packets or |
---|
| 232 | keyboard events may be close approximations of stochastic processes.</p> |
---|
| 233 | |
---|
| 234 | <p>The class <code><a href= |
---|
| 235 | "nondet_random.html#random_device">random_device</a></code> is a model for |
---|
| 236 | a non-deterministic random number generator.</p> |
---|
| 237 | |
---|
| 238 | <p><em>Note:</em> This type of random-number generator is useful for |
---|
| 239 | security applications, where it is important to prevent that an outside |
---|
| 240 | attacker guesses the numbers and thus obtains your encryption or |
---|
| 241 | authentication key. Thus, models of this concept should be cautious not to |
---|
| 242 | leak any information, to the extent possible by the environment. For |
---|
| 243 | example, it might be advisable to explicitly clear any temporary storage as |
---|
| 244 | soon as it is no longer needed.</p> |
---|
| 245 | |
---|
| 246 | <h2><a name="pseudo-rng" id="pseudo-rng">Pseudo-Random Number |
---|
| 247 | Generator</a></h2> |
---|
| 248 | |
---|
| 249 | <p>A pseudo-random number generator is a UniformRandomNumberGenerator which |
---|
| 250 | provides a deterministic sequence of pseudo-random numbers, based on some |
---|
| 251 | algorithm and internal state. Linear congruential and inversive |
---|
| 252 | congruential generators are examples of such pseudo-random number |
---|
| 253 | generators. Often, these generators are very sensitive to their parameters. |
---|
| 254 | In order to prevent wrong implementations from being used, an external |
---|
| 255 | testsuite should check that the generated sequence and the validation value |
---|
| 256 | provided do indeed match.</p> |
---|
| 257 | |
---|
| 258 | <p>Donald E. Knuth gives an extensive overview on pseudo-random number |
---|
| 259 | generation in his book "The Art of Computer Programming, Vol. 2, 3rd |
---|
| 260 | edition, Addison-Wesley, 1997". The descriptions for the specific |
---|
| 261 | generators contain additional references.</p> |
---|
| 262 | |
---|
| 263 | <p><em>Note:</em> Because the state of a pseudo-random number generator is |
---|
| 264 | necessarily finite, the sequence of numbers returned by the generator will |
---|
| 265 | loop eventually.</p> |
---|
| 266 | |
---|
| 267 | <p>In addition to the UniformRandomNumberGenerator requirements, a |
---|
| 268 | pseudo-random number generator has some additional requirements. In the |
---|
| 269 | following table, <code>X</code> denotes a pseudo-random number generator |
---|
| 270 | class returning objects of type <code>T</code>, <code>x</code> is a value |
---|
| 271 | of <code>T</code>, <code>u</code> is a value of <code>X</code>, and |
---|
| 272 | <code>v</code> is a <code>const</code> value of <code>X</code>.</p> |
---|
| 273 | |
---|
| 274 | <table border="1"> |
---|
| 275 | <tr> |
---|
| 276 | <th colspan="3" align="center"><code>PseudoRandomNumberGenerator</code> |
---|
| 277 | requirements</th> |
---|
| 278 | </tr> |
---|
| 279 | |
---|
| 280 | <tr> |
---|
| 281 | <td>expression</td> |
---|
| 282 | |
---|
| 283 | <td>return type</td> |
---|
| 284 | |
---|
| 285 | <td>pre/post-condition</td> |
---|
| 286 | </tr> |
---|
| 287 | |
---|
| 288 | <tr> |
---|
| 289 | <td><code>X()</code></td> |
---|
| 290 | |
---|
| 291 | <td>-</td> |
---|
| 292 | |
---|
| 293 | <td>creates a generator in some implementation-defined state. |
---|
| 294 | <em>Note:</em> Several generators thusly created may possibly produce |
---|
| 295 | dependent or identical sequences of random numbers.</td> |
---|
| 296 | </tr> |
---|
| 297 | |
---|
| 298 | <tr> |
---|
| 299 | <td><code>explicit X(...)</code></td> |
---|
| 300 | |
---|
| 301 | <td>-</td> |
---|
| 302 | |
---|
| 303 | <td>creates a generator with user-provided state; the implementation |
---|
| 304 | shall specify the constructor argument(s)</td> |
---|
| 305 | </tr> |
---|
| 306 | |
---|
| 307 | <tr> |
---|
| 308 | <td><code>u.seed(...)</code></td> |
---|
| 309 | |
---|
| 310 | <td>void</td> |
---|
| 311 | |
---|
| 312 | <td>sets the current state according to the argument(s); at least |
---|
| 313 | functions with the same signature as the non-default constructor(s) |
---|
| 314 | shall be provided.</td> |
---|
| 315 | </tr> |
---|
| 316 | |
---|
| 317 | <tr> |
---|
| 318 | <td><code>X::validation(x)</code></td> |
---|
| 319 | |
---|
| 320 | <td><code>bool</code></td> |
---|
| 321 | |
---|
| 322 | <td>compares the pre-computed and hardcoded 10001th element in the |
---|
| 323 | generator's random number sequence with <code>x</code>. The generator |
---|
| 324 | must have been constructed by its default constructor and |
---|
| 325 | <code>seed</code> must not have been called for the validation to be |
---|
| 326 | meaningful.</td> |
---|
| 327 | </tr> |
---|
| 328 | </table> |
---|
| 329 | |
---|
| 330 | <p><em>Note:</em> The <code>seed</code> member function is similar to the |
---|
| 331 | <code>assign</code> member function in STL containers. However, the naming |
---|
| 332 | did not seem appropriate.</p> |
---|
| 333 | |
---|
| 334 | <p>Classes which model a pseudo-random number generator shall also model |
---|
| 335 | EqualityComparable, i.e. implement <code>operator==</code>. Two |
---|
| 336 | pseudo-random number generators are defined to be <em>equivalent</em> if |
---|
| 337 | they both return an identical sequence of numbers starting from a given |
---|
| 338 | state.</p> |
---|
| 339 | |
---|
| 340 | <p>Classes which model a pseudo-random number generator should also model |
---|
| 341 | the Streamable concept, i.e. implement <code>operator<<</code> and |
---|
| 342 | <code>operator>></code>. If so, <code>operator<<</code> writes |
---|
| 343 | all current state of the pseudo-random number generator to the given |
---|
| 344 | <code>ostream</code> so that <code>operator>></code> can restore the |
---|
| 345 | state at a later time. The state shall be written in a platform-independent |
---|
| 346 | manner, but it is assumed that the <code>locale</code>s used for writing |
---|
| 347 | and reading be the same. The pseudo-random number generator with the |
---|
| 348 | restored state and the original at the just-written state shall be |
---|
| 349 | equivalent.</p> |
---|
| 350 | |
---|
| 351 | <p>Classes which model a pseudo-random number generator may also model the |
---|
| 352 | CopyConstructible and Assignable concepts. However, note that the sequences |
---|
| 353 | of the original and the copy are strongly correlated (in fact, they are |
---|
| 354 | identical), which may make them unsuitable for some problem domains. Thus, |
---|
| 355 | copying pseudo-random number generators is discouraged; they should always |
---|
| 356 | be passed by (non-<code>const</code>) reference.</p> |
---|
| 357 | |
---|
| 358 | <p>The classes <code><a href= |
---|
| 359 | "random-generators.html#rand48">rand48</a></code>, <code><a href= |
---|
| 360 | "random-generators.html#linear_congruential">minstd_rand</a></code>, and |
---|
| 361 | <code><a href="random-generators.html#mersenne_twister">mt19937</a></code> |
---|
| 362 | are models for a pseudo-random number generator.</p> |
---|
| 363 | |
---|
| 364 | <p><em>Note:</em> This type of random-number generator is useful for |
---|
| 365 | numerics, games and testing. The non-zero arguments constructor(s) and the |
---|
| 366 | <code>seed()</code> member function(s) allow for a user-provided state to |
---|
| 367 | be installed in the generator. This is useful for debugging Monte-Carlo |
---|
| 368 | algorithms and analyzing particular test scenarios. The Streamable concept |
---|
| 369 | allows to save/restore the state of the generator, for example to re-run a |
---|
| 370 | test suite at a later time.</p> |
---|
| 371 | |
---|
| 372 | <h2><a name="random-dist" id="random-dist">Random Distribution</a></h2> |
---|
| 373 | |
---|
| 374 | <p>A radom distribution produces random numbers distributed according to |
---|
| 375 | some distribution, given uniformly distributed random values as input. In |
---|
| 376 | the following table, <code>X</code> denotes a random distribution class |
---|
| 377 | returning objects of type <code>T</code>, <code>u</code> is a value of |
---|
| 378 | <code>X</code>, <code>x</code> is a (possibly const) value of |
---|
| 379 | <code>X</code>, and <code>e</code> is an lvalue of an arbitrary type that |
---|
| 380 | meets the requirements of a uniform random number generator, returning |
---|
| 381 | values of type <code>U</code>.</p> |
---|
| 382 | |
---|
| 383 | <table border="1"> |
---|
| 384 | <tr> |
---|
| 385 | <th colspan="4" align="center">Random distribution requirements (in |
---|
| 386 | addition to number generator, <code>CopyConstructible</code>, and |
---|
| 387 | <code>Assignable</code>)</th> |
---|
| 388 | </tr> |
---|
| 389 | |
---|
| 390 | <tr> |
---|
| 391 | <td>expression</td> |
---|
| 392 | |
---|
| 393 | <td>return type</td> |
---|
| 394 | |
---|
| 395 | <td>pre/post-condition</td> |
---|
| 396 | |
---|
| 397 | <td>complexity</td> |
---|
| 398 | </tr> |
---|
| 399 | |
---|
| 400 | <tr> |
---|
| 401 | <td><code>X::input_type</code></td> |
---|
| 402 | |
---|
| 403 | <td>U</td> |
---|
| 404 | |
---|
| 405 | <td>-</td> |
---|
| 406 | |
---|
| 407 | <td>compile-time</td> |
---|
| 408 | </tr> |
---|
| 409 | |
---|
| 410 | <tr> |
---|
| 411 | <td><code>u.reset()</code></td> |
---|
| 412 | |
---|
| 413 | <td><code>void</code></td> |
---|
| 414 | |
---|
| 415 | <td>subsequent uses of <code>u</code> do not depend on values produced |
---|
| 416 | by <code>e</code> prior to invoking <code>reset</code>.</td> |
---|
| 417 | |
---|
| 418 | <td>constant</td> |
---|
| 419 | </tr> |
---|
| 420 | |
---|
| 421 | <tr> |
---|
| 422 | <td><code>u(e)</code></td> |
---|
| 423 | |
---|
| 424 | <td><code>T</code></td> |
---|
| 425 | |
---|
| 426 | <td>the sequence of numbers returned by successive invocations with the |
---|
| 427 | same object <code>e</code> is randomly distributed with some |
---|
| 428 | probability density function p(x)</td> |
---|
| 429 | |
---|
| 430 | <td>amortized constant number of invocations of <code>e</code></td> |
---|
| 431 | </tr> |
---|
| 432 | |
---|
| 433 | <tr> |
---|
| 434 | <td><code>os << x</code></td> |
---|
| 435 | |
---|
| 436 | <td><code>std::ostream&</code></td> |
---|
| 437 | |
---|
| 438 | <td>writes a textual representation for the parameters and additional |
---|
| 439 | internal data of the distribution <code>x</code> to |
---|
| 440 | <code>os</code>.<br> |
---|
| 441 | post: The <code>os.<em>fmtflags</em></code> and fill character are |
---|
| 442 | unchanged.</td> |
---|
| 443 | |
---|
| 444 | <td>O(size of state)</td> |
---|
| 445 | </tr> |
---|
| 446 | |
---|
| 447 | <tr> |
---|
| 448 | <td><code>is >> u</code></td> |
---|
| 449 | |
---|
| 450 | <td><code>std::istream&</code></td> |
---|
| 451 | |
---|
| 452 | <td>restores the parameters and additional internal data of the |
---|
| 453 | distribution <code>u</code>.<br> |
---|
| 454 | pre: <code>is</code> provides a textual representation that was |
---|
| 455 | previously written by <code>operator<<</code><br> |
---|
| 456 | post: The <code>is.<em>fmtflags</em></code> are unchanged.</td> |
---|
| 457 | |
---|
| 458 | <td>O(size of state)</td> |
---|
| 459 | </tr> |
---|
| 460 | </table> |
---|
| 461 | |
---|
| 462 | <p>Additional requirements: The sequence of numbers produced by repeated |
---|
| 463 | invocations of <code>x(e)</code> does not change whether or not <code>os |
---|
| 464 | << x</code> is invoked between any of the invocations |
---|
| 465 | <code>x(e)</code>. If a textual representation is written using <code>os |
---|
| 466 | << x</code> and that representation is restored into the same or a |
---|
| 467 | different object <code>y</code> of the same type using <code>is >> |
---|
| 468 | y</code>, repeated invocations of <code>y(e)</code> produce the same |
---|
| 469 | sequence of random numbers as would repeated invocations of |
---|
| 470 | <code>x(e)</code>.</p> |
---|
| 471 | |
---|
| 472 | <h2><a name="quasi-rng" id="quasi-rng">Quasi-Random Number |
---|
| 473 | Generators</a></h2> |
---|
| 474 | |
---|
| 475 | <p>A quasi-random number generator is a Number Generator which provides a |
---|
| 476 | deterministic sequence of numbers, based on some algorithm and internal |
---|
| 477 | state. The numbers do not have any statistical properties (such as uniform |
---|
| 478 | distribution or independence of successive values).</p> |
---|
| 479 | |
---|
| 480 | <p><em>Note:</em> Quasi-random number generators are useful for Monte-Carlo |
---|
| 481 | integrations where specially crafted sequences of random numbers will make |
---|
| 482 | the approximation converge faster.</p> |
---|
| 483 | |
---|
| 484 | <p><em>[Does anyone have a model?]</em></p> |
---|
| 485 | <hr> |
---|
| 486 | |
---|
| 487 | <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= |
---|
| 488 | "http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional" |
---|
| 489 | height="31" width="88"></a></p> |
---|
| 490 | |
---|
| 491 | <p>Revised |
---|
| 492 | <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05 |
---|
| 493 | December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p> |
---|
| 494 | |
---|
| 495 | <p><i>Copyright © 2000-2003 <a href= |
---|
| 496 | "../../people/jens_maurer.htm">Jens Maurer</a></i></p> |
---|
| 497 | |
---|
| 498 | <p><i>Distributed under the Boost Software License, Version 1.0. (See |
---|
| 499 | accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or |
---|
| 500 | copy at <a href= |
---|
| 501 | "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> |
---|
| 502 | </body> |
---|
| 503 | </html> |
---|