[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>A Proposal to Add an Extensible Random Number Facility to the |
---|
| 9 | Standard Library</title> |
---|
| 10 | </head> |
---|
| 11 | |
---|
| 12 | <body bgcolor="#FFFFFF" text="#000000"> |
---|
| 13 | <font size="-1">Jens Maurer <Jens.Maurer@gmx.net><br> |
---|
| 14 | 2002-11-10<br> |
---|
| 15 | Document N1398=02-0056</font> |
---|
| 16 | |
---|
| 17 | <p><font size="-1"><code>$Id: proposal.html,v 1.44 2002/11/10 20:42:15 |
---|
| 18 | jmaurer Exp $</code></font></p> |
---|
| 19 | |
---|
| 20 | <h1>A Proposal to Add an Extensible Random Number Facility to the Standard |
---|
| 21 | Library (N1398)</h1> |
---|
| 22 | |
---|
| 23 | <blockquote> |
---|
| 24 | Any one who considers arithmetical methods of producing random digits is, |
---|
| 25 | of course, in a state of sin. |
---|
| 26 | </blockquote> |
---|
| 27 | |
---|
| 28 | <p align="right">John von Neumann, 1951</p> |
---|
| 29 | |
---|
| 30 | <h2>Revision history</h2> |
---|
| 31 | |
---|
| 32 | <ul> |
---|
| 33 | <li>2002-11-10: Publication in the Post-Santa Cruz mailing.</li> |
---|
| 34 | |
---|
| 35 | <li>The <code>seed(first, last)</code> interface now needs "unsigned |
---|
| 36 | long" values.</li> |
---|
| 37 | |
---|
| 38 | <li>Introduce "variate_generator", adjust distribution interface |
---|
| 39 | accordingly.</li> |
---|
| 40 | |
---|
| 41 | <li>Add "add-on packages" discussion.</li> |
---|
| 42 | |
---|
| 43 | <li>All distribution parameters must be defaulted.</li> |
---|
| 44 | |
---|
| 45 | <li>Add "target audience" subsection to "motivation" section.</li> |
---|
| 46 | |
---|
| 47 | <li>Add discussion of manager class.</li> |
---|
| 48 | |
---|
| 49 | <li>Engines are independent of distributions, thus consider respective |
---|
| 50 | lifetimes.</li> |
---|
| 51 | |
---|
| 52 | <li>Add "sharing of engines" as a major requirement.</li> |
---|
| 53 | |
---|
| 54 | <li>Add some open issues.</li> |
---|
| 55 | |
---|
| 56 | <li>2002-10-11: First publication on the C++ committee's library |
---|
| 57 | reflector.</li> |
---|
| 58 | </ul> |
---|
| 59 | |
---|
| 60 | <h2>I. Motivation</h2> |
---|
| 61 | |
---|
| 62 | <blockquote> |
---|
| 63 | <i>Why is this important? What kinds of problems does it address, and |
---|
| 64 | what kinds of programmers, is it intended to support? Is it based on |
---|
| 65 | existing practice?</i> |
---|
| 66 | </blockquote>Computers are deterministic machines by design: equal input |
---|
| 67 | data results in equal output, given the same internal state. Sometimes, |
---|
| 68 | applications require seemingly non-deterministic behaviour, usually |
---|
| 69 | provided by generating random numbers. Such applications include: |
---|
| 70 | |
---|
| 71 | <ul> |
---|
| 72 | <li>numerics (simulation, Monte-Carlo integration)</li> |
---|
| 73 | |
---|
| 74 | <li>games (shuffling card decks, non-deterministic enemy behavior)</li> |
---|
| 75 | |
---|
| 76 | <li>testing (generation of test input data for good coverage)</li> |
---|
| 77 | |
---|
| 78 | <li>security (generation of cryptographic keys)</li> |
---|
| 79 | </ul> |
---|
| 80 | |
---|
| 81 | <p>Programmers in all of the above areas have to find ways to generate |
---|
| 82 | random numbers. However, the difficulty to find generators that are both |
---|
| 83 | efficient and have good quality is often underestimated, and so ad-hoc |
---|
| 84 | implementations often fail to meet either or both of these goals.</p> |
---|
| 85 | |
---|
| 86 | <p>The C++ standard library includes <code>std::rand</code>, inherited from |
---|
| 87 | the C standard library, as the only facility to generate pseudo-random |
---|
| 88 | numbers. It is underspecified, because the generation function is not |
---|
| 89 | defined, and indeed early C standard library implementations provided |
---|
| 90 | surprisingly bad generators. Furthermore, the interface relies on global |
---|
| 91 | state, making it difficult or inefficient to provide for correct operation |
---|
| 92 | for simultaneous invocations in multi-threaded applications.</p> |
---|
| 93 | |
---|
| 94 | <p>There is a lot of existing practice in this area. A multitude of |
---|
| 95 | libraries, usually implemented in C or Fortran, is available from the |
---|
| 96 | scientific community. Some implement just one random number engine, others |
---|
| 97 | seek to provide a full framework. I know of no comprehensive C++ framework |
---|
| 98 | for generating random numbers that adheres to the design principles put |
---|
| 99 | forth in section III.</p> |
---|
| 100 | |
---|
| 101 | <p>Random number generators are appropriate for this TR because they fall |
---|
| 102 | into one of the domains (numerics) identified in N1314 as a target for the |
---|
| 103 | TR.</p> |
---|
| 104 | |
---|
| 105 | <h3>Target Audience</h3>There are several different kinds of programmers |
---|
| 106 | that are assumed to use the facilities provided in this proposal. |
---|
| 107 | |
---|
| 108 | <ul> |
---|
| 109 | <li>programmers that provide additional engines</li> |
---|
| 110 | |
---|
| 111 | <li>programmers that provide additional distributions</li> |
---|
| 112 | |
---|
| 113 | <li>programmers that provide generic add-on packages</li> |
---|
| 114 | |
---|
| 115 | <li>programmers that need random numbers</li> |
---|
| 116 | </ul>This proposal specifies an infrastructure so that the needs of all |
---|
| 117 | four groups are met. The first two groups benefit from a modular design so |
---|
| 118 | that they can plug in their contributions. Providing add-on packages |
---|
| 119 | benefits from a design that suits to generic programming needs. Finally, |
---|
| 120 | users in need of random numbers benefit from an interface to the package |
---|
| 121 | that is easy to use. |
---|
| 122 | |
---|
| 123 | <h2>II. Impact On the Standard</h2> |
---|
| 124 | |
---|
| 125 | <blockquote> |
---|
| 126 | <i>What does it depend on, and what depends on it? Is it a pure |
---|
| 127 | extension, or does it require changes to standard components? Does it |
---|
| 128 | require core language changes?</i> |
---|
| 129 | </blockquote>This proposal is a pure library extension. It does not require |
---|
| 130 | changes to any standard classes or functions. It does not require changes |
---|
| 131 | to any of the standard requirement tables. It does not require any changes |
---|
| 132 | in the core language, and it has been implemented in standard C++ as per |
---|
| 133 | ISO 14882:1998. |
---|
| 134 | |
---|
| 135 | <p>The ISO C99 extension that specify integral types having a given minimum |
---|
| 136 | or exact bitwidth (e.g. <code>int32_t</code>) aids in implementing this |
---|
| 137 | proposal, however these types (or the equivalent thereof under another |
---|
| 138 | name) can be defined with template metaprogramming in standard C++, so |
---|
| 139 | these are not strictly necessary.</p> |
---|
| 140 | |
---|
| 141 | <p>In case the ISO C99 extensions become part of the TR, section IV should |
---|
| 142 | be reviewed whether some requirements could be reformulated with the ISO |
---|
| 143 | C99 extensions.</p> |
---|
| 144 | |
---|
| 145 | <p>In case a standard reference-counted smart pointer becomes part of the |
---|
| 146 | TR, section IV should be reviewed and instances of the smart pointer be |
---|
| 147 | added to the acceptable template parameters for a |
---|
| 148 | <code>variate_generator</code>.</p> |
---|
| 149 | |
---|
| 150 | <h2>III. Design Decisions</h2> |
---|
| 151 | |
---|
| 152 | <blockquote> |
---|
| 153 | <i>Why did you choose the specific design that you did? What alternatives |
---|
| 154 | did you consider, and what are the tradeoffs? What are the consequences |
---|
| 155 | of your choice, for users and implementors? What decisions are left up to |
---|
| 156 | implementors? If there are any similar libraries in use, how do their |
---|
| 157 | design decisions compare to yours?</i> |
---|
| 158 | </blockquote>The design decisions are compared to those in the following |
---|
| 159 | libraries: |
---|
| 160 | |
---|
| 161 | <ul> |
---|
| 162 | <li>CLHEP (original at http://wwwinfo.cern.ch/asd/lhc++/clhep/index.html, |
---|
| 163 | modifications from FermiLab at (anonymous CVS) |
---|
| 164 | :pserver:anonymous@zoomcvs.fnal.gov:/usr/people/cvsuser/repository)</li> |
---|
| 165 | |
---|
| 166 | <li>crng 1.1: Random-number generators (RNGs) implemented as Python |
---|
| 167 | extension types coded in C (at http://www.sbc.su.se/~per/crng/)</li> |
---|
| 168 | |
---|
| 169 | <li>Swarm 2.1.1 (multi-agent simulation of complex systems), random |
---|
| 170 | number package, using a Smalltalk-like programming language (at |
---|
| 171 | http://www.santafe.edu/projects/swarm/swarmdocs/set/swarm.random.sgml.reference.html)</li> |
---|
| 172 | |
---|
| 173 | <li>GNU Scientific Library: general scientific computing library |
---|
| 174 | implemented in C, comprehensive coverage of random number engines and |
---|
| 175 | distributions (at http://sources.redhat.com/gsl)</li> |
---|
| 176 | </ul>The choice of engines and distributions is also contrasted against the |
---|
| 177 | following literature: |
---|
| 178 | |
---|
| 179 | <ul> |
---|
| 180 | <li>Donald E. Knuth, "The Art of Computer Programming Vol. 2"</li> |
---|
| 181 | |
---|
| 182 | <li>William H. Press et al., "Numerical Recipes in C"</li> |
---|
| 183 | </ul> |
---|
| 184 | |
---|
| 185 | <h3>A. Overview on Requirements</h3>Here is a short overview on the |
---|
| 186 | requirements for the random number framework. |
---|
| 187 | |
---|
| 188 | <ul> |
---|
| 189 | <li>allows users to choose in speed / size / quality trade-offs</li> |
---|
| 190 | |
---|
| 191 | <li>has a tight enough specification to get reliable cross-platform |
---|
| 192 | results</li> |
---|
| 193 | |
---|
| 194 | <li>allows storage of state on non-volatile media (e.g., in a disk file) |
---|
| 195 | to resume computation later</li> |
---|
| 196 | |
---|
| 197 | <li>does not impede sequence "jump-ahead" for parallel computation</li> |
---|
| 198 | |
---|
| 199 | <li>provides a variety of base engines, not just one</li> |
---|
| 200 | |
---|
| 201 | <li>allows the user to write its own base engines and use it with the |
---|
| 202 | library-provided distributions</li> |
---|
| 203 | |
---|
| 204 | <li>provides the most popular distributions</li> |
---|
| 205 | |
---|
| 206 | <li>allows the user to write its own distributions and use it with the |
---|
| 207 | library-provided engines</li> |
---|
| 208 | |
---|
| 209 | <li>allows sharing of engines by several distributions</li> |
---|
| 210 | |
---|
| 211 | <li>does not prevent implementations with utmost efficiency</li> |
---|
| 212 | |
---|
| 213 | <li>provides both pseudo-random number engines (for simulations etc.) and |
---|
| 214 | "true" non-deterministic random numbers (for cryptography)</li> |
---|
| 215 | </ul>All of the requirements are revisited in detail in the following |
---|
| 216 | sections. |
---|
| 217 | |
---|
| 218 | <h3>B. Pseudo-Random vs. Non-Deterministic Random Numbers</h3>This section |
---|
| 219 | tries to avoid philosophical discussions about randomness as much as |
---|
| 220 | possible, a certain amount of intuition is assumed. |
---|
| 221 | |
---|
| 222 | <p>In this proposal, a <em>pseudo-random number engine</em> is defined as |
---|
| 223 | an initial internal state x(0), a function f that moves from one internal |
---|
| 224 | state to the next x(i+1) := f(x(i)), and an output function o that produces |
---|
| 225 | the output o(x(i)) of the generator. This is an entirely deterministic |
---|
| 226 | process, it is determined by the initial state x(0) and functions f and o |
---|
| 227 | only. The initial state x(0) is determined from a seed. Apparent randomness |
---|
| 228 | is achieved only because the user has limited perception.</p> |
---|
| 229 | |
---|
| 230 | <p>A <em>non-deterministic random-number engine</em> provides a sequence of |
---|
| 231 | random numbers x(i) that cannot be foreseen. Examples are certain |
---|
| 232 | quantum-level physics experiments, measuring the time difference between |
---|
| 233 | radioactive decay of individual atoms or noise of a Zehner diode. |
---|
| 234 | Relatively unforeseeable random sources are also (the low bits of) timing |
---|
| 235 | between key touches, mouse movements, Ethernet packet arrivals, etc. An |
---|
| 236 | estimate for the amount of unforeseeability is the entropy, a concept from |
---|
| 237 | information theory. Completely foreseeable sequences (e.g., from |
---|
| 238 | pseudo-random number engines) have entropy 0, if all bits are |
---|
| 239 | unforeseeable, the entropy is equal to the number of bits in each |
---|
| 240 | number.</p> |
---|
| 241 | |
---|
| 242 | <p>Pseudo-random number engines are usually much faster than |
---|
| 243 | non-deterministic random-number engines, because the latter require I/O to |
---|
| 244 | query some randomness device outside of the computer. However, there is a |
---|
| 245 | common interface feature subset of both pseudo-random and non-deterministic |
---|
| 246 | random-number engines. For example, a non-deterministic random-number |
---|
| 247 | engine could be employed to produce random numbers with normal |
---|
| 248 | distribution; I believe this to be an unlikely scenario in practice.</p> |
---|
| 249 | |
---|
| 250 | <p>Other libraries, including those mentioned above, only provide either |
---|
| 251 | pseudo-random numbers, suitable for simulations and games, or |
---|
| 252 | non-deterministic random numbers, suitable for cryptographic |
---|
| 253 | applications.</p> |
---|
| 254 | |
---|
| 255 | <h3>C. Separation of Engines and Distributions</h3>Random-number generation |
---|
| 256 | is usually conceptually separated into <em>random-number engines</em> that |
---|
| 257 | produce uniformly distributed random numbers between a given minimum and |
---|
| 258 | maximum and <em>random-number distributions</em> that retrieve uniformly |
---|
| 259 | distributed random numbers from some engine and produce numbers according |
---|
| 260 | to some distribution (e.g., Gaussian normal or Bernoulli distribution). |
---|
| 261 | Returning to the formalism from section A, the former can be identified |
---|
| 262 | with the function f and the latter with the output function o. |
---|
| 263 | |
---|
| 264 | <p>This proposal honours this conceptual separation, and provides a class |
---|
| 265 | template to merge an arbitrary engine with an arbitrary distribution on |
---|
| 266 | top. To this end, this proposal sets up requirements for engines so that |
---|
| 267 | each of them can be used to provide uniformly distributed random numbers |
---|
| 268 | for any of the distributions. The resulting freedom of combination allows |
---|
| 269 | for the utmost re-use.</p> |
---|
| 270 | |
---|
| 271 | <p>Engines have usually been analyzed with all mathematical and empirical |
---|
| 272 | tools currently available. Nonetheless, those tools show the absence of a |
---|
| 273 | particular weakness only, and are not exhaustive. Albeit unlikely, a new |
---|
| 274 | kind of test (for example, a use of random numbers in a new kind of |
---|
| 275 | simulation or game) could show serious weaknesses in some engines that were |
---|
| 276 | not known before.</p> |
---|
| 277 | |
---|
| 278 | <p>This proposal attempts to specify the engines precisely; two different |
---|
| 279 | implementations, with the same seed, should return the same output |
---|
| 280 | sequence. This forces implementations to use the well-researched engines |
---|
| 281 | specified hereinafter, and users can have confidence in their quality and |
---|
| 282 | the limits thereof.</p> |
---|
| 283 | |
---|
| 284 | <p>On the other hand, the specifications for the distributions only define |
---|
| 285 | the statistical result, not the precise algorithm to use. This is different |
---|
| 286 | from engines, because for distribution algorithms, rigorous proofs of their |
---|
| 287 | correctness are available, usually under the precondition that the input |
---|
| 288 | random numbers are (truely) uniformly distributed. For example, there are |
---|
| 289 | at least a handful of algorithms known to produce normally distributed |
---|
| 290 | random numbers from uniformly distributed ones. Which one of these is most |
---|
| 291 | efficient depends on at least the relative execution speeds for various |
---|
| 292 | transcendental functions, cache and branch prediction behaviour of the CPU, |
---|
| 293 | and desired memory use. This proposal therefore leaves the choice of the |
---|
| 294 | algorithm to the implementation. It follows that output sequences for the |
---|
| 295 | distributions will not be identical across implementations. It is expected |
---|
| 296 | that implementations will carefully choose the algorithms for distributions |
---|
| 297 | up front, since it is certainly surprising to customers if some |
---|
| 298 | distribution produces different numbers from one implementation version to |
---|
| 299 | the next.</p> |
---|
| 300 | |
---|
| 301 | <p>Other libraries usually provide the same differentiation between engines |
---|
| 302 | and distributions. Libraries rarely have a wrapper around both engine and |
---|
| 303 | distribution, but it turns out that this can hide some complexities from |
---|
| 304 | the authors of distributions, since some facitilies need to be provided |
---|
| 305 | only once. A previous version of this proposal had distributions directly |
---|
| 306 | exposed to the user, and the distribution type dependent on the engine |
---|
| 307 | type. In various discussions, this was considered as too much coupling.</p> |
---|
| 308 | |
---|
| 309 | <p>Since other libraries do not aim to provide a portable specification |
---|
| 310 | framework, engines are sometimes only described qualitatively without |
---|
| 311 | giving the exact parameterization. Also, distributions are given as |
---|
| 312 | specific functions or classes, so the quality-of-implementation question |
---|
| 313 | which distribution algorithm to employ does not need to be addressed.</p> |
---|
| 314 | |
---|
| 315 | <h3>D. Templates vs. Virtual Functions</h3>The layering sketched in the |
---|
| 316 | previous subsection can be implemented by either a template mechanism or by |
---|
| 317 | using virtual functions in a class hierarchy. This proposal uses templates. |
---|
| 318 | Template parameters are usually some base type and values denoting fixed |
---|
| 319 | parameters for the functions f and o, e.g. a word size or modulus. |
---|
| 320 | |
---|
| 321 | <p>For virtual functions in a class hierarchy, the core language requires a |
---|
| 322 | (nearly) exact type match for a function in a derived classes overriding a |
---|
| 323 | function in a base class. This seems to be unnecessarily restrictive, |
---|
| 324 | because engines can sometimes benefit from using different integral base |
---|
| 325 | types. Also, with current compiler technology, virtual functions prevent |
---|
| 326 | inlining when a pointer to the base class is used to call a virtual |
---|
| 327 | function that is overridden in some derived class. In particular with |
---|
| 328 | applications such as simulations that sometimes use millions of |
---|
| 329 | pseudo-random numbers per second, losing significant amounts of performance |
---|
| 330 | due to missed inlining opportunities appears to not be acceptable.</p> |
---|
| 331 | |
---|
| 332 | <p>The CLHEP library bases all its engines on the abstract base class |
---|
| 333 | <code>HepRandomEngine</code>. Specific engines derive from this class and |
---|
| 334 | override its pure virtual functions. Similarly, all distributions are based |
---|
| 335 | on the base class <code>HepRandom</code>. Specific distributions derive |
---|
| 336 | from this class, override operator(), and provide a number of specific |
---|
| 337 | non-virtual functions.</p> |
---|
| 338 | |
---|
| 339 | <p>The GNU Scientific Library, while coded in C, adheres to the principles |
---|
| 340 | of object-structuring; all engines can be used with any of the |
---|
| 341 | distributions. The technical implementation is by mechanisms similar to |
---|
| 342 | virtual functions.</p> |
---|
| 343 | |
---|
| 344 | <h3>E. Parameterization and Initialization for Engines</h3>Engines usually |
---|
| 345 | have a "base" type which is used to store its internal state. Also, they |
---|
| 346 | usually have a choice of parameters. For example, a linear congruential |
---|
| 347 | engine is defined by x(i+1) = (a*x(i)+c) mod m, so f(x) = (a*x+c) mod m; |
---|
| 348 | the base type is "int" and parameters are a, c, and m. Finding parameters |
---|
| 349 | for a given function f that make for good randomness in the resulting |
---|
| 350 | engine's generated numbers x(i) requires extensive and specialized |
---|
| 351 | mathematical training and experience. In order to make good random numbers |
---|
| 352 | available to a large number of library users, this proposal not only |
---|
| 353 | defines generic random-number engines, but also provides a number of |
---|
| 354 | predefined well-known good parameterizations for those. Usually, there are |
---|
| 355 | only a few (less than five) well-known good parameterizations for each |
---|
| 356 | engine, so it appears feasible to provide these. |
---|
| 357 | |
---|
| 358 | <p>Since random-number engines are mathematically designed with computer |
---|
| 359 | implementation in mind, parameters are usually integers representable in a |
---|
| 360 | machine word, which usually coincides nicely with a C++ built-in type. The |
---|
| 361 | parameters could either be given as (compile-time) template arguments or as |
---|
| 362 | (run-time) constructor arguments.</p> |
---|
| 363 | |
---|
| 364 | <p>Providing parameters as template arguments allows for providing |
---|
| 365 | predefined parameterizations as simple "typedef"s. Furthermore, the |
---|
| 366 | parameters appear as integral constants, so the compiler can value-check |
---|
| 367 | the given constants against the engine's base type. Also, the library |
---|
| 368 | implementor can choose different implementations depending on the values of |
---|
| 369 | the parameters, without incurring any runtime overhead. For example, there |
---|
| 370 | is an efficient method to compute (a*x) mod m, provided that a certain |
---|
| 371 | magnitude of m relative to the underlying type is not exceeded. |
---|
| 372 | Additionally, the compiler's optimizer can benefit from the constants and |
---|
| 373 | potentially produce better code, for example by unrolling loops with fixed |
---|
| 374 | loop count.</p> |
---|
| 375 | |
---|
| 376 | <p>As an alternative, providing parameters as constructor arguments allows |
---|
| 377 | for more flexibility for the library user, for example when experimenting |
---|
| 378 | with several parameterizations. Predefined parameterizations can be |
---|
| 379 | provided by defining wrapper types which default the constructor |
---|
| 380 | parameters.</p> |
---|
| 381 | |
---|
| 382 | <p>Other libraries have hard-coded the parameters of their engines and do |
---|
| 383 | not allow the user any configuration of them at all. If the user wishes to |
---|
| 384 | change the parameters, he has to re-implement the engine's algorithm. In my |
---|
| 385 | opinion, this approach unnecessarily restricts re-use.</p> |
---|
| 386 | |
---|
| 387 | <p>Regarding initialization, this proposal chooses to provide |
---|
| 388 | "deterministic seeding" with the default constructor and the |
---|
| 389 | <code>seed</code> function without parameters: Two engines constructed |
---|
| 390 | using the default constructor will output the same sequence. In contrast, |
---|
| 391 | the CLHEP library's default constructed engines will take a fresh seed from |
---|
| 392 | a seed table for each instance. While this approach may be convenient for a |
---|
| 393 | certain group of users, it relies on global state and can easily be |
---|
| 394 | emulated by appropriately wrapping engines with deterministic seeding.</p> |
---|
| 395 | |
---|
| 396 | <p>In addition to the default constructor, all engines provide a |
---|
| 397 | constructor and <code>seed</code> function taking an iterator range |
---|
| 398 | [it1,it2) pointing to unsigned integral values. An engine initializes its |
---|
| 399 | state by successively consuming values from the iterator range, then |
---|
| 400 | returning the advanced iterator it1. This approach has the advantage that |
---|
| 401 | the user can completely exploit the large state of some engines for |
---|
| 402 | initialization. Also, it allows to initialize compound engines in a uniform |
---|
| 403 | manner. For example, a compound engine consisting of two simpler engines |
---|
| 404 | would initialize the first engine with its [it1,it2). The first engine |
---|
| 405 | returns a smaller iterator range that it has not consumed yet. This can be |
---|
| 406 | used to initialize the second engine.</p> |
---|
| 407 | |
---|
| 408 | <p>The iterator range [it1,it2) is specified to point to unsigned long |
---|
| 409 | values. There is no way to determine from a generic user program how the |
---|
| 410 | initialization values will be treated and what range of bits must be |
---|
| 411 | provided, except by enumerating all engines, e.g. in template |
---|
| 412 | specializations. The problem is that a given generator might have differing |
---|
| 413 | requirements on the values of the seed range even within one |
---|
| 414 | <code>seed</code> call.</p> |
---|
| 415 | |
---|
| 416 | <p>For example, imagine a</p> |
---|
| 417 | <pre> |
---|
| 418 | xor_combine<lagged_fibonacci<...>, mersenne_twister<...> > |
---|
| 419 | </pre>generator. For this, <code>seed(first, last)</code> will consume values |
---|
| 420 | as follows: First, seed the state of the <code>lagged_fibonacci</code> |
---|
| 421 | generator by consuming one item from [first, last) for each word of state. |
---|
| 422 | The values are reduced to (e.g.) 24 bits to fit the |
---|
| 423 | <code>lagged_fibonacci</code> state requirements. Then, seed the state of the |
---|
| 424 | <code>mersenne_twister</code> by consuming some number of items from the |
---|
| 425 | remaining [first, last). The values are reduced to 32 bits to fit the <code> |
---|
| 426 | mersenne_twister</code> state requirements. |
---|
| 427 | |
---|
| 428 | <p>How does a concise programming interface for those increasingly complex |
---|
| 429 | and varying requirements on [first, last) look like? I don't know, and I |
---|
| 430 | don't want to complicate the specification by inventing something |
---|
| 431 | complicated here.</p> |
---|
| 432 | |
---|
| 433 | <p>Thus, the specification says for each generator how it uses the seed |
---|
| 434 | values, and how many are consumed. Additional features are left to the |
---|
| 435 | user.</p> |
---|
| 436 | |
---|
| 437 | <p>In a way, this is similar to STL containers: It is intended that the |
---|
| 438 | user can exchange iterators to various containers in generic algorithms, |
---|
| 439 | but the container itself is not meant to be exchanged, i.e. having a |
---|
| 440 | Container template parameter is often not adequate. That is analogous to |
---|
| 441 | the random number case: The user can pass an engine around and use its |
---|
| 442 | <code>operator()</code> and <code>min</code> and <code>max</code> functions |
---|
| 443 | generically. However, the user can't generically query the engine |
---|
| 444 | attributes and parameters, simply because most are entirely different in |
---|
| 445 | semantics for each engine.</p> |
---|
| 446 | |
---|
| 447 | <p>The <code>seed(first, last)</code> interface can serve two purposes:</p> |
---|
| 448 | |
---|
| 449 | <ol> |
---|
| 450 | <li>In a generic context, the user can pass several integer values >= |
---|
| 451 | 1 for seeding. It is unlikely that the user explores the full state space |
---|
| 452 | with the seeds she provides, but she can be reasonably sure that her |
---|
| 453 | seeds aren't entirely incorrect. (There is no formal guarantee for that, |
---|
| 454 | except that the ability to provide bad seeds usually means the |
---|
| 455 | parameterization of the engine is bad, e.g. a non-prime modulus for a |
---|
| 456 | linear congruential engine.) For example, if the user wants a |
---|
| 457 | <code>seed(uint32_t)</code> on top of <code>seed(first, last)</code>, one |
---|
| 458 | option is to use a <code>linear_congruential</code> generator that |
---|
| 459 | produces the values required for <code>seed(first, last)</code>. When the |
---|
| 460 | user defines the iterator type for <code>first</code> and |
---|
| 461 | <code>last</code> so that it encapsulates the |
---|
| 462 | <code>linear_congruential</code> engine in <code>operator++</code>, the |
---|
| 463 | user doesn't even need to know beforehand how many values |
---|
| 464 | <code>seed(first, last)</code> will need.</li> |
---|
| 465 | |
---|
| 466 | <li>If the user is in a non-generic context, he knows the specific |
---|
| 467 | template type of the engine (probably not the template value-based |
---|
| 468 | parameterization, though). The precise specification for |
---|
| 469 | <code>seed(first, last)</code> allows to know what values need to be |
---|
| 470 | passed in so that a specific initial state is attained, for example to |
---|
| 471 | compare one implementation of the engine with another one that uses |
---|
| 472 | different seeding.</li> |
---|
| 473 | |
---|
| 474 | <li>If the user requires both, he needs to inject knowledge into (1) so |
---|
| 475 | that he is in the position of (2). One way to inject the knowledge is to |
---|
| 476 | use (partial) template specialization to add the knowledge. The specific |
---|
| 477 | parameterization of some engine can then be obtained by querying the data |
---|
| 478 | members of the engines.</li> |
---|
| 479 | </ol> |
---|
| 480 | |
---|
| 481 | <p>I haven't seen the iterator-based approach to engine initialization in |
---|
| 482 | other libraries; most initialization approaches rely on a either a single |
---|
| 483 | value or on per-engine specific approaches to initialization.</p> |
---|
| 484 | |
---|
| 485 | <p>An alternative approach is to pass a zero-argument function object |
---|
| 486 | ("generator") for seeding. It is trivial to implement a generator from a |
---|
| 487 | given iterator range, but it is more complicated to implement an iterator |
---|
| 488 | range from a generator. Also, the exception object that is specified to be |
---|
| 489 | thrown when the iterator range is exhausted could be configured in a |
---|
| 490 | user-provided iterator to generator mapping. With this approach, some |
---|
| 491 | engines would have three one-argument constructors: One taking a single |
---|
| 492 | integer for seeding, one taking a (reference?) to a (templated) generator, |
---|
| 493 | and the copy constructor. It appears that the opportunities for ambiguities |
---|
| 494 | or choosing the wrong overload are too confusing to the unsuspecting |
---|
| 495 | user.</p> |
---|
| 496 | |
---|
| 497 | <h3>F. Parameterization and Initialization for Distributions</h3>The |
---|
| 498 | distributions specified in this proposal have template parameters that |
---|
| 499 | indicate the output data type (e.g. <code>float</code>, |
---|
| 500 | <code>double</code>, <code>long double</code>) that the user desires. |
---|
| 501 | |
---|
| 502 | <p>The probability density functions of distributions usually have |
---|
| 503 | parameters. These are mapped to constructor parameters, to be set at |
---|
| 504 | runtime by the library user according to her requirements. The parameters |
---|
| 505 | for a distribution object cannot change after its construction. When |
---|
| 506 | constructing the distribution, this allows to pre-compute some data |
---|
| 507 | according to the parameters given without risk of inadvertently |
---|
| 508 | invalidating them later.</p> |
---|
| 509 | |
---|
| 510 | <p>Distributions may implement <code>operator()(T x)</code>, for arbitrary |
---|
| 511 | type <code>T</code>, to meet special needs, for example a "one-shot" mode |
---|
| 512 | where each invocation uses different distribution parameters.</p> |
---|
| 513 | |
---|
| 514 | <h3>G. Properties as Traits vs. In-Class Constants</h3>Users might wish to |
---|
| 515 | query compile-time properties of the engines and distributions, e.g. their |
---|
| 516 | base types, constant parameters, etc. This is similar to querying the |
---|
| 517 | properties of the built-in types such as <code>double</code> using |
---|
| 518 | <code>std::numeric_limits<></code>. However, engines and |
---|
| 519 | distributions cannot be simple types, so it does not appear to be necessary |
---|
| 520 | to separate the properties into separate traits classes. Instead, |
---|
| 521 | compile-time properties are given as members types and static member |
---|
| 522 | constants. |
---|
| 523 | |
---|
| 524 | <h3>H. Which Engines to Include</h3>There is a multitude of pseudo-random |
---|
| 525 | number engines available in both literature and code. Some engines, such as |
---|
| 526 | Mersenne Twister, have an independent algorithm ("base engine"). Others |
---|
| 527 | change the values or order of output of other engines to improve |
---|
| 528 | randomness, for example Knuth's "Algorithm B" ("compound engine"). The |
---|
| 529 | template mechanism allows easy combination of base and compound engines. |
---|
| 530 | |
---|
| 531 | <p>Engines may be categorized according to the following dimensions.</p> |
---|
| 532 | |
---|
| 533 | <ul> |
---|
| 534 | <li>integers or floating-point numbers produced (Some engines produce |
---|
| 535 | uniformly distributed integers in the range [min,max], however, most |
---|
| 536 | distribution functions expect uniformly distributed floating-point |
---|
| 537 | numbers in the range [0,1) as the input sequence. The obvious conversion |
---|
| 538 | requires a relatively costly integer to floating-point conversion plus a |
---|
| 539 | floating-point multiplication by (max-min+1)<sup>-1</sup> for each random |
---|
| 540 | number used. To save the multiplication, some engines can directly |
---|
| 541 | produce floating-point numbers in the range [0,1) by maintaining the |
---|
| 542 | state x(i) in an appropriately normalized form, given a sufficiently good |
---|
| 543 | implementation of basic floating-point operations (e.g. IEEE 754).</li> |
---|
| 544 | |
---|
| 545 | <li>quality of random numbers produced (What is the cycle length? Does |
---|
| 546 | the engine pass all relevant statistical tests? Up to what dimension are |
---|
| 547 | numbers equidistributed?)</li> |
---|
| 548 | |
---|
| 549 | <li>speed of generation (How many and what kind of operations have to be |
---|
| 550 | performed to produce one random number, on average?)</li> |
---|
| 551 | |
---|
| 552 | <li>size of state (How may machine words of storage are required to hold |
---|
| 553 | the state x(i) of the random engine?)</li> |
---|
| 554 | |
---|
| 555 | <li>option for independent subsequences (Is it possible to move from x(i) |
---|
| 556 | to x(i+k) with at most O(log(k)) steps? This allows to efficiently use |
---|
| 557 | subsequences x(0)...x(k-1), x(k)...x(2k-1), ..., x(jk)...x((j+1)k-1), |
---|
| 558 | ..., for example for parallel computation, where each of the m processors |
---|
| 559 | gets assigned the (independent) subsequence starting at x(jk) (0 <= k |
---|
| 560 | < m).)</li> |
---|
| 561 | </ul>According to the criteria above, the engines given below were chosen. |
---|
| 562 | The quality and size indications were completed according to best known |
---|
| 563 | parameterizations. Other parameterizations usually yield poorer quality |
---|
| 564 | and/or less size. |
---|
| 565 | |
---|
| 566 | <table border="1" summary=""> |
---|
| 567 | <tr> |
---|
| 568 | <th>engine</th> |
---|
| 569 | |
---|
| 570 | <th>int / float</th> |
---|
| 571 | |
---|
| 572 | <th>quality</th> |
---|
| 573 | |
---|
| 574 | <th>speed</th> |
---|
| 575 | |
---|
| 576 | <th>size of state</th> |
---|
| 577 | |
---|
| 578 | <th>subsequences</th> |
---|
| 579 | |
---|
| 580 | <th>comments</th> |
---|
| 581 | </tr> |
---|
| 582 | |
---|
| 583 | <tr> |
---|
| 584 | <td>linear_congruential</td> |
---|
| 585 | |
---|
| 586 | <td>int</td> |
---|
| 587 | |
---|
| 588 | <td>medium</td> |
---|
| 589 | |
---|
| 590 | <td>medium</td> |
---|
| 591 | |
---|
| 592 | <td>1 word</td> |
---|
| 593 | |
---|
| 594 | <td>yes</td> |
---|
| 595 | |
---|
| 596 | <td>cycle length is limited to the maximum value representable in one |
---|
| 597 | machine word, passes most statisticial tests with chosen |
---|
| 598 | parameters.</td> |
---|
| 599 | </tr> |
---|
| 600 | |
---|
| 601 | <tr> |
---|
| 602 | <td>mersenne_twister</td> |
---|
| 603 | |
---|
| 604 | <td>int</td> |
---|
| 605 | |
---|
| 606 | <td>good</td> |
---|
| 607 | |
---|
| 608 | <td>fast</td> |
---|
| 609 | |
---|
| 610 | <td>624 words</td> |
---|
| 611 | |
---|
| 612 | <td>no</td> |
---|
| 613 | |
---|
| 614 | <td>long cycles, passes all statistical tests, good equidistribution in |
---|
| 615 | high dimensions</td> |
---|
| 616 | </tr> |
---|
| 617 | |
---|
| 618 | <tr> |
---|
| 619 | <td>subtract_with_carry</td> |
---|
| 620 | |
---|
| 621 | <td>both</td> |
---|
| 622 | |
---|
| 623 | <td>medium</td> |
---|
| 624 | |
---|
| 625 | <td>fast</td> |
---|
| 626 | |
---|
| 627 | <td>25 words</td> |
---|
| 628 | |
---|
| 629 | <td>no</td> |
---|
| 630 | |
---|
| 631 | <td>very long cycles possible, fails some statistical tests. Can be |
---|
| 632 | improved with the discard_block compound engine.</td> |
---|
| 633 | </tr> |
---|
| 634 | |
---|
| 635 | <tr> |
---|
| 636 | <td>discard_block</td> |
---|
| 637 | |
---|
| 638 | <td>both</td> |
---|
| 639 | |
---|
| 640 | <td>good</td> |
---|
| 641 | |
---|
| 642 | <td>slow</td> |
---|
| 643 | |
---|
| 644 | <td>base engine + 1 word</td> |
---|
| 645 | |
---|
| 646 | <td>no</td> |
---|
| 647 | |
---|
| 648 | <td>compound engine that removes correlation provably by throwing away |
---|
| 649 | significant chunks of the base engine's sequence, the resulting speed |
---|
| 650 | is reduced to 10% to 3% of the base engine's.</td> |
---|
| 651 | </tr> |
---|
| 652 | |
---|
| 653 | <tr> |
---|
| 654 | <td>xor_combine</td> |
---|
| 655 | |
---|
| 656 | <td>int</td> |
---|
| 657 | |
---|
| 658 | <td>good</td> |
---|
| 659 | |
---|
| 660 | <td>fast</td> |
---|
| 661 | |
---|
| 662 | <td>base engines</td> |
---|
| 663 | |
---|
| 664 | <td>yes, if one of the base engines</td> |
---|
| 665 | |
---|
| 666 | <td>compound engine that XOR-combines the sequences of two base |
---|
| 667 | engines</td> |
---|
| 668 | </tr> |
---|
| 669 | </table> |
---|
| 670 | |
---|
| 671 | <p>Some engines were considered for inclusion, but left out for the |
---|
| 672 | following reasons:</p> |
---|
| 673 | |
---|
| 674 | <table border="1" summary=""> |
---|
| 675 | <tr> |
---|
| 676 | <th>engine</th> |
---|
| 677 | |
---|
| 678 | <th>int / float</th> |
---|
| 679 | |
---|
| 680 | <th>quality</th> |
---|
| 681 | |
---|
| 682 | <th>speed</th> |
---|
| 683 | |
---|
| 684 | <th>size of state</th> |
---|
| 685 | |
---|
| 686 | <th>subsequences</th> |
---|
| 687 | |
---|
| 688 | <th>comments</th> |
---|
| 689 | </tr> |
---|
| 690 | |
---|
| 691 | <tr> |
---|
| 692 | <td>shuffle_output</td> |
---|
| 693 | |
---|
| 694 | <td>int</td> |
---|
| 695 | |
---|
| 696 | <td>good</td> |
---|
| 697 | |
---|
| 698 | <td>fast</td> |
---|
| 699 | |
---|
| 700 | <td>base engine + 100 words</td> |
---|
| 701 | |
---|
| 702 | <td>no</td> |
---|
| 703 | |
---|
| 704 | <td>compound engine that reorders the base engine's output, little |
---|
| 705 | overhead for generation (one multiplication)</td> |
---|
| 706 | </tr> |
---|
| 707 | |
---|
| 708 | <tr> |
---|
| 709 | <td>lagged_fibonacci</td> |
---|
| 710 | |
---|
| 711 | <td>both</td> |
---|
| 712 | |
---|
| 713 | <td>medium</td> |
---|
| 714 | |
---|
| 715 | <td>fast</td> |
---|
| 716 | |
---|
| 717 | <td>up to 80,000 words</td> |
---|
| 718 | |
---|
| 719 | <td>no</td> |
---|
| 720 | |
---|
| 721 | <td>very long cycles possible, fails birthday spacings test. Same |
---|
| 722 | principle of generation as <code>subtract_with_carry</code>, i.e. x(i) |
---|
| 723 | = x(i-s) (*) x(i-r), where (*) is either of +, -, xor with or without |
---|
| 724 | carry.</td> |
---|
| 725 | </tr> |
---|
| 726 | |
---|
| 727 | <tr> |
---|
| 728 | <td>inversive_congruential (Hellekalek 1995)</td> |
---|
| 729 | |
---|
| 730 | <td>int</td> |
---|
| 731 | |
---|
| 732 | <td>good</td> |
---|
| 733 | |
---|
| 734 | <td>slow</td> |
---|
| 735 | |
---|
| 736 | <td>1 word</td> |
---|
| 737 | |
---|
| 738 | <td>no</td> |
---|
| 739 | |
---|
| 740 | <td>x(i+1) = a x(i)<sup>-1</sup> + c. Good equidistribution in several |
---|
| 741 | dimensions. Provides no apparent advantage compared to ranlux; the |
---|
| 742 | latter can produce floating-point numbers directly.</td> |
---|
| 743 | </tr> |
---|
| 744 | |
---|
| 745 | <tr> |
---|
| 746 | <td>additive_combine (L'Ecuyer 1988)</td> |
---|
| 747 | |
---|
| 748 | <td>int</td> |
---|
| 749 | |
---|
| 750 | <td>good</td> |
---|
| 751 | |
---|
| 752 | <td>medium</td> |
---|
| 753 | |
---|
| 754 | <td>2 words</td> |
---|
| 755 | |
---|
| 756 | <td>yes</td> |
---|
| 757 | |
---|
| 758 | <td>Combines two linear congruential generators. Same principle of |
---|
| 759 | combination as <code>xor_combine</code>, i.e. z(i) = x(i) (*) y(i), |
---|
| 760 | where (*) is one of +, -, xor.</td> |
---|
| 761 | </tr> |
---|
| 762 | |
---|
| 763 | <tr> |
---|
| 764 | <td>R250 (Kirkpatrick and Stoll)</td> |
---|
| 765 | |
---|
| 766 | <td>int</td> |
---|
| 767 | |
---|
| 768 | <td>bad</td> |
---|
| 769 | |
---|
| 770 | <td>fast</td> |
---|
| 771 | |
---|
| 772 | <td>~ 20 words</td> |
---|
| 773 | |
---|
| 774 | <td>no</td> |
---|
| 775 | |
---|
| 776 | <td>General Feedback Shift Register with two taps: Easily exploitable |
---|
| 777 | correlation.</td> |
---|
| 778 | </tr> |
---|
| 779 | |
---|
| 780 | <tr> |
---|
| 781 | <td>linear_feedback_shift</td> |
---|
| 782 | |
---|
| 783 | <td>int</td> |
---|
| 784 | |
---|
| 785 | <td>medium</td> |
---|
| 786 | |
---|
| 787 | <td>fast</td> |
---|
| 788 | |
---|
| 789 | <td>1 word</td> |
---|
| 790 | |
---|
| 791 | <td>no</td> |
---|
| 792 | |
---|
| 793 | <td>cycle length is limited to the maximum value representable in one |
---|
| 794 | machine word, fails some statistical tests, can be improved with the |
---|
| 795 | xor_combine compound engine.</td> |
---|
| 796 | </tr> |
---|
| 797 | </table> |
---|
| 798 | |
---|
| 799 | <p>The GNU Scientific Library and Swarm have additional engine that are not |
---|
| 800 | mentioned in the table below.</p> |
---|
| 801 | |
---|
| 802 | <table border="1" summary=""> |
---|
| 803 | <tr> |
---|
| 804 | <th>Engine</th> |
---|
| 805 | |
---|
| 806 | <th>this proposal</th> |
---|
| 807 | |
---|
| 808 | <th>CLHEP</th> |
---|
| 809 | |
---|
| 810 | <th>crng</th> |
---|
| 811 | |
---|
| 812 | <th>GNU Scientific Library</th> |
---|
| 813 | |
---|
| 814 | <th>Swarm</th> |
---|
| 815 | |
---|
| 816 | <th>Numerical Recipes</th> |
---|
| 817 | |
---|
| 818 | <th>Knuth</th> |
---|
| 819 | </tr> |
---|
| 820 | |
---|
| 821 | <tr> |
---|
| 822 | <td>LCG(2<sup>31</sup>-1, 16807)</td> |
---|
| 823 | |
---|
| 824 | <td>minstd_rand0</td> |
---|
| 825 | |
---|
| 826 | <td>-</td> |
---|
| 827 | |
---|
| 828 | <td>ParkMiller</td> |
---|
| 829 | |
---|
| 830 | <td>ran0, minstd</td> |
---|
| 831 | |
---|
| 832 | <td>-</td> |
---|
| 833 | |
---|
| 834 | <td>ran0</td> |
---|
| 835 | |
---|
| 836 | <td>p106, table 1, line 19</td> |
---|
| 837 | </tr> |
---|
| 838 | |
---|
| 839 | <tr> |
---|
| 840 | <td>LCG(2<sup>32</sup>, a=1664525, c=1013904223)</td> |
---|
| 841 | |
---|
| 842 | <td>linear_congruential< ..., 1664525, 1013904223, (1 << 32) |
---|
| 843 | ></td> |
---|
| 844 | |
---|
| 845 | <td>-</td> |
---|
| 846 | |
---|
| 847 | <td>-</td> |
---|
| 848 | |
---|
| 849 | <td>-</td> |
---|
| 850 | |
---|
| 851 | <td>LCG1gen</td> |
---|
| 852 | |
---|
| 853 | <td>-</td> |
---|
| 854 | |
---|
| 855 | <td>p106, table 1, line 16</td> |
---|
| 856 | </tr> |
---|
| 857 | |
---|
| 858 | <tr> |
---|
| 859 | <td>LCG1 + LCG2 + LCG3</td> |
---|
| 860 | |
---|
| 861 | <td>-</td> |
---|
| 862 | |
---|
| 863 | <td>-</td> |
---|
| 864 | |
---|
| 865 | <td>WichmannHill</td> |
---|
| 866 | |
---|
| 867 | <td>-</td> |
---|
| 868 | |
---|
| 869 | <td>-</td> |
---|
| 870 | |
---|
| 871 | <td>-</td> |
---|
| 872 | |
---|
| 873 | <td>-</td> |
---|
| 874 | </tr> |
---|
| 875 | |
---|
| 876 | <tr> |
---|
| 877 | <td>(LCG1 - LCG2 + LCG3 - LCG4) mod m0</td> |
---|
| 878 | |
---|
| 879 | <td>-</td> |
---|
| 880 | |
---|
| 881 | <td>-</td> |
---|
| 882 | |
---|
| 883 | <td>-</td> |
---|
| 884 | |
---|
| 885 | <td>-</td> |
---|
| 886 | |
---|
| 887 | <td>C4LCGXgen</td> |
---|
| 888 | |
---|
| 889 | <td>-</td> |
---|
| 890 | |
---|
| 891 | <td>-</td> |
---|
| 892 | </tr> |
---|
| 893 | |
---|
| 894 | <tr> |
---|
| 895 | <td>LCG(2<sup>31</sup>-1, 16807) with Bays/Durham shuffle</td> |
---|
| 896 | |
---|
| 897 | <td>shuffle_output<minstd_rand0, 32> (shuffle_output not in this |
---|
| 898 | proposal)</td> |
---|
| 899 | |
---|
| 900 | <td>-</td> |
---|
| 901 | |
---|
| 902 | <td>-</td> |
---|
| 903 | |
---|
| 904 | <td>ran1</td> |
---|
| 905 | |
---|
| 906 | <td>PMMLCG1gen</td> |
---|
| 907 | |
---|
| 908 | <td>ran1</td> |
---|
| 909 | |
---|
| 910 | <td>Algorithm "B"</td> |
---|
| 911 | </tr> |
---|
| 912 | |
---|
| 913 | <tr> |
---|
| 914 | <td>(LCG(2<sup>31</sup>-85, 40014) + LCG(2<sup>31</sup>-249, 40692)) |
---|
| 915 | mod 2<sup>31</sup>-85</td> |
---|
| 916 | |
---|
| 917 | <td>ecuyer1988 (additive_combine not in this proposal)</td> |
---|
| 918 | |
---|
| 919 | <td>Ranecu</td> |
---|
| 920 | |
---|
| 921 | <td>LEcuyer</td> |
---|
| 922 | |
---|
| 923 | <td>-</td> |
---|
| 924 | |
---|
| 925 | <td>C2LCGXgen</td> |
---|
| 926 | |
---|
| 927 | <td>-</td> |
---|
| 928 | |
---|
| 929 | <td>-</td> |
---|
| 930 | </tr> |
---|
| 931 | |
---|
| 932 | <tr> |
---|
| 933 | <td>(LCG(2<sup>31</sup>-85, 40014) with Bays/Durham shuffle + |
---|
| 934 | LCG(2<sup>31</sup>-249, 40692)) mod 2<sup>31</sup>-85</td> |
---|
| 935 | |
---|
| 936 | <td>additive_combine< shuffle_output<<br> |
---|
| 937 | linear_congruential<int, 40014, 0, 2147483563>, 32>,<br> |
---|
| 938 | linear_congruential<int, 40692, 0, 2147483399> > |
---|
| 939 | (additive_combine and shuffle_output not in this proposal)</td> |
---|
| 940 | |
---|
| 941 | <td>-</td> |
---|
| 942 | |
---|
| 943 | <td>-</td> |
---|
| 944 | |
---|
| 945 | <td>ran2</td> |
---|
| 946 | |
---|
| 947 | <td>-</td> |
---|
| 948 | |
---|
| 949 | <td>ran2</td> |
---|
| 950 | |
---|
| 951 | <td>-</td> |
---|
| 952 | </tr> |
---|
| 953 | |
---|
| 954 | <tr> |
---|
| 955 | <td>X(i) = (X(i-55) - X(i-33)) mod 10<sup>9</sup></td> |
---|
| 956 | |
---|
| 957 | <td>-</td> |
---|
| 958 | |
---|
| 959 | <td>-</td> |
---|
| 960 | |
---|
| 961 | <td>-</td> |
---|
| 962 | |
---|
| 963 | <td>ran3</td> |
---|
| 964 | |
---|
| 965 | <td>~SCGgen</td> |
---|
| 966 | |
---|
| 967 | <td>ran3</td> |
---|
| 968 | |
---|
| 969 | <td>-</td> |
---|
| 970 | </tr> |
---|
| 971 | |
---|
| 972 | <tr> |
---|
| 973 | <td>X(i) = (X(i-100) - X(i-37)) mod 2<sup>30</sup></td> |
---|
| 974 | |
---|
| 975 | <td>-</td> |
---|
| 976 | |
---|
| 977 | <td>-</td> |
---|
| 978 | |
---|
| 979 | <td>-</td> |
---|
| 980 | |
---|
| 981 | <td>-</td> |
---|
| 982 | |
---|
| 983 | <td>-</td> |
---|
| 984 | |
---|
| 985 | <td>-</td> |
---|
| 986 | |
---|
| 987 | <td>ran_array</td> |
---|
| 988 | </tr> |
---|
| 989 | |
---|
| 990 | <tr> |
---|
| 991 | <td>X(i) = (X(i-55) + X(i-24)) mod 2<sup>32</sup></td> |
---|
| 992 | |
---|
| 993 | <td>lagged_fibonacci< ..., 32, 55, 24, ...> (lagged_fibonacci not |
---|
| 994 | in this proposal)</td> |
---|
| 995 | |
---|
| 996 | <td>-</td> |
---|
| 997 | |
---|
| 998 | <td>-</td> |
---|
| 999 | |
---|
| 1000 | <td>-</td> |
---|
| 1001 | |
---|
| 1002 | <td>ACGgen</td> |
---|
| 1003 | |
---|
| 1004 | <td>-</td> |
---|
| 1005 | |
---|
| 1006 | <td>-</td> |
---|
| 1007 | </tr> |
---|
| 1008 | |
---|
| 1009 | <tr> |
---|
| 1010 | <td>DEShash(i,j)</td> |
---|
| 1011 | |
---|
| 1012 | <td>-</td> |
---|
| 1013 | |
---|
| 1014 | <td>-</td> |
---|
| 1015 | |
---|
| 1016 | <td>-</td> |
---|
| 1017 | |
---|
| 1018 | <td>-</td> |
---|
| 1019 | |
---|
| 1020 | <td>-</td> |
---|
| 1021 | |
---|
| 1022 | <td>ran4</td> |
---|
| 1023 | |
---|
| 1024 | <td>-</td> |
---|
| 1025 | </tr> |
---|
| 1026 | |
---|
| 1027 | <tr> |
---|
| 1028 | <td>MT</td> |
---|
| 1029 | |
---|
| 1030 | <td>mt19937</td> |
---|
| 1031 | |
---|
| 1032 | <td>MTwistEngine</td> |
---|
| 1033 | |
---|
| 1034 | <td>MT19937</td> |
---|
| 1035 | |
---|
| 1036 | <td>mt19937</td> |
---|
| 1037 | |
---|
| 1038 | <td>MT19937gen</td> |
---|
| 1039 | |
---|
| 1040 | <td>-</td> |
---|
| 1041 | |
---|
| 1042 | <td>-</td> |
---|
| 1043 | </tr> |
---|
| 1044 | |
---|
| 1045 | <tr> |
---|
| 1046 | <td>X(i) = (X(i-37) - X(i-24) - carry) mod 2<sup>32</sup></td> |
---|
| 1047 | |
---|
| 1048 | <td>subtract_with_carry< ..., (1<<32), 37, 24, ...></td> |
---|
| 1049 | |
---|
| 1050 | <td>-</td> |
---|
| 1051 | |
---|
| 1052 | <td>-</td> |
---|
| 1053 | |
---|
| 1054 | <td>-</td> |
---|
| 1055 | |
---|
| 1056 | <td>SWB1gen</td> |
---|
| 1057 | |
---|
| 1058 | <td>-</td> |
---|
| 1059 | |
---|
| 1060 | <td>-</td> |
---|
| 1061 | </tr> |
---|
| 1062 | |
---|
| 1063 | <tr> |
---|
| 1064 | <td>X(i) = (X(i-43) - X(i-22) - carry) mod 2<sup>32</sup>-5</td> |
---|
| 1065 | |
---|
| 1066 | <td>subtract_with_carry< ..., (1<<32)-5, 43, 22, ...></td> |
---|
| 1067 | |
---|
| 1068 | <td>-</td> |
---|
| 1069 | |
---|
| 1070 | <td>-</td> |
---|
| 1071 | |
---|
| 1072 | <td>-</td> |
---|
| 1073 | |
---|
| 1074 | <td>PSWBgen</td> |
---|
| 1075 | |
---|
| 1076 | <td>-</td> |
---|
| 1077 | |
---|
| 1078 | <td>-</td> |
---|
| 1079 | </tr> |
---|
| 1080 | |
---|
| 1081 | <tr> |
---|
| 1082 | <td>RCARRY with block discard by Lüscher</td> |
---|
| 1083 | |
---|
| 1084 | <td>discard_block< subtract_with_carry<...>, ...></td> |
---|
| 1085 | |
---|
| 1086 | <td>RanluxEngine, Ranlux64Engine</td> |
---|
| 1087 | |
---|
| 1088 | <td>Ranlux</td> |
---|
| 1089 | |
---|
| 1090 | <td>ranlx*</td> |
---|
| 1091 | |
---|
| 1092 | <td>-</td> |
---|
| 1093 | |
---|
| 1094 | <td>-</td> |
---|
| 1095 | |
---|
| 1096 | <td>-</td> |
---|
| 1097 | </tr> |
---|
| 1098 | |
---|
| 1099 | <tr> |
---|
| 1100 | <td>Hurd</td> |
---|
| 1101 | |
---|
| 1102 | <td>-</td> |
---|
| 1103 | |
---|
| 1104 | <td>Hurd160, Hurd288</td> |
---|
| 1105 | |
---|
| 1106 | <td>-</td> |
---|
| 1107 | |
---|
| 1108 | <td>-</td> |
---|
| 1109 | |
---|
| 1110 | <td>-</td> |
---|
| 1111 | |
---|
| 1112 | <td>-</td> |
---|
| 1113 | |
---|
| 1114 | <td>-</td> |
---|
| 1115 | </tr> |
---|
| 1116 | |
---|
| 1117 | <tr> |
---|
| 1118 | <td>physical model by Ranshi</td> |
---|
| 1119 | |
---|
| 1120 | <td>-</td> |
---|
| 1121 | |
---|
| 1122 | <td>Ranshi</td> |
---|
| 1123 | |
---|
| 1124 | <td>-</td> |
---|
| 1125 | |
---|
| 1126 | <td>-</td> |
---|
| 1127 | |
---|
| 1128 | <td>-</td> |
---|
| 1129 | |
---|
| 1130 | <td>-</td> |
---|
| 1131 | |
---|
| 1132 | <td>-</td> |
---|
| 1133 | </tr> |
---|
| 1134 | |
---|
| 1135 | <tr> |
---|
| 1136 | <td>return predefined data</td> |
---|
| 1137 | |
---|
| 1138 | <td>-</td> |
---|
| 1139 | |
---|
| 1140 | <td>NonRandom</td> |
---|
| 1141 | |
---|
| 1142 | <td>-</td> |
---|
| 1143 | |
---|
| 1144 | <td>-</td> |
---|
| 1145 | |
---|
| 1146 | <td>-</td> |
---|
| 1147 | |
---|
| 1148 | <td>-</td> |
---|
| 1149 | |
---|
| 1150 | <td>-</td> |
---|
| 1151 | </tr> |
---|
| 1152 | |
---|
| 1153 | <tr> |
---|
| 1154 | <td>RANMAR: z(i) = (z(i-97) - z(i-33)) mod 2<sup>24</sup>; y(i+1) = |
---|
| 1155 | (y(i)-c) mod 2<sup>24</sup>-3; X(i) = (z(i) - y(i)) mod |
---|
| 1156 | 2<sup>24</sup></td> |
---|
| 1157 | |
---|
| 1158 | <td>additive_combine< lagged_fibonacci< (1<<24), 97, 33, |
---|
| 1159 | ... >, linear_congruential< (1<<24)-3, 1, c, ...> |
---|
| 1160 | (additive_combine and lagged_fibonacci not in this proposal)</td> |
---|
| 1161 | |
---|
| 1162 | <td>JamesRandom</td> |
---|
| 1163 | |
---|
| 1164 | <td>-</td> |
---|
| 1165 | |
---|
| 1166 | <td>ranmar</td> |
---|
| 1167 | |
---|
| 1168 | <td>-</td> |
---|
| 1169 | |
---|
| 1170 | <td>-</td> |
---|
| 1171 | |
---|
| 1172 | <td>-</td> |
---|
| 1173 | </tr> |
---|
| 1174 | |
---|
| 1175 | <tr> |
---|
| 1176 | <td>Taus88</td> |
---|
| 1177 | |
---|
| 1178 | <td>taus88 = xor_combine ...</td> |
---|
| 1179 | |
---|
| 1180 | <td>-</td> |
---|
| 1181 | |
---|
| 1182 | <td>Taus88</td> |
---|
| 1183 | |
---|
| 1184 | <td>taus, taus2</td> |
---|
| 1185 | |
---|
| 1186 | <td>-</td> |
---|
| 1187 | |
---|
| 1188 | <td>-</td> |
---|
| 1189 | |
---|
| 1190 | <td>-</td> |
---|
| 1191 | </tr> |
---|
| 1192 | |
---|
| 1193 | <tr> |
---|
| 1194 | <td>Taus60</td> |
---|
| 1195 | |
---|
| 1196 | <td>xor_combine< linear_feedback_shift< 31, 13, 12 >, 0, |
---|
| 1197 | linear_feedback_shift< 29, 2, 4 >, 2, 0> |
---|
| 1198 | (linear_feedback_shift not in this proposal)</td> |
---|
| 1199 | |
---|
| 1200 | <td>-</td> |
---|
| 1201 | |
---|
| 1202 | <td>-</td> |
---|
| 1203 | |
---|
| 1204 | <td>-</td> |
---|
| 1205 | |
---|
| 1206 | <td>C2TAUSgen</td> |
---|
| 1207 | |
---|
| 1208 | <td>-</td> |
---|
| 1209 | |
---|
| 1210 | <td>-</td> |
---|
| 1211 | </tr> |
---|
| 1212 | |
---|
| 1213 | <tr> |
---|
| 1214 | <td>GFSR, 4-tap</td> |
---|
| 1215 | |
---|
| 1216 | <td>-</td> |
---|
| 1217 | |
---|
| 1218 | <td>-</td> |
---|
| 1219 | |
---|
| 1220 | <td>-</td> |
---|
| 1221 | |
---|
| 1222 | <td>gfsr4</td> |
---|
| 1223 | |
---|
| 1224 | <td>-</td> |
---|
| 1225 | |
---|
| 1226 | <td>-</td> |
---|
| 1227 | |
---|
| 1228 | <td>-</td> |
---|
| 1229 | </tr> |
---|
| 1230 | |
---|
| 1231 | <tr> |
---|
| 1232 | <td>MRG32k3a</td> |
---|
| 1233 | |
---|
| 1234 | <td>-</td> |
---|
| 1235 | |
---|
| 1236 | <td>-</td> |
---|
| 1237 | |
---|
| 1238 | <td>MRG32k3a</td> |
---|
| 1239 | |
---|
| 1240 | <td>-</td> |
---|
| 1241 | |
---|
| 1242 | <td>-</td> |
---|
| 1243 | |
---|
| 1244 | <td>-</td> |
---|
| 1245 | |
---|
| 1246 | <td>-</td> |
---|
| 1247 | </tr> |
---|
| 1248 | </table> |
---|
| 1249 | |
---|
| 1250 | <h3>I. Which Distributions to Include</h3>The following distributions were |
---|
| 1251 | chosen due to their relatively widespread use: |
---|
| 1252 | |
---|
| 1253 | <ul> |
---|
| 1254 | <li>Integer uniform</li> |
---|
| 1255 | |
---|
| 1256 | <li>Floating-point uniform</li> |
---|
| 1257 | |
---|
| 1258 | <li>Exponential</li> |
---|
| 1259 | |
---|
| 1260 | <li>Normal</li> |
---|
| 1261 | |
---|
| 1262 | <li>Gamma</li> |
---|
| 1263 | |
---|
| 1264 | <li>Poisson</li> |
---|
| 1265 | |
---|
| 1266 | <li>Binomial</li> |
---|
| 1267 | |
---|
| 1268 | <li>Geometric</li> |
---|
| 1269 | |
---|
| 1270 | <li>Bernoulli</li> |
---|
| 1271 | </ul>The GNU Scientific Library has a multitude of additional distributions |
---|
| 1272 | that are not mentioned in the table below. |
---|
| 1273 | |
---|
| 1274 | <table border="1" summary=""> |
---|
| 1275 | <tr> |
---|
| 1276 | <th>Distribution</th> |
---|
| 1277 | |
---|
| 1278 | <th>this proposal</th> |
---|
| 1279 | |
---|
| 1280 | <th>CLHEP</th> |
---|
| 1281 | |
---|
| 1282 | <th>crng</th> |
---|
| 1283 | |
---|
| 1284 | <th>GNU Scientific Library</th> |
---|
| 1285 | |
---|
| 1286 | <th>Swarm</th> |
---|
| 1287 | |
---|
| 1288 | <th>Numerical Recipes</th> |
---|
| 1289 | |
---|
| 1290 | <th>Knuth</th> |
---|
| 1291 | </tr> |
---|
| 1292 | |
---|
| 1293 | <tr> |
---|
| 1294 | <td>uniform (int)</td> |
---|
| 1295 | |
---|
| 1296 | <td>uniform_int</td> |
---|
| 1297 | |
---|
| 1298 | <td>-</td> |
---|
| 1299 | |
---|
| 1300 | <td>-</td> |
---|
| 1301 | |
---|
| 1302 | <td>-</td> |
---|
| 1303 | |
---|
| 1304 | <td>UniformIntegerDist</td> |
---|
| 1305 | |
---|
| 1306 | <td>-</td> |
---|
| 1307 | |
---|
| 1308 | <td>-</td> |
---|
| 1309 | </tr> |
---|
| 1310 | |
---|
| 1311 | <tr> |
---|
| 1312 | <td>uniform (float)</td> |
---|
| 1313 | |
---|
| 1314 | <td>uniform_real</td> |
---|
| 1315 | |
---|
| 1316 | <td>RandFlat</td> |
---|
| 1317 | |
---|
| 1318 | <td>UniformDeviate</td> |
---|
| 1319 | |
---|
| 1320 | <td>flat</td> |
---|
| 1321 | |
---|
| 1322 | <td>UniformDoubleDist</td> |
---|
| 1323 | |
---|
| 1324 | <td>-</td> |
---|
| 1325 | |
---|
| 1326 | <td>uniform</td> |
---|
| 1327 | </tr> |
---|
| 1328 | |
---|
| 1329 | <tr> |
---|
| 1330 | <td>exponential</td> |
---|
| 1331 | |
---|
| 1332 | <td>exponential_distribution</td> |
---|
| 1333 | |
---|
| 1334 | <td>RandExponential</td> |
---|
| 1335 | |
---|
| 1336 | <td>ExponentialDeviate</td> |
---|
| 1337 | |
---|
| 1338 | <td>exponential</td> |
---|
| 1339 | |
---|
| 1340 | <td>ExponentialDist</td> |
---|
| 1341 | |
---|
| 1342 | <td>exponential</td> |
---|
| 1343 | |
---|
| 1344 | <td>exponential</td> |
---|
| 1345 | </tr> |
---|
| 1346 | |
---|
| 1347 | <tr> |
---|
| 1348 | <td>normal</td> |
---|
| 1349 | |
---|
| 1350 | <td>normal_distribution</td> |
---|
| 1351 | |
---|
| 1352 | <td>RandGauss*</td> |
---|
| 1353 | |
---|
| 1354 | <td>NormalDeviate</td> |
---|
| 1355 | |
---|
| 1356 | <td>gaussian</td> |
---|
| 1357 | |
---|
| 1358 | <td>NormalDist</td> |
---|
| 1359 | |
---|
| 1360 | <td>normal (gaussian)</td> |
---|
| 1361 | |
---|
| 1362 | <td>normal</td> |
---|
| 1363 | </tr> |
---|
| 1364 | |
---|
| 1365 | <tr> |
---|
| 1366 | <td>lognormal</td> |
---|
| 1367 | |
---|
| 1368 | <td>-</td> |
---|
| 1369 | |
---|
| 1370 | <td>-</td> |
---|
| 1371 | |
---|
| 1372 | <td>-</td> |
---|
| 1373 | |
---|
| 1374 | <td>lognormal</td> |
---|
| 1375 | |
---|
| 1376 | <td>LogNormalDist</td> |
---|
| 1377 | |
---|
| 1378 | <td>-</td> |
---|
| 1379 | |
---|
| 1380 | <td>-</td> |
---|
| 1381 | </tr> |
---|
| 1382 | |
---|
| 1383 | <tr> |
---|
| 1384 | <td>gamma</td> |
---|
| 1385 | |
---|
| 1386 | <td>gamma_distribution</td> |
---|
| 1387 | |
---|
| 1388 | <td>RandGamma</td> |
---|
| 1389 | |
---|
| 1390 | <td>GammaDeviate</td> |
---|
| 1391 | |
---|
| 1392 | <td>gamma</td> |
---|
| 1393 | |
---|
| 1394 | <td>GammaDist</td> |
---|
| 1395 | |
---|
| 1396 | <td>gamma</td> |
---|
| 1397 | |
---|
| 1398 | <td>gamma</td> |
---|
| 1399 | </tr> |
---|
| 1400 | |
---|
| 1401 | <tr> |
---|
| 1402 | <td>beta</td> |
---|
| 1403 | |
---|
| 1404 | <td>-</td> |
---|
| 1405 | |
---|
| 1406 | <td>-</td> |
---|
| 1407 | |
---|
| 1408 | <td>BetaDeviate</td> |
---|
| 1409 | |
---|
| 1410 | <td>beta</td> |
---|
| 1411 | |
---|
| 1412 | <td>-</td> |
---|
| 1413 | |
---|
| 1414 | <td>-</td> |
---|
| 1415 | |
---|
| 1416 | <td>beta</td> |
---|
| 1417 | </tr> |
---|
| 1418 | |
---|
| 1419 | <tr> |
---|
| 1420 | <td>poisson</td> |
---|
| 1421 | |
---|
| 1422 | <td>poisson_distribution</td> |
---|
| 1423 | |
---|
| 1424 | <td>Poisson</td> |
---|
| 1425 | |
---|
| 1426 | <td>PoissonDeviate</td> |
---|
| 1427 | |
---|
| 1428 | <td>poisson</td> |
---|
| 1429 | |
---|
| 1430 | <td>PoissonDist</td> |
---|
| 1431 | |
---|
| 1432 | <td>poisson</td> |
---|
| 1433 | |
---|
| 1434 | <td>poisson</td> |
---|
| 1435 | </tr> |
---|
| 1436 | |
---|
| 1437 | <tr> |
---|
| 1438 | <td>binomial</td> |
---|
| 1439 | |
---|
| 1440 | <td>binomial_distribution</td> |
---|
| 1441 | |
---|
| 1442 | <td>RandBinomial</td> |
---|
| 1443 | |
---|
| 1444 | <td>BinomialDeviate</td> |
---|
| 1445 | |
---|
| 1446 | <td>binomial</td> |
---|
| 1447 | |
---|
| 1448 | <td>-</td> |
---|
| 1449 | |
---|
| 1450 | <td>binomial</td> |
---|
| 1451 | |
---|
| 1452 | <td>binomial</td> |
---|
| 1453 | </tr> |
---|
| 1454 | |
---|
| 1455 | <tr> |
---|
| 1456 | <td>geometric</td> |
---|
| 1457 | |
---|
| 1458 | <td>geometric_distribution</td> |
---|
| 1459 | |
---|
| 1460 | <td>-</td> |
---|
| 1461 | |
---|
| 1462 | <td>GeometricDeviate</td> |
---|
| 1463 | |
---|
| 1464 | <td>geometric</td> |
---|
| 1465 | |
---|
| 1466 | <td>-</td> |
---|
| 1467 | |
---|
| 1468 | <td>-</td> |
---|
| 1469 | |
---|
| 1470 | <td>geometric</td> |
---|
| 1471 | </tr> |
---|
| 1472 | |
---|
| 1473 | <tr> |
---|
| 1474 | <td>bernoulli</td> |
---|
| 1475 | |
---|
| 1476 | <td>bernoulli_distribution</td> |
---|
| 1477 | |
---|
| 1478 | <td>-</td> |
---|
| 1479 | |
---|
| 1480 | <td>BernoulliDeviate</td> |
---|
| 1481 | |
---|
| 1482 | <td>bernoulli</td> |
---|
| 1483 | |
---|
| 1484 | <td>BernoulliDist</td> |
---|
| 1485 | |
---|
| 1486 | <td>-</td> |
---|
| 1487 | |
---|
| 1488 | <td>-</td> |
---|
| 1489 | </tr> |
---|
| 1490 | |
---|
| 1491 | <tr> |
---|
| 1492 | <td>random bit</td> |
---|
| 1493 | |
---|
| 1494 | <td>-</td> |
---|
| 1495 | |
---|
| 1496 | <td>RandBit</td> |
---|
| 1497 | |
---|
| 1498 | <td>-</td> |
---|
| 1499 | |
---|
| 1500 | <td>-</td> |
---|
| 1501 | |
---|
| 1502 | <td>RandomBitDist</td> |
---|
| 1503 | |
---|
| 1504 | <td>-</td> |
---|
| 1505 | |
---|
| 1506 | <td>-</td> |
---|
| 1507 | </tr> |
---|
| 1508 | |
---|
| 1509 | <tr> |
---|
| 1510 | <td>breit-wigner</td> |
---|
| 1511 | |
---|
| 1512 | <td>-</td> |
---|
| 1513 | |
---|
| 1514 | <td>RandBreitWigner</td> |
---|
| 1515 | |
---|
| 1516 | <td>-</td> |
---|
| 1517 | |
---|
| 1518 | <td>-</td> |
---|
| 1519 | |
---|
| 1520 | <td>-</td> |
---|
| 1521 | |
---|
| 1522 | <td>-</td> |
---|
| 1523 | |
---|
| 1524 | <td>-</td> |
---|
| 1525 | </tr> |
---|
| 1526 | |
---|
| 1527 | <tr> |
---|
| 1528 | <td>chi-square</td> |
---|
| 1529 | |
---|
| 1530 | <td>-</td> |
---|
| 1531 | |
---|
| 1532 | <td>RandChiSquare</td> |
---|
| 1533 | |
---|
| 1534 | <td>-</td> |
---|
| 1535 | |
---|
| 1536 | <td>chisq</td> |
---|
| 1537 | |
---|
| 1538 | <td>-</td> |
---|
| 1539 | |
---|
| 1540 | <td>-</td> |
---|
| 1541 | |
---|
| 1542 | <td>chi-square</td> |
---|
| 1543 | </tr> |
---|
| 1544 | |
---|
| 1545 | <tr> |
---|
| 1546 | <td>landau</td> |
---|
| 1547 | |
---|
| 1548 | <td>-</td> |
---|
| 1549 | |
---|
| 1550 | <td>Landau</td> |
---|
| 1551 | |
---|
| 1552 | <td>-</td> |
---|
| 1553 | |
---|
| 1554 | <td>landau</td> |
---|
| 1555 | |
---|
| 1556 | <td>-</td> |
---|
| 1557 | |
---|
| 1558 | <td>-</td> |
---|
| 1559 | |
---|
| 1560 | <td>-</td> |
---|
| 1561 | </tr> |
---|
| 1562 | |
---|
| 1563 | <tr> |
---|
| 1564 | <td>F</td> |
---|
| 1565 | |
---|
| 1566 | <td>-</td> |
---|
| 1567 | |
---|
| 1568 | <td>-</td> |
---|
| 1569 | |
---|
| 1570 | <td>-</td> |
---|
| 1571 | |
---|
| 1572 | <td>F</td> |
---|
| 1573 | |
---|
| 1574 | <td>-</td> |
---|
| 1575 | |
---|
| 1576 | <td>-</td> |
---|
| 1577 | |
---|
| 1578 | <td>F (variance-ratio)</td> |
---|
| 1579 | </tr> |
---|
| 1580 | |
---|
| 1581 | <tr> |
---|
| 1582 | <td>t</td> |
---|
| 1583 | |
---|
| 1584 | <td>-</td> |
---|
| 1585 | |
---|
| 1586 | <td>-</td> |
---|
| 1587 | |
---|
| 1588 | <td>-</td> |
---|
| 1589 | |
---|
| 1590 | <td>t</td> |
---|
| 1591 | |
---|
| 1592 | <td>-</td> |
---|
| 1593 | |
---|
| 1594 | <td>-</td> |
---|
| 1595 | |
---|
| 1596 | <td>t</td> |
---|
| 1597 | </tr> |
---|
| 1598 | </table> |
---|
| 1599 | |
---|
| 1600 | <h3>J. Taxonomy of Concepts</h3>All of the engines support the number |
---|
| 1601 | generator requirements, i.e. they are zero-argument function objects which |
---|
| 1602 | return numbers. All of the distributions are one-argument function objects, |
---|
| 1603 | taking a reference to an engine and returning numbers. All of the engines |
---|
| 1604 | and some of the distributions return uniformly distributed random numbers. |
---|
| 1605 | This is reflected in the concept of the uniform random number generator, |
---|
| 1606 | which refines number generator. Engines for pseudo-random numbers model the |
---|
| 1607 | requirements for pseudo-random number engine, which refines uniform random |
---|
| 1608 | number generator. |
---|
| 1609 | <pre> |
---|
| 1610 | NumberGenerator ---- UniformRandomNumberGenerator ---- PseudoRandomNumberGenerator |
---|
| 1611 | \--- RandomDistribution |
---|
| 1612 | </pre> |
---|
| 1613 | |
---|
| 1614 | <h3>K. Validation</h3>How can a user have confidence that the |
---|
| 1615 | implementation of a random-number engine is exactly as specified, correctly |
---|
| 1616 | taking into account any platform pecularities (e.g., odd-sized ints)? After |
---|
| 1617 | all, minor typos in the implementation might not be apparent; the numbers |
---|
| 1618 | produced may look "random". This proposal therefore specifies for each |
---|
| 1619 | engine the 10000th number in the random number sequence that a |
---|
| 1620 | default-constructed engine object produces. |
---|
| 1621 | |
---|
| 1622 | <p>This is considered an important feature for library implementors and |
---|
| 1623 | serious users to check whether the provided library on the given platform |
---|
| 1624 | returns the correct numbers. It could be argued that a library implementor |
---|
| 1625 | should provide a correct implementation of some standard feature in any |
---|
| 1626 | case.</p> |
---|
| 1627 | |
---|
| 1628 | <p>No other library I have encountered provides explicit validation values |
---|
| 1629 | in either their specification or their implementation, although some of |
---|
| 1630 | them claim to be widely portable.</p> |
---|
| 1631 | |
---|
| 1632 | <p>Another design option for validation that was part of early drafts of |
---|
| 1633 | this proposal is moving the reference number (10000th value in the |
---|
| 1634 | sequence) from specification space to implementation space, thus providing |
---|
| 1635 | a <code>validation(x)</code> static member function for each engine that |
---|
| 1636 | compares the hard-coded 10000th value of the sequence with some |
---|
| 1637 | user-provided value <code>x</code> presumeably obtained by actually |
---|
| 1638 | invoking the random-number engine object 10000 times. Due to the |
---|
| 1639 | template-based design, this amounted to a "val" template value parameter |
---|
| 1640 | for each engine, and the <code>validation(x)</code> function reduced to the |
---|
| 1641 | trivial comparison "val == x". Handling validation for floating-point |
---|
| 1642 | engines required more machinery, because template value parameters cannot |
---|
| 1643 | be of floating-point type. Also, from a conceptual perspective, it seemed |
---|
| 1644 | odd to demand a validation decision from the very entitiy which one wanted |
---|
| 1645 | to validate.</p> |
---|
| 1646 | |
---|
| 1647 | <h3>L. Non-Volatile Storage of Engine and Distribution |
---|
| 1648 | State</h3>Pseudo-random number engines and distributions may store their |
---|
| 1649 | state on a <code>std::ostream</code> in textual form and recover it from an |
---|
| 1650 | appropriate <code>std::istream</code>. Each engine specifies how its |
---|
| 1651 | internal state is represented. The specific algorithm of a distribution is |
---|
| 1652 | left implementation-defined, thus no specifics about the representation of |
---|
| 1653 | its internal state are given. A store operation must not affect the number |
---|
| 1654 | sequence produced. It is expected that such external storage happens rarely |
---|
| 1655 | as opposed to producing random numbers, thus no particular attention to |
---|
| 1656 | performance is paid. |
---|
| 1657 | |
---|
| 1658 | <p>Engines and distributions use the usual idioms of |
---|
| 1659 | <code>operator<<</code> and <code>operator>></code>. If the |
---|
| 1660 | user needs additional processing before or after storage on non-volatile |
---|
| 1661 | media, there is always the option to use a temporary |
---|
| 1662 | <code>std::stringstream</code>.</p> |
---|
| 1663 | |
---|
| 1664 | <p>Distributions sometimes store values from their associated source of |
---|
| 1665 | random numbers across calls to their <code>operator()</code>. For example, |
---|
| 1666 | a common method for generating normally distributed random numbers is to |
---|
| 1667 | retrieve two uniformly distributed random numbers and compute two normally |
---|
| 1668 | distributed random numbers out of them. In order to reset the |
---|
| 1669 | distribution's random number cache to a defined state, each distribution |
---|
| 1670 | has a <code>reset</code> member function. It should be called on a |
---|
| 1671 | distribution whenever its associated engine is exchanged or restored.</p> |
---|
| 1672 | |
---|
| 1673 | <h3>M. Values vs. References</h3>Compounded engines such as |
---|
| 1674 | <code>shuffle_output</code> and <code>discard_block</code> contain a base |
---|
| 1675 | engine by value, because compounding is not intended to be used by |
---|
| 1676 | reference to an existing (re-used) engine object. |
---|
| 1677 | |
---|
| 1678 | <p>The wrapper <code>variate_generator</code> can store engines either by |
---|
| 1679 | value or by reference, explicitly chosen by the template parameters. This |
---|
| 1680 | allows to use references to a single engine in several |
---|
| 1681 | <code>variate_generator</code>, but makes it explicit to the user that he |
---|
| 1682 | is responsible for the management of the lifetime of the engine.</p> |
---|
| 1683 | |
---|
| 1684 | <h3>N. Providing the Probability Density Function in Distributions</h3>Some |
---|
| 1685 | libraries provide the probability density function of a given distribution |
---|
| 1686 | as part of that distribution's interface. While this may be useful |
---|
| 1687 | occasionally, this proposal does not provide for such a feature. One reason |
---|
| 1688 | is separation of concerns: The distribution class templates might benefit |
---|
| 1689 | from precomputing large tables of values depending on the distribution |
---|
| 1690 | parameters, while the computation of the probability density function does |
---|
| 1691 | not. Also, the function representation is often straightforward, so the |
---|
| 1692 | user can easily code it himself. |
---|
| 1693 | |
---|
| 1694 | <h3>O. Implementation-defined behaviour</h3>This proposal specifies |
---|
| 1695 | implementation-defined behaviour in a number of places. I believe this is |
---|
| 1696 | unavoidable; this section provides detailed reasoning, including why the |
---|
| 1697 | implementation is required to document the choice. |
---|
| 1698 | |
---|
| 1699 | <p>The precise state-holding base data types for the various engines are |
---|
| 1700 | left implementation-defined, because engines are usually optimized for |
---|
| 1701 | binary integers with 32 bits of word size. The specification in this |
---|
| 1702 | proposal cannot foresee whether a 32 bit quantity on the machine is |
---|
| 1703 | available in C++ as short, int, long, or not at all. It is up to the |
---|
| 1704 | implementation to decide which data type fits best. The implementation is |
---|
| 1705 | required to document the choice of data type, so that users can |
---|
| 1706 | (non-portably) rely on the precise type, for example for further |
---|
| 1707 | computation. Should the ISO C99 extensions become part of ISO C++, the |
---|
| 1708 | implementation-defined types could be replaced by e.g. |
---|
| 1709 | <code>int_least32_t</code>.</p> |
---|
| 1710 | |
---|
| 1711 | <p>The method how to produce non-deterministic random numbers is considered |
---|
| 1712 | implementation-defined, because it inherently depends on the implementation |
---|
| 1713 | and possibly even on the runtime environment: Imagine a platform that has |
---|
| 1714 | operating system support for randomness collection, e.g. from user |
---|
| 1715 | keystrokes and Ethernet inter-packet arrival timing (Linux |
---|
| 1716 | <code>/dev/random</code> does this). If, in some installation, access to |
---|
| 1717 | the operating system functions providing these services has been |
---|
| 1718 | restricted, the C++ non-deterministic random number engine has been |
---|
| 1719 | deprived of its randomness. An implementation is required to document how |
---|
| 1720 | it obtains the non-deterministic random numbers, because only then can |
---|
| 1721 | users' confidence in them grow. Confidence is of particular concern in the |
---|
| 1722 | area of cryptography.</p> |
---|
| 1723 | |
---|
| 1724 | <p>The algorithms how to produce the various distributions are specified as |
---|
| 1725 | implementation-defined, because there is a vast variety of algorithms known |
---|
| 1726 | for each distribution. Each has a different trade-off in terms of speed, |
---|
| 1727 | adaptation to recent computer architectures, and memory use. The |
---|
| 1728 | implementation is required to document its choice so that the user can |
---|
| 1729 | judge whether it is acceptable quality-wise.</p> |
---|
| 1730 | |
---|
| 1731 | <h3>P. Lower and upper bounds on UniformRandomNumberGenerator</h3>The |
---|
| 1732 | member functions <code>min()</code> and <code>max()</code> return the lower |
---|
| 1733 | and upper bounds of a UniformRandomNumberGenerator. This could be a |
---|
| 1734 | random-number engine or one of the <code>uniform_int</code> and |
---|
| 1735 | <code>uniform_real</code> distributions. |
---|
| 1736 | |
---|
| 1737 | <p>Those bounds are not specified to be tight, because for some engines, |
---|
| 1738 | the bounds depend on the seeds. The seed can be changed during the lifetime |
---|
| 1739 | of the engine object, while the values returned by <code>min()</code> and |
---|
| 1740 | <code>max()</code> are invariant. Therefore, <code>min()</code> and |
---|
| 1741 | <code>max()</code> must return conservative bounds that are independent of |
---|
| 1742 | the seed.</p> |
---|
| 1743 | |
---|
| 1744 | <h3>Q. With or without manager class</h3>This proposal presents a design |
---|
| 1745 | with a manager class template, <code>variate_generator</code>, after |
---|
| 1746 | extensive discussion with some members of the computing division of Fermi |
---|
| 1747 | National Accelerator Laboratory. User-written and library-provided engines |
---|
| 1748 | and distributions plug in to the manager class. The approach is remotely |
---|
| 1749 | similar to the locale design in the standard library, where (user-written) |
---|
| 1750 | facets plug in to the (library-provided) locale class. |
---|
| 1751 | |
---|
| 1752 | <p>Earlier versions of this propsoal made (potentially user-written) |
---|
| 1753 | distributions directly visible to (some other) user that wants to get |
---|
| 1754 | random numbers distributed accordingly ("client"), there was no additional |
---|
| 1755 | management layer between the distribution and the client.</p> |
---|
| 1756 | |
---|
| 1757 | <p>The following additional features could be provided by the management |
---|
| 1758 | layer:</p> |
---|
| 1759 | |
---|
| 1760 | <ul> |
---|
| 1761 | <li>The management layer contains an adaptor (to convert the engine's |
---|
| 1762 | output into the distribution's input) in addition to the engine and the |
---|
| 1763 | distribution.</li> |
---|
| 1764 | |
---|
| 1765 | <li>Adaptors and distributions do not store state, but instead, in each |
---|
| 1766 | invocation, consume an arbitrary number of input values and produce a |
---|
| 1767 | fixed number of output values. The management layer is responsible for |
---|
| 1768 | connecting the engine - adaptor - distribution chain, invoking each part |
---|
| 1769 | when more numbers are needed from the next part of the chain.</li> |
---|
| 1770 | |
---|
| 1771 | <li>On request, the management layer is responsible for saving and |
---|
| 1772 | restoring the buffers that exist between engine, adaptor, and |
---|
| 1773 | distribution.</li> |
---|
| 1774 | |
---|
| 1775 | <li>On request, the management layer shares engines with another instance |
---|
| 1776 | of the management layer.</li> |
---|
| 1777 | </ul>It is envisioned that user-written distributions will often be based |
---|
| 1778 | on some arbitrary algorithmic distribution, instead of trying to implement |
---|
| 1779 | a given mathematical probability density function. Here is an example: |
---|
| 1780 | |
---|
| 1781 | <ul> |
---|
| 1782 | <li>Retrieve a uniform integer with value either 1 or 2.</li> |
---|
| 1783 | |
---|
| 1784 | <li>If 1, return a number with normal distribution.</li> |
---|
| 1785 | |
---|
| 1786 | <li>If 2, return a number with gamma distribution.</li> |
---|
| 1787 | </ul>Both in this case and when implementing complex distributions based on |
---|
| 1788 | a probability density function (e.g. the gamma distribution), it is |
---|
| 1789 | important to be able to arbitrarily nest distributions. Either design |
---|
| 1790 | allows for this with utmost ease: Compounding distributions are contained |
---|
| 1791 | in the compound by value, and each one produces a single value on |
---|
| 1792 | invocation. With the alternative design of giving distributions the freedom |
---|
| 1793 | to produce more than one output number in each invocation, compound |
---|
| 1794 | distributions such as the one shown above need to handle the situation that |
---|
| 1795 | each of the compounding members could provide several output values, the |
---|
| 1796 | number of which is unknown at the time the distribution is written. |
---|
| 1797 | (Remember that it is unfeasible to prescribe a precise algorithm for each |
---|
| 1798 | library-provided distribution in the standard, see subsection O.) That |
---|
| 1799 | approach shifts implementation effort from the place where it came up, i.e. |
---|
| 1800 | the distribution that chose to use an algorithm that produces several |
---|
| 1801 | values in one invocation, to the places where that distribution is used. |
---|
| 1802 | This, considered by itself, does not seem to be a good approach. Also, only |
---|
| 1803 | very few distributions lead to a natural implementation that produces |
---|
| 1804 | several values in one invocation; so far, the normal distribution is the |
---|
| 1805 | only one known to me. However, it is expected that there will be plenty of |
---|
| 1806 | distributions that use a normal distribution as its base, so far those |
---|
| 1807 | known to me are lognormal and uniform_on_sphere (both not part of this |
---|
| 1808 | proposal). As a conclusion, independent of whether the design provides for |
---|
| 1809 | a management layer or not, distributions should always return a single |
---|
| 1810 | value on each invocation, and management of buffers for additional values |
---|
| 1811 | that might be produced should be internal to the distribution. Should it |
---|
| 1812 | become necessary for the user to employ buffer management more often, a |
---|
| 1813 | user-written base class for the distributions could be of help. |
---|
| 1814 | |
---|
| 1815 | <p>The ability to share engines is important. This proposal makes lifetime |
---|
| 1816 | management issues explicit by requiring pointer or reference types in the |
---|
| 1817 | template instantiation of <code>variate_generator</code> if reference |
---|
| 1818 | semantics are desired. Without a management class, providing this features |
---|
| 1819 | is much more cumbersome and imposes additional burden on the programmers |
---|
| 1820 | that produce distributions. Alternatively, reference semantics could always |
---|
| 1821 | be used, but this is an error-prone approach due to the lack of a standard |
---|
| 1822 | reference-counted smart pointer. I believe it is impossible to add a |
---|
| 1823 | reference-counted sharing mechanism in a manager-class-free design without |
---|
| 1824 | giving its precise type. And that would certainly conflict in semantic |
---|
| 1825 | scope with a smart pointer that will get into the standard eventually.</p> |
---|
| 1826 | |
---|
| 1827 | <p>The management layer allows for a few common features to be factored |
---|
| 1828 | out, in particular access to the engine and some member typedefs.</p> |
---|
| 1829 | |
---|
| 1830 | <p>Comparison of other differing features between manager and non-manager |
---|
| 1831 | designs:</p> |
---|
| 1832 | |
---|
| 1833 | <ul> |
---|
| 1834 | <li>When passing a <code>variate_generator</code> as a an argument to a |
---|
| 1835 | function, the design in this proposal allows selecting only those |
---|
| 1836 | function signatures during overload resolution that are intended to be |
---|
| 1837 | called with a <code>variate_generator</code>. In contrast, misbehaviour |
---|
| 1838 | is possible without a manager class, similar to iterators in function |
---|
| 1839 | signatures: <code>template<class BiIter> void f(BiIter it)</code> |
---|
| 1840 | matches <code>f(5)</code>, without regard to the bidirectional iterator |
---|
| 1841 | requirements. An error then happens when instantiating f. The situation |
---|
| 1842 | worsens when several competing function templates are available and the |
---|
| 1843 | wrong one is chosen accidentally.</li> |
---|
| 1844 | |
---|
| 1845 | <li>With the engine passed into the distribution's constructor, the full |
---|
| 1846 | type hierarchy of engine (and possibly adaptor) are available to the |
---|
| 1847 | distribution, allowing to cache information derived from the engine (e.g. |
---|
| 1848 | its value range) . Also, (partial) specialization of distributions could |
---|
| 1849 | be written that optimize the interaction with a specific engine and/or |
---|
| 1850 | adaptor. In this proposal's design, this information is available in the |
---|
| 1851 | <code>variate_generator</code> template only. However, optimizations by |
---|
| 1852 | specialization for the engine/adaptor combination are perceived to |
---|
| 1853 | possibly have high benefit, while those for the (engine+adaptor) / |
---|
| 1854 | distribution combination are presumed to be much less beneficial.</li> |
---|
| 1855 | |
---|
| 1856 | <li>Having distribution classes directly exposed to the client easily |
---|
| 1857 | allows that the user writes a distribution with an additional arbitrary |
---|
| 1858 | member function declaration, intended to produce random numbers while |
---|
| 1859 | taking additional parameters into account. In this proposal's design, |
---|
| 1860 | this is possible by using the generic <code>operator()(T x)</code> |
---|
| 1861 | forwarding function.</li> |
---|
| 1862 | </ul> |
---|
| 1863 | |
---|
| 1864 | <h3>R. Add-on packages</h3>This proposal specifies a framework for random |
---|
| 1865 | number generation. Users might have additional requirements not met by this |
---|
| 1866 | framework. The following extensions have been identified, and they are |
---|
| 1867 | expressly not addressed in this proposal. It is perceived that these items |
---|
| 1868 | can be seamlessly implemented in an add-on package which sits on top of an |
---|
| 1869 | implementation according to this proposal. |
---|
| 1870 | |
---|
| 1871 | <ul> |
---|
| 1872 | <li>unique seeding: Make it easy for the user to provide a unique seed |
---|
| 1873 | for each instance of a pseudo-random number engine. Design idea: |
---|
| 1874 | <pre> |
---|
| 1875 | class unique_seed; |
---|
| 1876 | |
---|
| 1877 | template<class Engine> |
---|
| 1878 | Engine seed(unique_seed&); |
---|
| 1879 | </pre>The "seed" function retrieves some unique seed from the unique_seed |
---|
| 1880 | class and then uses the <code>seed(first, last)</code> interface of an engine |
---|
| 1881 | to implant that unique seed. Specific seeding requirements for some engine |
---|
| 1882 | can be met by (partial) template specialization. |
---|
| 1883 | </li> |
---|
| 1884 | |
---|
| 1885 | <li>runtime-replaceable distributions and associated save/restore |
---|
| 1886 | functionality: Provide a class hierarchy that invokes distributions by |
---|
| 1887 | means of a virtual function, thereby allowing for runtime replacement of |
---|
| 1888 | the actual distribution. Provide a factory function to reconstruct the |
---|
| 1889 | distribution instance after saving it to some non-volatile media.</li> |
---|
| 1890 | </ul> |
---|
| 1891 | |
---|
| 1892 | <h3>S. Adaptors</h3>Sometimes, users may want to have better control how |
---|
| 1893 | the bits from the engine are used to fill the mantissa of the |
---|
| 1894 | floating-point value that serves as input to some distribution. This is |
---|
| 1895 | possible by writing an engine wrapper and passing that in to the |
---|
| 1896 | <code>variate_generator</code> as the engine. The |
---|
| 1897 | <code>variate_generator</code> will only apply automatic adaptations if the |
---|
| 1898 | output type of the engine is integers and the input type for the |
---|
| 1899 | distribution is floating-point or vice versa. |
---|
| 1900 | |
---|
| 1901 | <h3>Z. Open issues</h3> |
---|
| 1902 | |
---|
| 1903 | <ul> |
---|
| 1904 | <li>Some engines require non-negative template arguments, usually bit |
---|
| 1905 | counts. Should these be given as "int" or "unsigned int"? Using "unsigned |
---|
| 1906 | int" sometimes adds significant clutter to the presentation. Or "size_t", |
---|
| 1907 | but this is probably too large a type?</li> |
---|
| 1908 | </ul> |
---|
| 1909 | |
---|
| 1910 | <h2>IV. Proposed Text</h2>(Insert the following as a new section in clause |
---|
| 1911 | 26 "Numerics". Adjust the overview at the beginning of clause 26 |
---|
| 1912 | accordingly.) |
---|
| 1913 | |
---|
| 1914 | <p>This subclause defines a facility for generating random numbers.</p> |
---|
| 1915 | |
---|
| 1916 | <h3>Random number requirements</h3>A number generator is a function object |
---|
| 1917 | (std:20.3 [lib.function.objects]). |
---|
| 1918 | |
---|
| 1919 | <p>In the following table, <code>X</code> denotes a number generator class |
---|
| 1920 | returning objects of type <code>T</code>, and <code>u</code> is a (possibly |
---|
| 1921 | <code>const</code>) value of <code>X</code>.</p> |
---|
| 1922 | |
---|
| 1923 | <table border="1" summary=""> |
---|
| 1924 | <tr> |
---|
| 1925 | <th colspan="4" align="center">Number generator requirements (in |
---|
| 1926 | addition to function object)</th> |
---|
| 1927 | </tr> |
---|
| 1928 | |
---|
| 1929 | <tr> |
---|
| 1930 | <td>expression</td> |
---|
| 1931 | |
---|
| 1932 | <td>return type</td> |
---|
| 1933 | |
---|
| 1934 | <td>pre/post-condition</td> |
---|
| 1935 | |
---|
| 1936 | <td>complexity</td> |
---|
| 1937 | </tr> |
---|
| 1938 | |
---|
| 1939 | <tr> |
---|
| 1940 | <td><code>X::result_type</code></td> |
---|
| 1941 | |
---|
| 1942 | <td>T</td> |
---|
| 1943 | |
---|
| 1944 | <td><code>std::numeric_limits<T>::is_specialized</code> is |
---|
| 1945 | <code>true</code></td> |
---|
| 1946 | |
---|
| 1947 | <td>compile-time</td> |
---|
| 1948 | </tr> |
---|
| 1949 | </table> |
---|
| 1950 | |
---|
| 1951 | <p>In the following table, <code>X</code> denotes a uniform random number |
---|
| 1952 | generator class returning objects of type <code>T</code>, <code>u</code> is |
---|
| 1953 | a value of <code>X</code> and <code>v</code> is a (possibly |
---|
| 1954 | <code>const</code>) value of <code>X</code>.</p> |
---|
| 1955 | |
---|
| 1956 | <table border="1" summary=""> |
---|
| 1957 | <tr> |
---|
| 1958 | <th colspan="4" align="center">Uniform random number generator |
---|
| 1959 | requirements (in addition to number generator)</th> |
---|
| 1960 | </tr> |
---|
| 1961 | |
---|
| 1962 | <tr> |
---|
| 1963 | <td>expression</td> |
---|
| 1964 | |
---|
| 1965 | <td>return type</td> |
---|
| 1966 | |
---|
| 1967 | <td>pre/post-condition</td> |
---|
| 1968 | |
---|
| 1969 | <td>complexity</td> |
---|
| 1970 | </tr> |
---|
| 1971 | |
---|
| 1972 | <tr> |
---|
| 1973 | <td><code>u()</code></td> |
---|
| 1974 | |
---|
| 1975 | <td>T</td> |
---|
| 1976 | |
---|
| 1977 | <td>-</td> |
---|
| 1978 | |
---|
| 1979 | <td>amortized constant</td> |
---|
| 1980 | </tr> |
---|
| 1981 | |
---|
| 1982 | <tr> |
---|
| 1983 | <td><code>v.min()</code></td> |
---|
| 1984 | |
---|
| 1985 | <td><code>T</code></td> |
---|
| 1986 | |
---|
| 1987 | <td>Returns some l where l is less than or equal to all values |
---|
| 1988 | potentially returned by <code>operator()</code>. The return value of |
---|
| 1989 | this function shall not change during the lifetime of |
---|
| 1990 | <code>v</code>.</td> |
---|
| 1991 | |
---|
| 1992 | <td>constant</td> |
---|
| 1993 | </tr> |
---|
| 1994 | |
---|
| 1995 | <tr> |
---|
| 1996 | <td><code>v.max()</code></td> |
---|
| 1997 | |
---|
| 1998 | <td><code>T</code></td> |
---|
| 1999 | |
---|
| 2000 | <td>If <code>std::numeric_limits<T>::is_integer</code>, returns l |
---|
| 2001 | where l is less than or equal to all values potentially returned by |
---|
| 2002 | <code>operator()</code>, otherwise, returns l where l is strictly less |
---|
| 2003 | than all values potentially returned by <code>operator()</code>. In any |
---|
| 2004 | case, the return value of this function shall not change during the |
---|
| 2005 | lifetime of <code>v</code>.</td> |
---|
| 2006 | |
---|
| 2007 | <td>constant</td> |
---|
| 2008 | </tr> |
---|
| 2009 | </table> |
---|
| 2010 | |
---|
| 2011 | <p>In the following table, <code>X</code> denotes a pseudo-random number |
---|
| 2012 | engine class returning objects of type <code>T</code>, <code>t</code> is a |
---|
| 2013 | value of <code>T</code>, <code>u</code> is a value of <code>X</code>, |
---|
| 2014 | <code>v</code> is an lvalue of <code>X</code>, <code>it1</code> is an |
---|
| 2015 | lvalue and <code>it2</code> is a (possibly <code>const</code>) value of an |
---|
| 2016 | input iterator type <code>It</code> having an unsigned integral value type, |
---|
| 2017 | <code>x</code>, <code>y</code> are (possibly <code>const</code>) values of |
---|
| 2018 | <code>X</code>, <code>os</code> is convertible to an lvalue of type |
---|
| 2019 | <code>std::ostream</code>, and <code>is</code> is convertible to an lvalue |
---|
| 2020 | of type <code>std::istream</code>.</p> |
---|
| 2021 | |
---|
| 2022 | <p>A pseudo-random number engine x has a state x(i) at any given time. The |
---|
| 2023 | specification of each pseudo-random number engines defines the size of its |
---|
| 2024 | state in multiples of the size of its <code>result_type</code>, given as an |
---|
| 2025 | integral constant expression.</p> |
---|
| 2026 | |
---|
| 2027 | <table border="1" summary=""> |
---|
| 2028 | <tr> |
---|
| 2029 | <th colspan="4" align="center">Pseudo-random number engine requirements |
---|
| 2030 | (in addition to uniform random number generator, |
---|
| 2031 | <code>CopyConstructible</code>, and <code>Assignable</code>)</th> |
---|
| 2032 | </tr> |
---|
| 2033 | |
---|
| 2034 | <tr> |
---|
| 2035 | <td>expression</td> |
---|
| 2036 | |
---|
| 2037 | <td>return type</td> |
---|
| 2038 | |
---|
| 2039 | <td>pre/post-condition</td> |
---|
| 2040 | |
---|
| 2041 | <td>complexity</td> |
---|
| 2042 | </tr> |
---|
| 2043 | |
---|
| 2044 | <tr> |
---|
| 2045 | <td><code>X()</code></td> |
---|
| 2046 | |
---|
| 2047 | <td>-</td> |
---|
| 2048 | |
---|
| 2049 | <td>creates an engine with the same initial state as all other |
---|
| 2050 | default-constructed engines of type <code>X</code> in the program.</td> |
---|
| 2051 | |
---|
| 2052 | <td>O(size of state)</td> |
---|
| 2053 | </tr> |
---|
| 2054 | |
---|
| 2055 | <tr> |
---|
| 2056 | <td><code>X(it1, it2)</code></td> |
---|
| 2057 | |
---|
| 2058 | <td>-</td> |
---|
| 2059 | |
---|
| 2060 | <td>creates an engine with the initial state given by the range |
---|
| 2061 | <code>[it1,it2)</code>. <code>it1</code> is advanced by the size of |
---|
| 2062 | state. If the size of the range [it1,it2) is insufficient, leaves |
---|
| 2063 | <code>it1 == it2</code> and throws <code>invalid_argument</code>.</td> |
---|
| 2064 | |
---|
| 2065 | <td>O(size of state)</td> |
---|
| 2066 | </tr> |
---|
| 2067 | |
---|
| 2068 | <tr> |
---|
| 2069 | <td><code>u.seed()</code></td> |
---|
| 2070 | |
---|
| 2071 | <td>void</td> |
---|
| 2072 | |
---|
| 2073 | <td>post: <code>u == X()</code></td> |
---|
| 2074 | |
---|
| 2075 | <td>O(size of state)</td> |
---|
| 2076 | </tr> |
---|
| 2077 | |
---|
| 2078 | <tr> |
---|
| 2079 | <td><code>u.seed(it1, it2)</code></td> |
---|
| 2080 | |
---|
| 2081 | <td>void</td> |
---|
| 2082 | |
---|
| 2083 | <td>post: If there are sufficiently many values in [it1, it2) to |
---|
| 2084 | initialize the state of <code>u</code>, then <code>u == |
---|
| 2085 | X(it1,it2)</code>. Otherwise, <code>it1 == it2</code>, throws |
---|
| 2086 | <code>invalid_argument</code>, and further use of <code>u</code> |
---|
| 2087 | (except destruction) is undefined until a <code>seed</code> member |
---|
| 2088 | function has been executed without throwing an exception.</td> |
---|
| 2089 | |
---|
| 2090 | <td>O(size of state)</td> |
---|
| 2091 | </tr> |
---|
| 2092 | |
---|
| 2093 | <tr> |
---|
| 2094 | <td><code>u()</code></td> |
---|
| 2095 | |
---|
| 2096 | <td><code>T</code></td> |
---|
| 2097 | |
---|
| 2098 | <td>given the state u(i) of the engine, computes u(i+1), sets the state |
---|
| 2099 | to u(i+1), and returns some output dependent on u(i+1)</td> |
---|
| 2100 | |
---|
| 2101 | <td>amortized constant</td> |
---|
| 2102 | </tr> |
---|
| 2103 | |
---|
| 2104 | <tr> |
---|
| 2105 | <td><code>x == y</code></td> |
---|
| 2106 | |
---|
| 2107 | <td><code>bool</code></td> |
---|
| 2108 | |
---|
| 2109 | <td><code>==</code> is an equivalence relation. The current state x(i) |
---|
| 2110 | of x is equal to the current state y(j) of y.</td> |
---|
| 2111 | |
---|
| 2112 | <td>O(size of state)</td> |
---|
| 2113 | </tr> |
---|
| 2114 | |
---|
| 2115 | <tr> |
---|
| 2116 | <td><code>x != y</code></td> |
---|
| 2117 | |
---|
| 2118 | <td><code>bool</code></td> |
---|
| 2119 | |
---|
| 2120 | <td><code>!(x == y)</code></td> |
---|
| 2121 | |
---|
| 2122 | <td>O(size of state)</td> |
---|
| 2123 | </tr> |
---|
| 2124 | |
---|
| 2125 | <tr> |
---|
| 2126 | <td><code>os << x</code></td> |
---|
| 2127 | |
---|
| 2128 | <td><code>std::ostream&</code></td> |
---|
| 2129 | |
---|
| 2130 | <td>writes the textual representation of the state x(i) of |
---|
| 2131 | <code>x</code> to <code>os</code>, with |
---|
| 2132 | <code>os.<em>fmtflags</em></code> set to |
---|
| 2133 | <code>ios_base::dec|ios_base::fixed|ios_base::left</code> and the fill |
---|
| 2134 | character set to the space character. In the output, adjacent numbers |
---|
| 2135 | are separated by one or more space characters.<br> |
---|
| 2136 | post: The <code>os.<em>fmtflags</em></code> and fill character are |
---|
| 2137 | unchanged.</td> |
---|
| 2138 | |
---|
| 2139 | <td>O(size of state)</td> |
---|
| 2140 | </tr> |
---|
| 2141 | |
---|
| 2142 | <tr> |
---|
| 2143 | <td><code>is >> v</code></td> |
---|
| 2144 | |
---|
| 2145 | <td><code>std::istream&</code></td> |
---|
| 2146 | |
---|
| 2147 | <td>sets the state v(i) of <code>v</code> as determined by reading its |
---|
| 2148 | textual representation from <code>is</code>.<br> |
---|
| 2149 | post: The <code>is.<em>fmtflags</em></code> are unchanged.</td> |
---|
| 2150 | |
---|
| 2151 | <td>O(size of state)</td> |
---|
| 2152 | </tr> |
---|
| 2153 | </table> |
---|
| 2154 | |
---|
| 2155 | <p>In the following table, <code>X</code> denotes a random distribution |
---|
| 2156 | class returning objects of type <code>T</code>, <code>u</code> is a value |
---|
| 2157 | of <code>X</code>, <code>x</code> is a (possibly const) value of |
---|
| 2158 | <code>X</code>, and <code>e</code> is an lvalue of an arbitrary type that |
---|
| 2159 | meets the requirements of a uniform random number generator, returning |
---|
| 2160 | values of type <code>U</code>.</p> |
---|
| 2161 | |
---|
| 2162 | <table border="1" summary=""> |
---|
| 2163 | <tr> |
---|
| 2164 | <th colspan="4" align="center">Random distribution requirements (in |
---|
| 2165 | addition to number generator, <code>CopyConstructible</code>, and |
---|
| 2166 | <code>Assignable</code>)</th> |
---|
| 2167 | </tr> |
---|
| 2168 | |
---|
| 2169 | <tr> |
---|
| 2170 | <td>expression</td> |
---|
| 2171 | |
---|
| 2172 | <td>return type</td> |
---|
| 2173 | |
---|
| 2174 | <td>pre/post-condition</td> |
---|
| 2175 | |
---|
| 2176 | <td>complexity</td> |
---|
| 2177 | </tr> |
---|
| 2178 | |
---|
| 2179 | <tr> |
---|
| 2180 | <td><code>X::input_type</code></td> |
---|
| 2181 | |
---|
| 2182 | <td>U</td> |
---|
| 2183 | |
---|
| 2184 | <td>-</td> |
---|
| 2185 | |
---|
| 2186 | <td>compile-time</td> |
---|
| 2187 | </tr> |
---|
| 2188 | |
---|
| 2189 | <tr> |
---|
| 2190 | <td><code>u.reset()</code></td> |
---|
| 2191 | |
---|
| 2192 | <td><code>void</code></td> |
---|
| 2193 | |
---|
| 2194 | <td>subsequent uses of <code>u</code> do not depend on values produced |
---|
| 2195 | by <code>e</code> prior to invoking <code>reset</code>.</td> |
---|
| 2196 | |
---|
| 2197 | <td>constant</td> |
---|
| 2198 | </tr> |
---|
| 2199 | |
---|
| 2200 | <tr> |
---|
| 2201 | <td><code>u(e)</code></td> |
---|
| 2202 | |
---|
| 2203 | <td><code>T</code></td> |
---|
| 2204 | |
---|
| 2205 | <td>the sequence of numbers returned by successive invocations with the |
---|
| 2206 | same object <code>e</code> is randomly distributed with some |
---|
| 2207 | probability density function p(x)</td> |
---|
| 2208 | |
---|
| 2209 | <td>amortized constant number of invocations of <code>e</code></td> |
---|
| 2210 | </tr> |
---|
| 2211 | |
---|
| 2212 | <tr> |
---|
| 2213 | <td><code>os << x</code></td> |
---|
| 2214 | |
---|
| 2215 | <td><code>std::ostream&</code></td> |
---|
| 2216 | |
---|
| 2217 | <td>writes a textual representation for the parameters and additional |
---|
| 2218 | internal data of the distribution <code>x</code> to |
---|
| 2219 | <code>os</code>.<br> |
---|
| 2220 | post: The <code>os.<em>fmtflags</em></code> and fill character are |
---|
| 2221 | unchanged.</td> |
---|
| 2222 | |
---|
| 2223 | <td>O(size of state)</td> |
---|
| 2224 | </tr> |
---|
| 2225 | |
---|
| 2226 | <tr> |
---|
| 2227 | <td><code>is >> u</code></td> |
---|
| 2228 | |
---|
| 2229 | <td><code>std::istream&</code></td> |
---|
| 2230 | |
---|
| 2231 | <td>restores the parameters and additional internal data of the |
---|
| 2232 | distribution <code>u</code>.<br> |
---|
| 2233 | pre: <code>is</code> provides a textual representation that was |
---|
| 2234 | previously written by <code>operator<<</code><br> |
---|
| 2235 | post: The <code>is.<em>fmtflags</em></code> are unchanged.</td> |
---|
| 2236 | |
---|
| 2237 | <td>O(size of state)</td> |
---|
| 2238 | </tr> |
---|
| 2239 | </table> |
---|
| 2240 | |
---|
| 2241 | <p>Additional requirements: The sequence of numbers produced by repeated |
---|
| 2242 | invocations of <code>x(e)</code> does not change whether or not <code>os |
---|
| 2243 | << x</code> is invoked between any of the invocations |
---|
| 2244 | <code>x(e)</code>. If a textual representation is written using <code>os |
---|
| 2245 | << x</code> and that representation is restored into the same or a |
---|
| 2246 | different object <code>y</code> of the same type using <code>is >> |
---|
| 2247 | y</code>, repeated invocations of <code>y(e)</code> produce the same |
---|
| 2248 | sequence of random numbers as would repeated invocations of |
---|
| 2249 | <code>x(e)</code>.</p> |
---|
| 2250 | |
---|
| 2251 | <p>In the following subclauses, a template parameter named |
---|
| 2252 | <code>UniformRandomNumberGenerator</code> shall denote a class that |
---|
| 2253 | satisfies all the requirements of a uniform random number generator. |
---|
| 2254 | Moreover, a template parameter named <code>Distribution</code> shall denote |
---|
| 2255 | a type that satisfies all the requirements of a random distribution. |
---|
| 2256 | Furthermore, a template parameter named <code>RealType</code> shall denote |
---|
| 2257 | a type that holds an approximation to a real number. This type shall meet |
---|
| 2258 | the requirements for a numeric type (26.1 [lib.numeric.requirements]), the |
---|
| 2259 | binary operators +, -, *, / shall be applicable to it, a conversion from |
---|
| 2260 | <code>double</code> shall exist, and function signatures corresponding to |
---|
| 2261 | those for type <code>double</code> in subclause 26.5 [lib.c.math] shall be |
---|
| 2262 | available by argument-dependent lookup (3.4.2 [basic.lookup.koenig]). |
---|
| 2263 | <em>[Note: The built-in floating-point types <code>float</code> and |
---|
| 2264 | <code>double</code> meet these requirements.]</em></p> |
---|
| 2265 | |
---|
| 2266 | <h3>Header <code><random></code> synopsis</h3> |
---|
| 2267 | <pre> |
---|
| 2268 | namespace std { |
---|
| 2269 | template<class UniformRandomNumberGenerator, class Distribution> |
---|
| 2270 | class variate_generator; |
---|
| 2271 | |
---|
| 2272 | template<class IntType, IntType a, IntType c, IntType m> |
---|
| 2273 | class linear_congruential; |
---|
| 2274 | |
---|
| 2275 | template<class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2276 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2277 | class mersenne_twister; |
---|
| 2278 | |
---|
| 2279 | template<class IntType, IntType m, int s, int r> |
---|
| 2280 | class subtract_with_carry; |
---|
| 2281 | |
---|
| 2282 | template<class RealType, int w, int s, int r> |
---|
| 2283 | class subtract_with_carry_01; |
---|
| 2284 | |
---|
| 2285 | template<class UniformRandomNumberGenerator, int p, int r> |
---|
| 2286 | class discard_block; |
---|
| 2287 | |
---|
| 2288 | template<class UniformRandomNumberGenerator1, int s1, |
---|
| 2289 | class UniformRandomNumberGenerator2, int s2> |
---|
| 2290 | class xor_combine; |
---|
| 2291 | |
---|
| 2292 | class random_device; |
---|
| 2293 | |
---|
| 2294 | template<class IntType = int> |
---|
| 2295 | class uniform_int; |
---|
| 2296 | |
---|
| 2297 | template<class RealType = double> |
---|
| 2298 | class bernoulli_distribution; |
---|
| 2299 | |
---|
| 2300 | template<class IntType = int, class RealType = double> |
---|
| 2301 | class geometric_distribution; |
---|
| 2302 | |
---|
| 2303 | template<class IntType = int, class RealType = double> |
---|
| 2304 | class poisson_distribution; |
---|
| 2305 | |
---|
| 2306 | template<class IntType = int, class RealType = double> |
---|
| 2307 | class binomial_distribution; |
---|
| 2308 | |
---|
| 2309 | template<class RealType = double> |
---|
| 2310 | class uniform_real; |
---|
| 2311 | |
---|
| 2312 | template<class RealType = double> |
---|
| 2313 | class exponential_distribution; |
---|
| 2314 | |
---|
| 2315 | template<class RealType = double> |
---|
| 2316 | class normal_distribution; |
---|
| 2317 | |
---|
| 2318 | template<class RealType = double> |
---|
| 2319 | class gamma_distribution; |
---|
| 2320 | |
---|
| 2321 | } // namespace std |
---|
| 2322 | </pre> |
---|
| 2323 | |
---|
| 2324 | <h3>Class template <code>variate_generator</code></h3>A |
---|
| 2325 | <code>variate_generator</code> produces random numbers, drawing randomness |
---|
| 2326 | from an underlying uniform random number generator and shaping the |
---|
| 2327 | distribution of the numbers corresponding to a distribution function. |
---|
| 2328 | <pre> |
---|
| 2329 | template<class Engine, class Distribution> |
---|
| 2330 | class variate_generator |
---|
| 2331 | { |
---|
| 2332 | public: |
---|
| 2333 | typedef Engine engine_type; |
---|
| 2334 | typedef /* <em>implementation defined</em> */ engine_value_type; |
---|
| 2335 | typedef Distribution distribution_type; |
---|
| 2336 | typedef typename Distribution::result_type result_type; |
---|
| 2337 | |
---|
| 2338 | variate_generator(engine_type eng, distribution_type d); |
---|
| 2339 | |
---|
| 2340 | result_type operator()(); |
---|
| 2341 | template<class T> result_type operator()(T value); |
---|
| 2342 | |
---|
| 2343 | engine_value_type& engine(); |
---|
| 2344 | const engine_value_type& engine() const; |
---|
| 2345 | |
---|
| 2346 | distribution_type& distribution(); |
---|
| 2347 | const distribution_type& distribution() const; |
---|
| 2348 | |
---|
| 2349 | result_type min() const; |
---|
| 2350 | result_type max() const; |
---|
| 2351 | }; |
---|
| 2352 | </pre>The template argument for the parameter <code>Engine</code> shall be of |
---|
| 2353 | the form <code><em>U</em></code>, <code><em>U</em>&</code>, or <code><em> |
---|
| 2354 | U</em>*</code>, where <code><em>U</em></code> denotes a class that |
---|
| 2355 | satisfies all the requirements of a uniform random number generator. The |
---|
| 2356 | member <code>engine_value_type</code> shall name <code><em>U</em></code>. |
---|
| 2357 | |
---|
| 2358 | <p>Specializations of <code>variate_generator</code> satisfy the |
---|
| 2359 | requirements of CopyConstructible. They also satisfy the requirements of |
---|
| 2360 | Assignable unless the template parameter <code>Engine</code> is of the form |
---|
| 2361 | <code><em>U</em>&</code>.</p> |
---|
| 2362 | |
---|
| 2363 | <p>The complexity of all functions specified in this section is constant. |
---|
| 2364 | No function described in this section except the constructor throws an |
---|
| 2365 | exception.</p> |
---|
| 2366 | <pre> |
---|
| 2367 | variate_generator(engine_type eng, distribution_type d) |
---|
| 2368 | </pre><strong>Effects:</strong> Constructs a <code>variate_generator</code> |
---|
| 2369 | object with the associated uniform random number generator <code>eng</code> |
---|
| 2370 | and the associated random distribution <code>d</code>.<br> |
---|
| 2371 | <strong>Throws:</strong> If and what the copy constructor of Engine or |
---|
| 2372 | Distribution throws. |
---|
| 2373 | <pre> |
---|
| 2374 | result_type operator()() |
---|
| 2375 | </pre><strong>Returns:</strong> <code>distribution()(e)</code><br> |
---|
| 2376 | <strong>Notes:</strong> The sequence of numbers produced by the uniform |
---|
| 2377 | random number generator <code>e</code>, s<sub>e</sub>, is obtained from the |
---|
| 2378 | sequence of numbers produced by the associated uniform random number |
---|
| 2379 | generator <code>eng</code>, s<sub>eng</sub>, as follows: Consider the |
---|
| 2380 | values of <code>numeric_limits<<em>T</em>>::is_integer</code> for |
---|
| 2381 | <code><em>T</em></code> both <code>Distribution::input_type</code> and |
---|
| 2382 | <code>engine_value_type::result_type</code>. If the values for both types |
---|
| 2383 | are <code>true</code>, then s<sub>e</sub> is identical to s<sub>eng</sub>. |
---|
| 2384 | Otherwise, if the values for both types are <code>false</code>, then the |
---|
| 2385 | numbers in s<sub>eng</sub> are divided by |
---|
| 2386 | <code>engine().max()-engine().min()</code> to obtain the numbers in |
---|
| 2387 | s<sub>e</sub>. Otherwise, if the value for |
---|
| 2388 | <code>engine_value_type::result_type</code> is <code>true</code> and the |
---|
| 2389 | value for <code>Distribution::input_type</code> is <code>false</code>, then |
---|
| 2390 | the numbers in s<sub>eng</sub> are divided by |
---|
| 2391 | <code>engine().max()-engine().min()+1</code> to obtain the numbers in |
---|
| 2392 | s<sub>e</sub>. Otherwise, the mapping from s<sub>eng</sub> to s<sub>e</sub> |
---|
| 2393 | is implementation-defined. In all cases, an implicit conversion from |
---|
| 2394 | <code>engine_value_type::result_type</code> to |
---|
| 2395 | <code>Distribution::input_type</code> is performed. If such a conversion |
---|
| 2396 | does not exist, the program is ill-formed. |
---|
| 2397 | <pre> |
---|
| 2398 | template<class T> result_type operator()(T value) |
---|
| 2399 | </pre><strong>Returns:</strong> <code>distribution()(e, value)</code>. For |
---|
| 2400 | the semantics of <code>e</code>, see the description of |
---|
| 2401 | <code>operator()()</code>. |
---|
| 2402 | <pre> |
---|
| 2403 | engine_value_type& engine() |
---|
| 2404 | </pre><strong>Returns:</strong> A reference to the associated uniform random |
---|
| 2405 | number generator. |
---|
| 2406 | <pre> |
---|
| 2407 | const engine_value_type& engine() const |
---|
| 2408 | </pre><strong>Returns:</strong> A reference to the associated uniform random |
---|
| 2409 | number generator. |
---|
| 2410 | <pre> |
---|
| 2411 | distribution_type& distribution() |
---|
| 2412 | </pre><strong>Returns:</strong> A reference to the associated random |
---|
| 2413 | distribution. |
---|
| 2414 | <pre> |
---|
| 2415 | const distribution_type& distribution() const |
---|
| 2416 | </pre><strong>Returns:</strong> A reference to the associated random |
---|
| 2417 | distribution. |
---|
| 2418 | <pre> |
---|
| 2419 | result_type min() const |
---|
| 2420 | </pre><strong>Precondition:</strong> <code>distribution().min()</code> is |
---|
| 2421 | well-formed<br> |
---|
| 2422 | <strong>Returns:</strong> <code>distribution().min()</code> |
---|
| 2423 | <pre> |
---|
| 2424 | result_type max() const |
---|
| 2425 | </pre><strong>Precondition:</strong> <code>distribution().max()</code> is |
---|
| 2426 | well-formed<br> |
---|
| 2427 | <strong>Returns:</strong> <code>distribution().max()</code> |
---|
| 2428 | |
---|
| 2429 | <h3>Random number engine class templates</h3>Except where specified |
---|
| 2430 | otherwise, the complexity of all functions specified in the following |
---|
| 2431 | sections is constant. No function described in this section except the |
---|
| 2432 | constructor and seed functions taking an iterator range [it1,it2) throws an |
---|
| 2433 | exception. |
---|
| 2434 | |
---|
| 2435 | <p>The class templates specified in this section satisfy all the |
---|
| 2436 | requirements of a pseudo-random number engine (given in tables in section |
---|
| 2437 | x.x), except where specified otherwise. Descriptions are provided here only |
---|
| 2438 | for operations on the engines that are not described in one of these tables |
---|
| 2439 | or for operations where there is additional semantic information.</p> |
---|
| 2440 | |
---|
| 2441 | <p>All members declared <code>static const</code> in any of the following |
---|
| 2442 | class templates shall be defined in such a way that they are usable as |
---|
| 2443 | integral constant expressions.</p> |
---|
| 2444 | |
---|
| 2445 | <h4>Class template <code>linear_congruential</code></h4>A |
---|
| 2446 | <code>linear_congruential</code> engine produces random numbers using a |
---|
| 2447 | linear function x(i+1) := (a * x(i) + c) mod m. |
---|
| 2448 | <pre> |
---|
| 2449 | namespace std { |
---|
| 2450 | template<class IntType, IntType a, IntType c, IntType m> |
---|
| 2451 | class linear_congruential |
---|
| 2452 | { |
---|
| 2453 | public: |
---|
| 2454 | // <em>types</em> |
---|
| 2455 | typedef IntType result_type; |
---|
| 2456 | |
---|
| 2457 | // <em>parameter values</em> |
---|
| 2458 | static const IntType multiplier = a; |
---|
| 2459 | static const IntType increment = c; |
---|
| 2460 | static const IntType modulus = m; |
---|
| 2461 | |
---|
| 2462 | // <em> constructors and member function</em> |
---|
| 2463 | explicit linear_congruential(IntType x0 = 1); |
---|
| 2464 | template<class In> linear_congruential(In& first, In last); |
---|
| 2465 | void seed(IntType x0 = 1); |
---|
| 2466 | template<class In> void seed(In& first, In last); |
---|
| 2467 | result_type min() const; |
---|
| 2468 | result_type max() const; |
---|
| 2469 | result_type operator()(); |
---|
| 2470 | }; |
---|
| 2471 | |
---|
| 2472 | template<class IntType, IntType a, IntType c, IntType m> |
---|
| 2473 | bool operator==(const linear_congruential<IntType, a, c, m>& x, |
---|
| 2474 | const linear_congruential<IntType, a, c, m>& y); |
---|
| 2475 | template<class IntType, IntType a, IntType c, IntType m> |
---|
| 2476 | bool operator!=(const linear_congruential<IntType, a, c, m>& x, |
---|
| 2477 | const linear_congruential<IntType, a, c, m>& y); |
---|
| 2478 | |
---|
| 2479 | template<class CharT, class traits, |
---|
| 2480 | class IntType, IntType a, IntType c, IntType m> |
---|
| 2481 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 2482 | const linear_congruential<IntType, a, c, m>& x); |
---|
| 2483 | template<class CharT, class traits, |
---|
| 2484 | class IntType, IntType a, IntType c, IntType m> |
---|
| 2485 | basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is, |
---|
| 2486 | linear_congruential<IntType, a, c, m>& x); |
---|
| 2487 | } |
---|
| 2488 | </pre>The template parameter <code>IntType</code> shall denote an integral |
---|
| 2489 | type large enough to store values up to (m-1). If the template parameter |
---|
| 2490 | <code>m</code> is 0, the behaviour is implementation-defined. Otherwise, the |
---|
| 2491 | template parameters <code>a</code> and <code>c</code> shall be less than m. |
---|
| 2492 | |
---|
| 2493 | <p>The size of the state x(i) is 1.</p> |
---|
| 2494 | <pre> |
---|
| 2495 | explicit linear_congruential(IntType x0 = 1) |
---|
| 2496 | </pre><strong>Requires:</strong> <code>c > 0 || (x0 % m) > 0</code><br> |
---|
| 2497 | |
---|
| 2498 | <strong>Effects:</strong> Constructs a <code>linear_congruential</code> |
---|
| 2499 | engine with state x(0) := <code>x0</code> mod m. |
---|
| 2500 | <pre> |
---|
| 2501 | void seed(IntType x0 = 1) |
---|
| 2502 | </pre><strong>Requires:</strong> <code>c > 0 || (x0 % m) > 0</code><br> |
---|
| 2503 | |
---|
| 2504 | <strong>Effects:</strong> Sets the state x(i) of the engine to |
---|
| 2505 | <code>x0</code> mod m. |
---|
| 2506 | <pre> |
---|
| 2507 | template<class In> linear_congruential(In& first, In last) |
---|
| 2508 | </pre><strong>Requires:</strong> <code>c > 0 || *first > 0</code><br> |
---|
| 2509 | <strong>Effects:</strong> Sets the state x(i) of the engine to |
---|
| 2510 | <code>*first</code> mod m.<br> |
---|
| 2511 | <strong>Complexity:</strong> Exactly one dereference of |
---|
| 2512 | <code>*first</code>. |
---|
| 2513 | <pre> |
---|
| 2514 | template<class CharT, class traits, |
---|
| 2515 | class IntType, IntType a, IntType c, IntType m> |
---|
| 2516 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 2517 | const linear_congruential<IntType, a, c, m>& x); |
---|
| 2518 | </pre><strong>Effects:</strong> Writes x(i) to <code>os</code>. |
---|
| 2519 | |
---|
| 2520 | <h4>Class template <code>mersenne_twister</code></h4>A |
---|
| 2521 | <code>mersenne_twister</code> engine produces random numbers o(x(i)) using |
---|
| 2522 | the following computation, performed modulo 2<sup>w</sup>. <code>um</code> |
---|
| 2523 | is a value with only the upper <code>w-r</code> bits set in its binary |
---|
| 2524 | representation. <code>lm</code> is a value with only its lower |
---|
| 2525 | <code>r</code> bits set in its binary representation. <em>rshift</em> is a |
---|
| 2526 | bitwise right shift with zero-valued bits appearing in the high bits of the |
---|
| 2527 | result. <em>lshift</em> is a bitwise left shift with zero-valued bits |
---|
| 2528 | appearing in the low bits of the result. |
---|
| 2529 | |
---|
| 2530 | <ul> |
---|
| 2531 | <li>y(i) = (x(i-n) <em>bitand</em> um) | (x(i-(n-1)) <em>bitand</em> |
---|
| 2532 | lm)</li> |
---|
| 2533 | |
---|
| 2534 | <li>If the lowest bit of the binary representation of y(i) is set, x(i) = |
---|
| 2535 | x(i-(n-m)) <em>xor</em> (y(i) <em>rshift</em> 1) <em>xor</em> a; |
---|
| 2536 | otherwise x(i) = x(i-(n-m)) <em>xor</em> (y(i) <em>rshift</em> 1).</li> |
---|
| 2537 | |
---|
| 2538 | <li>z1(i) = x(i) <em>xor</em> ( x(i) <em>rshift</em> u )</li> |
---|
| 2539 | |
---|
| 2540 | <li>z2(i) = z1(i) <em>xor</em> ( (z1(i) <em>lshift</em> s) |
---|
| 2541 | <em>bitand</em> b )</li> |
---|
| 2542 | |
---|
| 2543 | <li>z3(i) = z2(i) <em>xor</em> ( (z2(i) <em>lshift</em> t) |
---|
| 2544 | <em>bitand</em> c )</li> |
---|
| 2545 | |
---|
| 2546 | <li>o(x(i)) = z3(i) <em>xor</em> ( z3(i) <em>rshift</em> l )</li> |
---|
| 2547 | </ul> |
---|
| 2548 | <pre> |
---|
| 2549 | namespace std { |
---|
| 2550 | template<class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2551 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2552 | class mersenne_twister |
---|
| 2553 | { |
---|
| 2554 | public: |
---|
| 2555 | // <em>types</em> |
---|
| 2556 | typedef UIntType result_type; |
---|
| 2557 | |
---|
| 2558 | // <em>parameter values</em> |
---|
| 2559 | static const int word_size = w; |
---|
| 2560 | static const int state_size = n; |
---|
| 2561 | static const int shift_size = m; |
---|
| 2562 | static const int mask_bits = r; |
---|
| 2563 | static const UIntType parameter_a = a; |
---|
| 2564 | static const int output_u = u; |
---|
| 2565 | static const int output_s = s; |
---|
| 2566 | static const UIntType output_b = b; |
---|
| 2567 | static const int output_t = t; |
---|
| 2568 | static const UIntType output_c = c; |
---|
| 2569 | static const int output_l = l; |
---|
| 2570 | |
---|
| 2571 | // <em> constructors and member function</em> |
---|
| 2572 | mersenne_twister(); |
---|
| 2573 | explicit mersenne_twister(UIntType value); |
---|
| 2574 | template<class In> mersenne_twister(In& first, In last); |
---|
| 2575 | void seed(); |
---|
| 2576 | void seed(UIntType value); |
---|
| 2577 | template<class In> void seed(In& first, In last); |
---|
| 2578 | result_type min() const; |
---|
| 2579 | result_type max() const; |
---|
| 2580 | result_type operator()(); |
---|
| 2581 | }; |
---|
| 2582 | |
---|
| 2583 | template<class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2584 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2585 | bool operator==(const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& y, |
---|
| 2586 | const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x); |
---|
| 2587 | template<class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2588 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2589 | bool operator!=(const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& y, |
---|
| 2590 | const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x); |
---|
| 2591 | |
---|
| 2592 | template<class CharT, class traits, |
---|
| 2593 | class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2594 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2595 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 2596 | const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x); |
---|
| 2597 | template<class CharT, class traits, |
---|
| 2598 | class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2599 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2600 | basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is, |
---|
| 2601 | mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x); |
---|
| 2602 | } |
---|
| 2603 | </pre>The template parameter <code>UIntType</code> shall denote an unsigned |
---|
| 2604 | integral type large enough to store values up to 2<sup>w</sup>-1. Also, the |
---|
| 2605 | following relations shall hold: 1<=m<=n. 0<=r,u,s,t,l<=w. |
---|
| 2606 | 0<=a,b,c<=2<sup>w</sup>-1. |
---|
| 2607 | |
---|
| 2608 | <p>The size of the state x(i) is <code>n</code>.</p> |
---|
| 2609 | <pre> |
---|
| 2610 | mersenne_twister() |
---|
| 2611 | </pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> |
---|
| 2612 | engine and invokes <code>seed()</code>. |
---|
| 2613 | <pre> |
---|
| 2614 | explicit mersenne_twister(result_type value) |
---|
| 2615 | </pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> |
---|
| 2616 | engine and invokes <code>seed(value)</code>. |
---|
| 2617 | <pre> |
---|
| 2618 | template<class In> mersenne_twister(In& first, In last) |
---|
| 2619 | </pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> |
---|
| 2620 | engine and invokes <code>seed(first, last)</code>. |
---|
| 2621 | <pre> |
---|
| 2622 | void seed() |
---|
| 2623 | </pre><strong>Effects:</strong> Invokes <code>seed(4357)</code>. |
---|
| 2624 | <pre> |
---|
| 2625 | void seed(result_type value) |
---|
| 2626 | </pre><strong>Requires:</strong> <code>value > 0</code><br> |
---|
| 2627 | <strong>Effects:</strong> With a linear congruential generator l(i) having |
---|
| 2628 | parameters m<sub>l</sub> = 2<sup>32</sup>, a<sub>l</sub> = 69069, |
---|
| 2629 | c<sub>l</sub> = 0, and l(0) = <code>value</code>, sets x(-n) ... x(-1) to |
---|
| 2630 | l(1) ... l(n), respectively.<br> |
---|
| 2631 | <strong>Complexity:</strong> O(n) |
---|
| 2632 | <pre> |
---|
| 2633 | template<class In> void seed(In& first, In last) |
---|
| 2634 | </pre><strong>Effects:</strong> Given the values z<sub>0</sub> ... |
---|
| 2635 | z<sub>n-1</sub> obtained by dereferencing [first, first+n), sets x(-n) ... |
---|
| 2636 | x(-1) to z<sub>0</sub> mod 2<sup>w</sup> ... z<sub>n-1</sub> mod |
---|
| 2637 | 2<sup>w</sup>.<br> |
---|
| 2638 | <strong>Complexity:</strong> Exactly <code>n</code> dereferences of |
---|
| 2639 | <code>first</code>. |
---|
| 2640 | <pre> |
---|
| 2641 | template<class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2642 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2643 | bool operator==(const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& y, |
---|
| 2644 | const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x) |
---|
| 2645 | </pre><strong>Returns:</strong> x(i-n) == y(j-n) and ... and x(i-1) == |
---|
| 2646 | y(j-1)<br> |
---|
| 2647 | <strong>Notes:</strong> Assumes the next output of <code>x</code> is |
---|
| 2648 | o(x(i)) and the next output of <code>y</code> is o(y(j)).<br> |
---|
| 2649 | <strong>Complexity:</strong> O(n) |
---|
| 2650 | <pre> |
---|
| 2651 | template<class CharT, class traits, |
---|
| 2652 | class UIntType, int w, int n, int m, int r, UIntType a, int u, |
---|
| 2653 | int s, UIntType b, int t, UIntType c, int l> |
---|
| 2654 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 2655 | const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x) |
---|
| 2656 | </pre><strong>Effects:</strong> Writes x(i-n), ... x(i-1) to <code>os</code>, |
---|
| 2657 | in that order.<br> |
---|
| 2658 | <strong>Complexity:</strong> O(n) |
---|
| 2659 | |
---|
| 2660 | <h4>Class template <code>subtract_with_carry</code></h4>A |
---|
| 2661 | <code>subtract_with_carry</code> engine produces integer random numbers |
---|
| 2662 | using x(i) = (x(i-s) - x(i-r) - carry(i-1)) mod m; carry(i) = 1 if x(i-s) - |
---|
| 2663 | x(i-r) - carry(i-1) < 0, else carry(i) = 0. |
---|
| 2664 | <pre> |
---|
| 2665 | namespace std { |
---|
| 2666 | template<class IntType, IntType m, int s, int r> |
---|
| 2667 | class subtract_with_carry |
---|
| 2668 | { |
---|
| 2669 | public: |
---|
| 2670 | // <em>types</em> |
---|
| 2671 | typedef IntType result_type; |
---|
| 2672 | |
---|
| 2673 | // <em>parameter values</em> |
---|
| 2674 | static const IntType modulus = m; |
---|
| 2675 | static const int long_lag = r; |
---|
| 2676 | static const int short_lag = s; |
---|
| 2677 | |
---|
| 2678 | // <em> constructors and member function</em> |
---|
| 2679 | subtract_with_carry(); |
---|
| 2680 | explicit subtract_with_carry(IntType value); |
---|
| 2681 | template<class In> subtract_with_carry(In& first, In last); |
---|
| 2682 | void seed(IntType value = 19780503); |
---|
| 2683 | template<class In> void seed(In& first, In last); |
---|
| 2684 | result_type min() const; |
---|
| 2685 | result_type max() const; |
---|
| 2686 | result_type operator()(); |
---|
| 2687 | }; |
---|
| 2688 | template<class IntType, IntType m, int s, int r> |
---|
| 2689 | bool operator==(const subtract_with_carry<IntType, m, s, r> & x, |
---|
| 2690 | const subtract_with_carry<IntType, m, s, r> & y); |
---|
| 2691 | |
---|
| 2692 | template<class IntType, IntType m, int s, int r> |
---|
| 2693 | bool operator!=(const subtract_with_carry<IntType, m, s, r> & x, |
---|
| 2694 | const subtract_with_carry<IntType, m, s, r> & y); |
---|
| 2695 | |
---|
| 2696 | template<class CharT, class Traits, |
---|
| 2697 | class IntType, IntType m, int s, int r> |
---|
| 2698 | std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os, |
---|
| 2699 | const subtract_with_carry<IntType, m, s, r>& f); |
---|
| 2700 | |
---|
| 2701 | template<class CharT, class Traits, |
---|
| 2702 | class IntType, IntType m, int s, int r> |
---|
| 2703 | std::basic_istream<CharT,Traits>& operator>>(std::basic_istream<CharT,Traits>& is, |
---|
| 2704 | subtract_with_carry<IntType, m, s, r>& f); |
---|
| 2705 | } |
---|
| 2706 | </pre>The template parameter <code>IntType</code> shall denote a signed |
---|
| 2707 | integral type large enough to store values up to m-1. The following relation |
---|
| 2708 | shall hold: 0<s<r. Let w the number of bits in the binary |
---|
| 2709 | representation of m. |
---|
| 2710 | |
---|
| 2711 | <p>The size of the state is <code>r</code>.</p> |
---|
| 2712 | <pre> |
---|
| 2713 | subtract_with_carry() |
---|
| 2714 | </pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code> |
---|
| 2715 | engine and invokes <code>seed()</code>. |
---|
| 2716 | <pre> |
---|
| 2717 | explicit subtract_with_carry(IntType value) |
---|
| 2718 | </pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code> |
---|
| 2719 | engine and invokes <code>seed(value)</code>. |
---|
| 2720 | <pre> |
---|
| 2721 | template<class In> subtract_with_carry(In& first, In last) |
---|
| 2722 | </pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code> |
---|
| 2723 | engine and invokes <code>seed(first, last)</code>. |
---|
| 2724 | <pre> |
---|
| 2725 | void seed(IntType value = 19780503) |
---|
| 2726 | </pre><strong>Requires:</strong> <code>value > 0</code><br> |
---|
| 2727 | <strong>Effects:</strong> With a linear congruential generator l(i) having |
---|
| 2728 | parameters m<sub>l</sub> = 2147483563, a<sub>l</sub> = 40014, c<sub>l</sub> |
---|
| 2729 | = 0, and l(0) = <code>value</code>, sets x(-r) ... x(-1) to l(1) mod m ... |
---|
| 2730 | l(r) mod m, respectively. If x(-1) == 0, sets carry(-1) = 1, else sets |
---|
| 2731 | carry(-1) = 0.<br> |
---|
| 2732 | <strong>Complexity:</strong> O(r) |
---|
| 2733 | <pre> |
---|
| 2734 | template<class In> void seed(In& first, In last) |
---|
| 2735 | </pre><strong>Effects:</strong> With n=w/32+1 (rounded downward) and given |
---|
| 2736 | the values z<sub>0</sub> ... z<sub>n*r-1</sub> obtained by dereferencing |
---|
| 2737 | [first, first+n*r), sets x(-r) ... x(-1) to (z<sub>0</sub> * 2<sup>32</sup> + |
---|
| 2738 | ... + z<sub>n-1</sub> * 2<sup>32*(n-1)</sup>) mod m ... (z<sub>(r-1)*n</sub> |
---|
| 2739 | * 2<sup>32</sup> + ... + z<sub>r-1</sub> * 2<sup>32*(n-1)</sup>) mod m. If |
---|
| 2740 | x(-1) == 0, sets carry(-1) = 1, else sets carry(-1) = 0.<br> |
---|
| 2741 | <strong>Complexity:</strong> Exactly <code>r*n</code> dereferences of |
---|
| 2742 | <code>first</code>. |
---|
| 2743 | <pre> |
---|
| 2744 | template<class IntType, IntType m, int s, int r> |
---|
| 2745 | bool operator==(const subtract_with_carry<IntType, m, s, r> & x, |
---|
| 2746 | const subtract_with_carry<IntType, m, s, r> & y) |
---|
| 2747 | </pre><strong>Returns:</strong> x(i-r) == y(j-r) and ... and x(i-1) == |
---|
| 2748 | y(j-1).<br> |
---|
| 2749 | <strong>Notes:</strong> Assumes the next output of <code>x</code> is x(i) |
---|
| 2750 | and the next output of <code>y</code> is y(j).<br> |
---|
| 2751 | <strong>Complexity:</strong> O(r) |
---|
| 2752 | <pre> |
---|
| 2753 | template<class CharT, class Traits, |
---|
| 2754 | class IntType, IntType m, int s, int r> |
---|
| 2755 | std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os, |
---|
| 2756 | const subtract_with_carry<IntType, m, s, r>& f) |
---|
| 2757 | </pre><strong>Effects:</strong> Writes x(i-r) ... x(i-1), carry(i-1) to |
---|
| 2758 | <code>os</code>, in that order.<br> |
---|
| 2759 | <strong>Complexity:</strong> O(r) |
---|
| 2760 | |
---|
| 2761 | <h4>Class template <code>subtract_with_carry_01</code></h4>A |
---|
| 2762 | <code>subtract_with_carry_01</code> engine produces floating-point random |
---|
| 2763 | numbers using x(i) = (x(i-s) - x(i-r) - carry(i-1)) mod 1; carry(i) = |
---|
| 2764 | 2<sup>-w</sup> if x(i-s) - x(i-r) - carry(i-1) < 0, else carry(i) = 0. |
---|
| 2765 | <pre> |
---|
| 2766 | namespace std { |
---|
| 2767 | template<class RealType, int w, int s, int r> |
---|
| 2768 | class subtract_with_carry_01 |
---|
| 2769 | { |
---|
| 2770 | public: |
---|
| 2771 | // <em>types</em> |
---|
| 2772 | typedef RealType result_type; |
---|
| 2773 | |
---|
| 2774 | // <em>parameter values</em> |
---|
| 2775 | static const int word_size = w; |
---|
| 2776 | static const int long_lag = r; |
---|
| 2777 | static const int short_lag = s; |
---|
| 2778 | |
---|
| 2779 | // <em> constructors and member function</em> |
---|
| 2780 | subtract_with_carry_01(); |
---|
| 2781 | explicit subtract_with_carry_01(unsigned int value); |
---|
| 2782 | template<class In> subtract_with_carry_01(In& first, In last); |
---|
| 2783 | void seed(unsigned int value = 19780503); |
---|
| 2784 | template<class In> void seed(In& first, In last); |
---|
| 2785 | result_type min() const; |
---|
| 2786 | result_type max() const; |
---|
| 2787 | result_type operator()(); |
---|
| 2788 | }; |
---|
| 2789 | template<class RealType, int w, int s, int r> |
---|
| 2790 | bool operator==(const subtract_with_carry_01<RealType, w, s, r> x, |
---|
| 2791 | const subtract_with_carry_01<RealType, w, s, r> y); |
---|
| 2792 | |
---|
| 2793 | template<class RealType, int w, int s, int r> |
---|
| 2794 | bool operator!=(const subtract_with_carry_01<RealType, w, s, r> x, |
---|
| 2795 | const subtract_with_carry_01<RealType, w, s, r> y); |
---|
| 2796 | |
---|
| 2797 | template<class CharT, class Traits, |
---|
| 2798 | class RealType, int w, int s, int r> |
---|
| 2799 | std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os, |
---|
| 2800 | const subtract_with_carry_01<RealType, w, s, r>& f); |
---|
| 2801 | |
---|
| 2802 | template<class CharT, class Traits, |
---|
| 2803 | class RealType, int w, int s, int r> |
---|
| 2804 | std::basic_istream<CharT,Traits>& operator>>(std::basic_istream<CharT,Traits>& is, |
---|
| 2805 | subtract_with_carry_01<RealType, w, s, r>& f); |
---|
| 2806 | } |
---|
| 2807 | </pre>The following relation shall hold: 0<s<r. |
---|
| 2808 | |
---|
| 2809 | <p>The size of the state is <code>r</code>.</p> |
---|
| 2810 | <pre> |
---|
| 2811 | subtract_with_carry_01() |
---|
| 2812 | </pre><strong>Effects:</strong> Constructs a |
---|
| 2813 | <code>subtract_with_carry_01</code> engine and invokes <code>seed()</code>. |
---|
| 2814 | <pre> |
---|
| 2815 | explicit subtract_with_carry_01(unsigned int value) |
---|
| 2816 | </pre><strong>Effects:</strong> Constructs a |
---|
| 2817 | <code>subtract_with_carry_01</code> engine and invokes |
---|
| 2818 | <code>seed(value)</code>. |
---|
| 2819 | <pre> |
---|
| 2820 | template<class In> subtract_with_carry_01(In& first, In last) |
---|
| 2821 | </pre><strong>Effects:</strong> Constructs a |
---|
| 2822 | <code>subtract_with_carry_01</code> engine and invokes <code>seed(first, |
---|
| 2823 | last)</code>. |
---|
| 2824 | <pre> |
---|
| 2825 | void seed(unsigned int value = 19780503) |
---|
| 2826 | </pre><strong>Effects:</strong> With a linear congruential generator l(i) |
---|
| 2827 | having parameters m = 2147483563, a = 40014, c = 0, and l(0) = |
---|
| 2828 | <code>value</code>, sets x(-r) ... x(-1) to (l(1)*2<sup>-w</sup>) mod 1 ... |
---|
| 2829 | (l(r)*2<sup>-w</sup>) mod 1, respectively. If x(-1) == 0, sets carry(-1) = |
---|
| 2830 | 2<sup>-w</sup>, else sets carry(-1) = 0.<br> |
---|
| 2831 | <strong>Complexity:</strong> O(r) |
---|
| 2832 | <pre> |
---|
| 2833 | template<class In> void seed(In& first, In last) |
---|
| 2834 | </pre><strong>Effects:</strong> With n=w/32+1 (rounded downward) and given |
---|
| 2835 | the values z<sub>0</sub> ... z<sub>n*r-1</sub> obtained by dereferencing |
---|
| 2836 | [first, first+n*r), sets x(-r) ... x(-1) to (z<sub>0</sub> * 2<sup>32</sup> + |
---|
| 2837 | ... + z<sub>n-1</sub> * 2<sup>32*(n-1)</sup>) * 2<sup>-w</sup> mod 1 ... |
---|
| 2838 | (z<sub>(r-1)*n</sub> * 2<sup>32</sup> + ... + z<sub>r-1</sub> * |
---|
| 2839 | 2<sup>32*(n-1)</sup>) * 2<sup>-w</sup> mod 1. If x(-1) == 0, sets carry(-1) = |
---|
| 2840 | 2<sup>-w</sup>, else sets carry(-1) = 0.<br> |
---|
| 2841 | <strong>Complexity:</strong> O(r*n) |
---|
| 2842 | <pre> |
---|
| 2843 | template<class RealType, int w, int s, int r> |
---|
| 2844 | bool operator==(const subtract_with_carry<RealType, w, s, r> x, |
---|
| 2845 | const subtract_with_carry<RealType, w, s, r> y); |
---|
| 2846 | </pre><strong>Returns:</strong> true, if and only if x(i-r) == y(j-r) and ... |
---|
| 2847 | and x(i-1) == y(j-1).<br> |
---|
| 2848 | <strong>Complexity:</strong> O(r) |
---|
| 2849 | <pre> |
---|
| 2850 | template<class CharT, class Traits, |
---|
| 2851 | class RealType, int w, int s, int r> |
---|
| 2852 | std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os, |
---|
| 2853 | const subtract_with_carry<RealType, w, s, r>& f); |
---|
| 2854 | </pre><strong>Effects:</strong> Write x(i-r)*2<sup>w</sup> ... |
---|
| 2855 | x(i-1)*2<sup>w</sup>, carry(i-1)*2<sup>w</sup> to <code>os</code>, in that |
---|
| 2856 | order.<br> |
---|
| 2857 | <strong>Complexity:</strong> O(r) |
---|
| 2858 | |
---|
| 2859 | <h4>Class template <code>discard_block</code></h4>A |
---|
| 2860 | <code>discard_block</code> engine produces random numbers from some base |
---|
| 2861 | engine by discarding blocks of data. |
---|
| 2862 | <pre> |
---|
| 2863 | namespace std { |
---|
| 2864 | template<class UniformRandomNumberGenerator, int p, int r> |
---|
| 2865 | class discard_block |
---|
| 2866 | { |
---|
| 2867 | public: |
---|
| 2868 | // <em>types</em> |
---|
| 2869 | typedef UniformRandomNumberGenerator base_type; |
---|
| 2870 | typedef typename base_type::result_type result_type; |
---|
| 2871 | |
---|
| 2872 | // <em>parameter values</em> |
---|
| 2873 | static const int block_size = p; |
---|
| 2874 | static const int used_block = r; |
---|
| 2875 | |
---|
| 2876 | // <em> constructors and member function</em> |
---|
| 2877 | discard_block(); |
---|
| 2878 | explicit discard_block(const base_type & rng); |
---|
| 2879 | template<class In> discard_block(In& first, In last); |
---|
| 2880 | void seed(); |
---|
| 2881 | template<class In> void seed(In& first, In last); |
---|
| 2882 | const base_type& base() const; |
---|
| 2883 | result_type min() const; |
---|
| 2884 | result_type max() const; |
---|
| 2885 | result_type operator()(); |
---|
| 2886 | private: |
---|
| 2887 | // base_type b; <em>exposition only</em> |
---|
| 2888 | // int n; <em>exposition only</em> |
---|
| 2889 | }; |
---|
| 2890 | template<class UniformRandomNumberGenerator, int p, int r> |
---|
| 2891 | bool operator==(const discard_block<UniformRandomNumberGenerator,p,r> & x, |
---|
| 2892 | (const discard_block<UniformRandomNumberGenerator,p,r> & y); |
---|
| 2893 | template<class UniformRandomNumberGenerator, int p, int r, |
---|
| 2894 | typename UniformRandomNumberGenerator::result_type val> |
---|
| 2895 | bool operator!=(const discard_block<UniformRandomNumberGenerator,p,r> & x, |
---|
| 2896 | (const discard_block<UniformRandomNumberGenerator,p,r> & y); |
---|
| 2897 | |
---|
| 2898 | template<class CharT, class traits, |
---|
| 2899 | class UniformRandomNumberGenerator, int p, int r> |
---|
| 2900 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 2901 | const discard_block<UniformRandomNumberGenerator,p,r> & x); |
---|
| 2902 | template<class CharT, class traits, |
---|
| 2903 | class UniformRandomNumberGenerator, int p, int r> |
---|
| 2904 | basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is, |
---|
| 2905 | discard_block<UniformRandomNumberGenerator,p,r> & x); |
---|
| 2906 | |
---|
| 2907 | } |
---|
| 2908 | </pre>The template parameter <code>UniformRandomNumberGenerator</code> shall |
---|
| 2909 | denote a class that satisfies all the requirements of a uniform random number |
---|
| 2910 | generator, given in tables in section x.x. r <= p. The size of the state |
---|
| 2911 | is the size of <code><em>b</em></code> plus 1. |
---|
| 2912 | <pre> |
---|
| 2913 | discard_block() |
---|
| 2914 | </pre><strong>Effects:</strong> Constructs a <code>discard_block</code> |
---|
| 2915 | engine. To construct the subobject <em>b</em>, invokes its default |
---|
| 2916 | constructor. Sets <code>n = 0</code>. |
---|
| 2917 | <pre> |
---|
| 2918 | explicit discard_block(const base_type & rng) |
---|
| 2919 | </pre><strong>Effects:</strong> Constructs a <code>discard_block</code> |
---|
| 2920 | engine. Initializes <em>b</em> with a copy of <code>rng</code>. Sets <code>n |
---|
| 2921 | = 0</code>. |
---|
| 2922 | <pre> |
---|
| 2923 | template<class In> discard_block(In& first, In last) |
---|
| 2924 | </pre><strong>Effects:</strong> Constructs a <code>discard_block</code> |
---|
| 2925 | engine. To construct the subobject <em>b</em>, invokes the <code>b(first, |
---|
| 2926 | last)</code> constructor. Sets <code>n = 0</code>. |
---|
| 2927 | <pre> |
---|
| 2928 | void seed() |
---|
| 2929 | </pre><strong>Effects:</strong> Invokes <code><em>b</em>.seed()</code> and |
---|
| 2930 | sets <code>n = 0</code>. |
---|
| 2931 | <pre> |
---|
| 2932 | template<class In> void seed(In& first, In last) |
---|
| 2933 | </pre><strong>Effects:</strong> Invokes <code><em>b</em>.seed(first, |
---|
| 2934 | last)</code> and sets <code>n = 0</code>. |
---|
| 2935 | <pre> |
---|
| 2936 | const base_type& base() const |
---|
| 2937 | </pre><strong>Returns:</strong> <em>b</em> |
---|
| 2938 | <pre> |
---|
| 2939 | result_type operator()() |
---|
| 2940 | </pre><strong>Effects:</strong> If <em>n</em> >= r, invokes |
---|
| 2941 | <code><em>b</em></code> (p-r) times, discards the values returned, and sets |
---|
| 2942 | <code>n = 0</code>. In any case, then increments <code>n</code> and returns |
---|
| 2943 | <code><em>b()</em></code>. |
---|
| 2944 | <pre> |
---|
| 2945 | template<class CharT, class traits, |
---|
| 2946 | class UniformRandomNumberGenerator, int p, int r> |
---|
| 2947 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 2948 | const discard_block<UniformRandomNumberGenerator,p,r> & x); |
---|
| 2949 | </pre><strong>Effects:</strong> Writes <code><em>b</em></code>, then |
---|
| 2950 | <code><em>n</em></code> to <code>os</code>. |
---|
| 2951 | |
---|
| 2952 | <h4>Class template <code>xor_combine</code></h4>A <code>xor_combine</code> |
---|
| 2953 | engine produces random numbers from two integer base engines by merging |
---|
| 2954 | their random values with bitwise exclusive-or. |
---|
| 2955 | <pre> |
---|
| 2956 | namespace std { |
---|
| 2957 | template<class UniformRandomNumberGenerator1, int s1, |
---|
| 2958 | class UniformRandomNumberGenerator2, int s2> |
---|
| 2959 | class xor_combine |
---|
| 2960 | { |
---|
| 2961 | public: |
---|
| 2962 | // <em>types</em> |
---|
| 2963 | typedef UniformRandomNumberGenerator1 base1_type; |
---|
| 2964 | typedef UniformRandomNumberGenerator2 base2_type; |
---|
| 2965 | typedef typename base_type::result_type result_type; |
---|
| 2966 | |
---|
| 2967 | // <em>parameter values</em> |
---|
| 2968 | static const int shift1 = s1; |
---|
| 2969 | static const int shift2 = s2; |
---|
| 2970 | |
---|
| 2971 | // <em> constructors and member function</em> |
---|
| 2972 | xor_combine(); |
---|
| 2973 | xor_combine(const base1_type & rng1, const base2_type & rng2); |
---|
| 2974 | template<class In> xor_combine(In& first, In last); |
---|
| 2975 | void seed(); |
---|
| 2976 | template<class In> void seed(In& first, In last); |
---|
| 2977 | const base1_type& base1() const; |
---|
| 2978 | const base2_type& base2() const; |
---|
| 2979 | result_type min() const; |
---|
| 2980 | result_type max() const; |
---|
| 2981 | result_type operator()(); |
---|
| 2982 | private: |
---|
| 2983 | // base1_type b1; <em>exposition only</em> |
---|
| 2984 | // base2_type b2; <em>exposition only</em> |
---|
| 2985 | }; |
---|
| 2986 | template<class UniformRandomNumberGenerator1, int s1, |
---|
| 2987 | class UniformRandomNumberGenerator2, int s2> |
---|
| 2988 | bool operator==(const xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 2989 | UniformRandomNumberGenerator2, s2> & x, |
---|
| 2990 | (const xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 2991 | UniformRandomNumberGenerator2, s2> & y); |
---|
| 2992 | template<class UniformRandomNumberGenerator1, int s1, |
---|
| 2993 | class UniformRandomNumberGenerator2, int s2> |
---|
| 2994 | bool operator!=(const xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 2995 | UniformRandomNumberGenerator2, s2> & x, |
---|
| 2996 | (const xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 2997 | UniformRandomNumberGenerator2, s2> & y); |
---|
| 2998 | |
---|
| 2999 | template<class CharT, class traits, |
---|
| 3000 | class UniformRandomNumberGenerator1, int s1, |
---|
| 3001 | class UniformRandomNumberGenerator2, int s2> |
---|
| 3002 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 3003 | const xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 3004 | UniformRandomNumberGenerator2, s2> & x); |
---|
| 3005 | template<class CharT, class traits, |
---|
| 3006 | class UniformRandomNumberGenerator1, int s1, |
---|
| 3007 | class UniformRandomNumberGenerator2, int s2> |
---|
| 3008 | basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is, |
---|
| 3009 | xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 3010 | UniformRandomNumberGenerator2, s2> & x); |
---|
| 3011 | |
---|
| 3012 | } |
---|
| 3013 | </pre>The template parameters <code>UniformRandomNumberGenerator1</code> and |
---|
| 3014 | <code>UniformRandomNumberGenerator1</code> shall denote classes that satisfy |
---|
| 3015 | all the requirements of a uniform random number generator, given in tables in |
---|
| 3016 | section x.x . The size of the state is the size of <code><em>b1</em></code> |
---|
| 3017 | plus the size of <code><em>b2</em></code>. |
---|
| 3018 | <pre> |
---|
| 3019 | xor_combine() |
---|
| 3020 | </pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine. |
---|
| 3021 | To construct each of the subobjects <em>b1</em> and <em>b2</em>, invokes |
---|
| 3022 | their respective default constructors. |
---|
| 3023 | <pre> |
---|
| 3024 | xor_combine(const base1_type & rng1, const base2_type & rng2) |
---|
| 3025 | </pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine. |
---|
| 3026 | Initializes <em>b1</em> with a copy of <code>rng1</code> and <em>b2</em> with |
---|
| 3027 | a copy of <code>rng2</code>. |
---|
| 3028 | <pre> |
---|
| 3029 | template<class In> xor_combine(In& first, In last) |
---|
| 3030 | </pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine. |
---|
| 3031 | To construct the subobject <em>b1</em>, invokes the <code>b1(first, |
---|
| 3032 | last)</code> constructor. Then, to construct the subobject <em>b2</em>, |
---|
| 3033 | invokes the <code>b2(first, last)</code> constructor. |
---|
| 3034 | <pre> |
---|
| 3035 | void seed() |
---|
| 3036 | </pre><strong>Effects:</strong> Invokes <code><em>b1</em>.seed()</code> and |
---|
| 3037 | <code><em>b2</em>.seed()</code>. |
---|
| 3038 | <pre> |
---|
| 3039 | template<class In> void seed(In& first, In last) |
---|
| 3040 | </pre><strong>Effects:</strong> Invokes <code><em>b1</em>.seed(first, |
---|
| 3041 | last)</code>, then invokes <code><em>b2</em>.seed(first, last)</code>. |
---|
| 3042 | <pre> |
---|
| 3043 | const base1_type& base1() const |
---|
| 3044 | </pre><strong>Returns:</strong> <em>b1</em> |
---|
| 3045 | <pre> |
---|
| 3046 | const base2_type& base2() const |
---|
| 3047 | </pre><strong>Returns:</strong> <em>b2</em> |
---|
| 3048 | <pre> |
---|
| 3049 | result_type operator()() |
---|
| 3050 | </pre><strong>Returns:</strong> (<code><em>b1</em>() << s1) ^ |
---|
| 3051 | (<em>b2</em>() << s2)</code>. |
---|
| 3052 | <pre> |
---|
| 3053 | template<class CharT, class traits, |
---|
| 3054 | class UniformRandomNumberGenerator1, int s1, |
---|
| 3055 | class UniformRandomNumberGenerator2, int s2> |
---|
| 3056 | basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os, |
---|
| 3057 | const xor_combine<UniformRandomNumberGenerator1, s1, |
---|
| 3058 | UniformRandomNumberGenerator2, s2> & x); |
---|
| 3059 | </pre><strong>Effects:</strong> Writes <code><em>b1</em></code>, then <code> |
---|
| 3060 | <em>b2</em></code> to <code>os</code>. |
---|
| 3061 | |
---|
| 3062 | <h3>Engines with predefined parameters</h3> |
---|
| 3063 | <pre> |
---|
| 3064 | namespace std { |
---|
| 3065 | typedef linear_congruential</* <em>implementation defined</em> */, 16807, 0, 2147483647> minstd_rand0; |
---|
| 3066 | typedef linear_congruential</* <em>implementation defined</em> */, 48271, 0, 2147483647> minstd_rand; |
---|
| 3067 | |
---|
| 3068 | typedef mersenne_twister</* <em>implementation defined</em> */,32,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18> mt19937; |
---|
| 3069 | |
---|
| 3070 | typedef subtract_with_carry_01<float, 24, 10, 24> ranlux_base_01; |
---|
| 3071 | typedef subtract_with_carry_01<double, 48, 10, 24> ranlux64_base_01; |
---|
| 3072 | |
---|
| 3073 | typedef discard_block<subtract_with_carry</* <em>implementation defined</em> */, (1<<24), 10, 24>, 223, 24> ranlux3; |
---|
| 3074 | typedef discard_block<subtract_with_carry</* <em>implementation defined</em> */, (1<<24), 10, 24>, 389, 24> ranlux4; |
---|
| 3075 | |
---|
| 3076 | typedef discard_block<subtract_with_carry_01<float, 24, 10, 24>, 223, 24> ranlux3_01; |
---|
| 3077 | typedef discard_block<subtract_with_carry_01<float, 24, 10, 24>, 389, 24> ranlux4_01; |
---|
| 3078 | } |
---|
| 3079 | </pre>For a default-constructed <code>minstd_rand0</code> object, x(10000) = |
---|
| 3080 | 1043618065. For a default-constructed <code>minstd_rand</code> object, |
---|
| 3081 | x(10000) = 399268537. |
---|
| 3082 | |
---|
| 3083 | <p>For a default-constructed <code>mt19937</code> object, x(10000) = |
---|
| 3084 | 3346425566.</p> |
---|
| 3085 | |
---|
| 3086 | <p>For a default-constructed <code>ranlux3</code> object, x(10000) = |
---|
| 3087 | 5957620. For a default-constructed <code>ranlux4</code> object, x(10000) = |
---|
| 3088 | 8587295. For a default-constructed <code>ranlux3_01</code> object, x(10000) |
---|
| 3089 | = 5957620 * 2<sup>-24</sup>. For a default-constructed |
---|
| 3090 | <code>ranlux4_01</code> object, x(10000) = 8587295 * 2<sup>-24</sup>.</p> |
---|
| 3091 | |
---|
| 3092 | <h3>Class <code>random_device</code></h3>A <code>random_device</code> |
---|
| 3093 | produces non-deterministic random numbers. It satisfies all the |
---|
| 3094 | requirements of a uniform random number generator (given in tables in |
---|
| 3095 | section x.x). Descriptions are provided here only for operations on the |
---|
| 3096 | engines that are not described in one of these tables or for operations |
---|
| 3097 | where there is additional semantic information. |
---|
| 3098 | |
---|
| 3099 | <p>If implementation limitations prevent generating non-deterministic |
---|
| 3100 | random numbers, the implementation can employ a pseudo-random number |
---|
| 3101 | engine.</p> |
---|
| 3102 | <pre> |
---|
| 3103 | namespace std { |
---|
| 3104 | class random_device |
---|
| 3105 | { |
---|
| 3106 | public: |
---|
| 3107 | // <em>types</em> |
---|
| 3108 | typedef unsigned int result_type; |
---|
| 3109 | |
---|
| 3110 | // <em>constructors, destructors and member functions</em> |
---|
| 3111 | explicit random_device(const std::string& token = /* <em>implementation-defined</em> */); |
---|
| 3112 | result_type min() const; |
---|
| 3113 | result_type max() const; |
---|
| 3114 | double entropy() const; |
---|
| 3115 | result_type operator()(); |
---|
| 3116 | |
---|
| 3117 | private: |
---|
| 3118 | random_device(const random_device& ); |
---|
| 3119 | void operator=(const random_device& ); |
---|
| 3120 | }; |
---|
| 3121 | } |
---|
| 3122 | </pre> |
---|
| 3123 | <pre> |
---|
| 3124 | explicit random_device(const std::string& token = /* <em>implementation-defined</em> */) |
---|
| 3125 | </pre><strong>Effects:</strong> Constructs a <code>random_device</code> |
---|
| 3126 | non-deterministic random number engine. The semantics and default value of |
---|
| 3127 | the <code>token</code> parameter are implementation-defined. [Footnote: The |
---|
| 3128 | parameter is intended to allow an implementation to differentiate between |
---|
| 3129 | different sources of randomness.]<br> |
---|
| 3130 | <strong>Throws:</strong> A value of some type derived from |
---|
| 3131 | <code>exception</code> if the <code>random_device</code> could not be |
---|
| 3132 | initialized. |
---|
| 3133 | <pre> |
---|
| 3134 | result_type min() const |
---|
| 3135 | </pre><strong>Returns:</strong> |
---|
| 3136 | <code>numeric_limits<result_type>::min()</code> |
---|
| 3137 | <pre> |
---|
| 3138 | result_type max() const |
---|
| 3139 | </pre><strong>Returns:</strong> |
---|
| 3140 | <code>numeric_limits<result_type>::max()</code> |
---|
| 3141 | <pre> |
---|
| 3142 | double entropy() const |
---|
| 3143 | </pre><strong>Returns:</strong> An entropy estimate for the random numbers |
---|
| 3144 | returned by operator(), in the range <code>min()</code> to log<sub>2</sub>( |
---|
| 3145 | <code>max()</code>+1). A deterministic random number generator (e.g. a |
---|
| 3146 | pseudo-random number engine) has entropy 0.<br> |
---|
| 3147 | <strong>Throws:</strong> Nothing. |
---|
| 3148 | <pre> |
---|
| 3149 | result_type operator()() |
---|
| 3150 | </pre><strong>Returns:</strong> A non-deterministic random value, uniformly |
---|
| 3151 | distributed between <code>min()</code> and <code>max()</code>, inclusive. It |
---|
| 3152 | is implementation-defined how these values are generated.<br> |
---|
| 3153 | <strong>Throws:</strong> A value of some type derived from |
---|
| 3154 | <code>exception</code> if a random number could not be obtained. |
---|
| 3155 | |
---|
| 3156 | <h3>Random distribution class templates</h3>The class templates specified |
---|
| 3157 | in this section satisfy all the requirements of a random distribution |
---|
| 3158 | (given in tables in section x.x). Descriptions are provided here only for |
---|
| 3159 | operations on the distributions that are not described in one of these |
---|
| 3160 | tables or for operations where there is additional semantic information. |
---|
| 3161 | |
---|
| 3162 | <p>A template parameter named <code>IntType</code> shall denote a type that |
---|
| 3163 | represents an integer number. This type shall meet the requirements for a |
---|
| 3164 | numeric type (26.1 [lib.numeric.requirements]), the binary operators +, -, |
---|
| 3165 | *, /, % shall be applicable to it, and a conversion from <code>int</code> |
---|
| 3166 | shall exist. <em>[Footnote: The built-in types <code>int</code> and |
---|
| 3167 | <code>long</code> meet these requirements.]</em></p> |
---|
| 3168 | |
---|
| 3169 | <p>Given an object whose type is specified in this subclause, if the |
---|
| 3170 | lifetime of the uniform random number generator referred to in the |
---|
| 3171 | constructor invocation for that object has ended, any use of that object is |
---|
| 3172 | undefined.</p> |
---|
| 3173 | |
---|
| 3174 | <p>No function described in this section throws an exception, unless an |
---|
| 3175 | operation on values of <code>IntType</code> or <code>RealType</code> throws |
---|
| 3176 | an exception. <em>[Note: Then, the effects are undefined, see |
---|
| 3177 | [lib.numeric.requirements]. ]</em></p> |
---|
| 3178 | |
---|
| 3179 | <p>The algorithms for producing each of the specified distributions are |
---|
| 3180 | implementation-defined.</p> |
---|
| 3181 | |
---|
| 3182 | <h4>Class template <code>uniform_int</code></h4>A <code>uniform_int</code> |
---|
| 3183 | random distribution produces integer random numbers x in the range min |
---|
| 3184 | <= x <= max, with equal probability. min and max are the parameters |
---|
| 3185 | of the distribution. |
---|
| 3186 | |
---|
| 3187 | <p>A <code>uniform_int</code> random distribution satisfies all the |
---|
| 3188 | requirements of a uniform random number generator (given in tables in |
---|
| 3189 | section x.x).</p> |
---|
| 3190 | <pre> |
---|
| 3191 | namespace std { |
---|
| 3192 | template<class IntType = int> |
---|
| 3193 | class uniform_int |
---|
| 3194 | { |
---|
| 3195 | public: |
---|
| 3196 | // <em>types</em> |
---|
| 3197 | typedef IntType input_type; |
---|
| 3198 | typedef IntType result_type; |
---|
| 3199 | |
---|
| 3200 | // <em> constructors and member function</em> |
---|
| 3201 | explicit uniform_int(IntType min = 0, IntType max = 9); |
---|
| 3202 | result_type min() const; |
---|
| 3203 | result_type max() const; |
---|
| 3204 | void reset(); |
---|
| 3205 | template<class UniformRandomNumberGenerator> |
---|
| 3206 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3207 | template<class UniformRandomNumberGenerator> |
---|
| 3208 | result_type operator()(UniformRandomNumberGenerator& urng, result_type n); |
---|
| 3209 | }; |
---|
| 3210 | } |
---|
| 3211 | </pre> |
---|
| 3212 | <pre> |
---|
| 3213 | uniform_int(IntType min = 0, IntType max = 9) |
---|
| 3214 | </pre><strong>Requires:</strong> min <= max<br> |
---|
| 3215 | <strong>Effects:</strong> Constructs a <code>uniform_int</code> object. |
---|
| 3216 | <code>min</code> and <code>max</code> are the parameters of the |
---|
| 3217 | distribution. |
---|
| 3218 | <pre> |
---|
| 3219 | result_type min() const |
---|
| 3220 | </pre><strong>Returns:</strong> The "min" parameter of the distribution. |
---|
| 3221 | <pre> |
---|
| 3222 | result_type max() const |
---|
| 3223 | </pre><strong>Returns:</strong> The "max" parameter of the distribution. |
---|
| 3224 | <pre> |
---|
| 3225 | result_type operator()(UniformRandomNumberGenerator& urng, result_type n) |
---|
| 3226 | </pre><strong>Returns:</strong> A uniform random number x in the range 0 |
---|
| 3227 | <= x < n. <em>[Note: This allows a <code>variate_generator</code> |
---|
| 3228 | object with a <code>uniform_int</code> distribution to be used with |
---|
| 3229 | std::random_shuffe, see [lib.alg.random.shuffle]. ]</em> |
---|
| 3230 | |
---|
| 3231 | <h4>Class template <code>bernoulli_distribution</code></h4>A |
---|
| 3232 | <code>bernoulli_distribution</code> random distribution produces |
---|
| 3233 | <code>bool</code> values distributed with probabilities p(true) = p and |
---|
| 3234 | p(false) = 1-p. p is the parameter of the distribution. |
---|
| 3235 | <pre> |
---|
| 3236 | namespace std { |
---|
| 3237 | template<class RealType = double> |
---|
| 3238 | class bernoulli_distribution |
---|
| 3239 | { |
---|
| 3240 | public: |
---|
| 3241 | // <em>types</em> |
---|
| 3242 | typedef int input_type; |
---|
| 3243 | typedef bool result_type; |
---|
| 3244 | |
---|
| 3245 | // <em> constructors and member function</em> |
---|
| 3246 | explicit bernoulli_distribution(const RealType& p = RealType(0.5)); |
---|
| 3247 | RealType p() const; |
---|
| 3248 | void reset(); |
---|
| 3249 | template<class UniformRandomNumberGenerator> |
---|
| 3250 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3251 | }; |
---|
| 3252 | } |
---|
| 3253 | </pre> |
---|
| 3254 | <pre> |
---|
| 3255 | bernoulli_distribution(const RealType& p = RealType(0.5)) |
---|
| 3256 | </pre><strong>Requires:</strong> 0 <= p <= 1<br> |
---|
| 3257 | <strong>Effects:</strong> Constructs a <code>bernoulli_distribution</code> |
---|
| 3258 | object. <code>p</code> is the parameter of the distribution. |
---|
| 3259 | <pre> |
---|
| 3260 | RealType p() const |
---|
| 3261 | </pre><strong>Returns:</strong> The "p" parameter of the distribution. |
---|
| 3262 | |
---|
| 3263 | <h4>Class template <code>geometric_distribution</code></h4>A |
---|
| 3264 | <code>geometric_distribution</code> random distribution produces integer |
---|
| 3265 | values <em>i</em> >= 1 with p(i) = (1-p) * p<sup>i-1</sup>. p is the |
---|
| 3266 | parameter of the distribution. |
---|
| 3267 | <pre> |
---|
| 3268 | namespace std { |
---|
| 3269 | template<class IntType = int, class RealType = double> |
---|
| 3270 | class geometric_distribution |
---|
| 3271 | { |
---|
| 3272 | public: |
---|
| 3273 | // <em>types</em> |
---|
| 3274 | typedef RealType input_type; |
---|
| 3275 | typedef IntType result_type; |
---|
| 3276 | |
---|
| 3277 | // <em> constructors and member function</em> |
---|
| 3278 | explicit geometric_distribution(const RealType& p = RealType(0.5)); |
---|
| 3279 | RealType p() const; |
---|
| 3280 | void reset(); |
---|
| 3281 | template<class UniformRandomNumberGenerator> |
---|
| 3282 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3283 | }; |
---|
| 3284 | } |
---|
| 3285 | </pre> |
---|
| 3286 | <pre> |
---|
| 3287 | geometric_distribution(const RealType& p = RealType(0.5)) |
---|
| 3288 | </pre><strong>Requires:</strong> 0 < p < 1<br> |
---|
| 3289 | <strong>Effects:</strong> Constructs a <code>geometric_distribution</code> |
---|
| 3290 | object; <code>p</code> is the parameter of the distribution. |
---|
| 3291 | <pre> |
---|
| 3292 | RealType p() const |
---|
| 3293 | </pre><strong>Returns:</strong> The "p" parameter of the distribution. |
---|
| 3294 | |
---|
| 3295 | <h4>Class template <code>poisson_distribution</code></h4>A |
---|
| 3296 | <code>poisson_distribution</code> random distribution produces integer |
---|
| 3297 | values <em>i</em> >= 0 with p(i) = exp(-mean) * mean<sup>i</sup> / i!. |
---|
| 3298 | mean is the parameter of the distribution. |
---|
| 3299 | <pre> |
---|
| 3300 | namespace std { |
---|
| 3301 | template<class IntType = int, class RealType = double> |
---|
| 3302 | class poisson_distribution |
---|
| 3303 | { |
---|
| 3304 | public: |
---|
| 3305 | // <em>types</em> |
---|
| 3306 | typedef RealType input_type; |
---|
| 3307 | typedef IntType result_type; |
---|
| 3308 | |
---|
| 3309 | // <em> constructors and member function</em> |
---|
| 3310 | explicit poisson_distribution(const RealType& mean = RealType(1)); |
---|
| 3311 | RealType mean() const; |
---|
| 3312 | void reset(); |
---|
| 3313 | template<class UniformRandomNumberGenerator> |
---|
| 3314 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3315 | }; |
---|
| 3316 | } |
---|
| 3317 | </pre> |
---|
| 3318 | <pre> |
---|
| 3319 | poisson_distribution(const RealType& mean = RealType(1)) |
---|
| 3320 | </pre><strong>Requires:</strong> mean > 0<br> |
---|
| 3321 | <strong>Effects:</strong> Constructs a <code>poisson_distribution</code> |
---|
| 3322 | object; <code>mean</code> is the parameter of the distribution. |
---|
| 3323 | <pre> |
---|
| 3324 | RealType mean() const |
---|
| 3325 | </pre><strong>Returns:</strong> The "mean" parameter of the distribution. |
---|
| 3326 | |
---|
| 3327 | <h4>Class template <code>binomial_distribution</code></h4>A |
---|
| 3328 | <code>binomial_distribution</code> random distribution produces integer |
---|
| 3329 | values <em>i</em> >= 0 with p(i) = (n over i) * p<sup>i</sup> * |
---|
| 3330 | (1-p)<sup>t-i</sup>. t and p are the parameters of the distribution. |
---|
| 3331 | <pre> |
---|
| 3332 | namespace std { |
---|
| 3333 | template<class IntType = int, class RealType = double> |
---|
| 3334 | class binomial_distribution |
---|
| 3335 | { |
---|
| 3336 | public: |
---|
| 3337 | // <em>types</em> |
---|
| 3338 | typedef /* <em>implementation-defined</em> */ input_type; |
---|
| 3339 | typedef IntType result_type; |
---|
| 3340 | |
---|
| 3341 | // <em> constructors and member function</em> |
---|
| 3342 | explicit binomial_distribution(IntType t = 1, const RealType& p = RealType(0.5)); |
---|
| 3343 | IntType t() const; |
---|
| 3344 | RealType p() const; |
---|
| 3345 | void reset(); |
---|
| 3346 | template<class UniformRandomNumberGenerator> |
---|
| 3347 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3348 | }; |
---|
| 3349 | } |
---|
| 3350 | </pre> |
---|
| 3351 | <pre> |
---|
| 3352 | binomial_distribution(IntType t = 1, const RealType& p = RealType(0.5)) |
---|
| 3353 | </pre><strong>Requires:</strong> 0 <= p <= 1 and t >= 0<br> |
---|
| 3354 | <strong>Effects:</strong> Constructs a <code>binomial_distribution</code> |
---|
| 3355 | object; <code>t</code> and <code>p</code> are the parameters of the |
---|
| 3356 | distribution. |
---|
| 3357 | <pre> |
---|
| 3358 | IntType t() const |
---|
| 3359 | </pre><strong>Returns:</strong> The "t" parameter of the distribution. |
---|
| 3360 | <pre> |
---|
| 3361 | RealType p() const |
---|
| 3362 | </pre><strong>Returns:</strong> The "p" parameter of the distribution. |
---|
| 3363 | |
---|
| 3364 | <h4>Class template <code>uniform_real</code></h4>A |
---|
| 3365 | <code>uniform_real</code> random distribution produces floating-point |
---|
| 3366 | random numbers x in the range min <= x <= max, with equal |
---|
| 3367 | probability. min and max are the parameters of the distribution. |
---|
| 3368 | |
---|
| 3369 | <p>A <code>uniform_real</code> random distribution satisfies all the |
---|
| 3370 | requirements of a uniform random number generator (given in tables in |
---|
| 3371 | section x.x).</p> |
---|
| 3372 | <pre> |
---|
| 3373 | namespace std { |
---|
| 3374 | template<class RealType = double> |
---|
| 3375 | class uniform_real |
---|
| 3376 | { |
---|
| 3377 | public: |
---|
| 3378 | // <em>types</em> |
---|
| 3379 | typedef RealType input_type; |
---|
| 3380 | typedef RealType result_type; |
---|
| 3381 | |
---|
| 3382 | // <em> constructors and member function</em> |
---|
| 3383 | explicit uniform_real(RealType min = RealType(0), RealType max = RealType(1)); |
---|
| 3384 | result_type min() const; |
---|
| 3385 | result_type max() const; |
---|
| 3386 | void reset(); |
---|
| 3387 | template<class UniformRandomNumberGenerator> |
---|
| 3388 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3389 | }; |
---|
| 3390 | } |
---|
| 3391 | </pre> |
---|
| 3392 | <pre> |
---|
| 3393 | uniform_real(RealType min = RealType(0), RealType max = RealType(1)) |
---|
| 3394 | </pre><strong>Requires:</strong> min <= max<br> |
---|
| 3395 | <strong>Effects:</strong> Constructs a <code>uniform_real</code> object; |
---|
| 3396 | <code>min</code> and <code>max</code> are the parameters of the |
---|
| 3397 | distribution. |
---|
| 3398 | <pre> |
---|
| 3399 | result_type min() const |
---|
| 3400 | </pre><strong>Returns:</strong> The "min" parameter of the distribution. |
---|
| 3401 | <pre> |
---|
| 3402 | result_type max() const |
---|
| 3403 | </pre><strong>Returns:</strong> The "max" parameter of the distribution. |
---|
| 3404 | |
---|
| 3405 | <h4>Class template <code>exponential_distribution</code></h4>An |
---|
| 3406 | <code>exponential_distribution</code> random distribution produces random |
---|
| 3407 | numbers x > 0 distributed with probability density function p(x) = |
---|
| 3408 | lambda * exp(-lambda * x), where lambda is the parameter of the |
---|
| 3409 | distribution. |
---|
| 3410 | <pre> |
---|
| 3411 | namespace std { |
---|
| 3412 | template<class RealType = double> |
---|
| 3413 | class exponential_distribution |
---|
| 3414 | { |
---|
| 3415 | public: |
---|
| 3416 | // <em>types</em> |
---|
| 3417 | typedef RealType input_type; |
---|
| 3418 | typedef RealType result_type; |
---|
| 3419 | |
---|
| 3420 | // <em> constructors and member function</em> |
---|
| 3421 | explicit exponential_distribution(const result_type& lambda = result_type(1)); |
---|
| 3422 | RealType lambda() const; |
---|
| 3423 | void reset(); |
---|
| 3424 | template<class UniformRandomNumberGenerator> |
---|
| 3425 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3426 | }; |
---|
| 3427 | } |
---|
| 3428 | </pre> |
---|
| 3429 | <pre> |
---|
| 3430 | exponential_distribution(const result_type& lambda = result_type(1)) |
---|
| 3431 | </pre><strong>Requires:</strong> lambda > 0<br> |
---|
| 3432 | <strong>Effects:</strong> Constructs an |
---|
| 3433 | <code>exponential_distribution</code> object with <code>rng</code> as the |
---|
| 3434 | reference to the underlying source of random numbers. <code>lambda</code> |
---|
| 3435 | is the parameter for the distribution. |
---|
| 3436 | <pre> |
---|
| 3437 | RealType lambda() const |
---|
| 3438 | </pre><strong>Returns:</strong> The "lambda" parameter of the distribution. |
---|
| 3439 | |
---|
| 3440 | <h4>Class template <code>normal_distribution</code></h4>A |
---|
| 3441 | <code>normal_distribution</code> random distribution produces random |
---|
| 3442 | numbers x distributed with probability density function p(x) = |
---|
| 3443 | 1/sqrt(2*pi*sigma) * exp(- (x-mean)<sup>2</sup> / (2*sigma<sup>2</sup>) ), |
---|
| 3444 | where mean and sigma are the parameters of the distribution. |
---|
| 3445 | <pre> |
---|
| 3446 | namespace std { |
---|
| 3447 | template<class RealType = double> |
---|
| 3448 | class normal_distribution |
---|
| 3449 | { |
---|
| 3450 | public: |
---|
| 3451 | // <em>types</em> |
---|
| 3452 | typedef RealType input_type; |
---|
| 3453 | typedef RealType result_type; |
---|
| 3454 | |
---|
| 3455 | // <em> constructors and member function</em> |
---|
| 3456 | explicit normal_distribution(base_type & rng, const result_type& mean = 0, |
---|
| 3457 | const result_type& sigma = 1); |
---|
| 3458 | RealType mean() const; |
---|
| 3459 | RealType sigma() const; |
---|
| 3460 | void reset(); |
---|
| 3461 | template<class UniformRandomNumberGenerator> |
---|
| 3462 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3463 | }; |
---|
| 3464 | } |
---|
| 3465 | </pre> |
---|
| 3466 | <pre> |
---|
| 3467 | explicit normal_distribution( const result_type& mean = 0, |
---|
| 3468 | const result_type& sigma = 1); |
---|
| 3469 | </pre><strong>Requires:</strong> sigma > 0<br> |
---|
| 3470 | <strong>Effects:</strong> Constructs a <code>normal_distribution</code> |
---|
| 3471 | object; <code>mean</code> and <code>sigma</code> are the parameters for the |
---|
| 3472 | distribution. |
---|
| 3473 | <pre> |
---|
| 3474 | RealType mean() const |
---|
| 3475 | </pre><strong>Returns:</strong> The "mean" parameter of the distribution. |
---|
| 3476 | <pre> |
---|
| 3477 | RealType sigma() const |
---|
| 3478 | </pre><strong>Returns:</strong> The "sigma" parameter of the distribution. |
---|
| 3479 | |
---|
| 3480 | <h4>Class template <code>gamma_distribution</code></h4>A |
---|
| 3481 | <code>gamma_distribution</code> random distribution produces random numbers |
---|
| 3482 | x distributed with probability density function p(x) = 1/Gamma(alpha) * |
---|
| 3483 | x<sup>alpha-1</sup> * exp(-x), where alpha is the parameter of the |
---|
| 3484 | distribution. |
---|
| 3485 | <pre> |
---|
| 3486 | namespace std { |
---|
| 3487 | template<class RealType = double> |
---|
| 3488 | class gamma_distribution |
---|
| 3489 | { |
---|
| 3490 | public: |
---|
| 3491 | // <em>types</em> |
---|
| 3492 | typedef RealType input_type; |
---|
| 3493 | typedef RealType result_type; |
---|
| 3494 | |
---|
| 3495 | // <em> constructors and member function</em> |
---|
| 3496 | explicit gamma_distribution(const result_type& alpha = result_type(1)); |
---|
| 3497 | RealType alpha() const; |
---|
| 3498 | void reset(); |
---|
| 3499 | template<class UniformRandomNumberGenerator> |
---|
| 3500 | result_type operator()(UniformRandomNumberGenerator& urng); |
---|
| 3501 | }; |
---|
| 3502 | } |
---|
| 3503 | </pre> |
---|
| 3504 | <pre> |
---|
| 3505 | explicit gamma_distribution(const result_type& alpha = result_type(1)); |
---|
| 3506 | </pre><strong>Requires:</strong> alpha > 0<br> |
---|
| 3507 | <strong>Effects:</strong> Constructs a <code>gamma_distribution</code> |
---|
| 3508 | object; <code>alpha</code> is the parameter for the distribution. |
---|
| 3509 | <pre> |
---|
| 3510 | RealType alpha() const |
---|
| 3511 | </pre><strong>Returns:</strong> The "alpha" parameter of the distribution. |
---|
| 3512 | |
---|
| 3513 | <h2>V. Acknowledgements</h2> |
---|
| 3514 | |
---|
| 3515 | <ul> |
---|
| 3516 | <li>Thanks to Walter Brown, Mark Fischler and Marc Paterno from Fermilab |
---|
| 3517 | for input about the requirements of high-energy physics.</li> |
---|
| 3518 | |
---|
| 3519 | <li>Thanks to David Abrahams for additional comments on the design.</li> |
---|
| 3520 | |
---|
| 3521 | <li>Thanks to the Boost community for a platform for |
---|
| 3522 | experimentation.</li> |
---|
| 3523 | </ul> |
---|
| 3524 | |
---|
| 3525 | <h2>VI. References</h2> |
---|
| 3526 | |
---|
| 3527 | <ul> |
---|
| 3528 | <li>William H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P. |
---|
| 3529 | Flannery, "Numerical Recipes in C: The art of scientific computing", 2nd |
---|
| 3530 | ed., 1992, pp. 274-328</li> |
---|
| 3531 | |
---|
| 3532 | <li>Bruce Schneier, "Applied Cryptography", 2nd ed., 1996, ch. 16-17. [I |
---|
| 3533 | haven't read this myself. Yet.]</li> |
---|
| 3534 | |
---|
| 3535 | <li>D. H. Lehmer, "Mathematical methods in large-scale computing units", |
---|
| 3536 | Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, Harvard |
---|
| 3537 | University Press, 1951, pp. 141-146</li> |
---|
| 3538 | |
---|
| 3539 | <li>P.A. Lewis, A.S. Goodman, J.M. Miller, "A pseudo-random number |
---|
| 3540 | generator for the System/360", IBM Systems Journal, Vol. 8, No. 2, 1969, |
---|
| 3541 | pp. 136-146</li> |
---|
| 3542 | |
---|
| 3543 | <li>Stephen K. Park and Keith W. Miller, "Random Number Generators: Good |
---|
| 3544 | ones are hard to find", Communications of the ACM, Vol. 31, No. 10, |
---|
| 3545 | October 1988, pp. 1192-1201</li> |
---|
| 3546 | |
---|
| 3547 | <li>Makoto Matsumoto and Takuji Nishimura, "Mersenne Twister: A |
---|
| 3548 | 623-dimensionally equidistributed uniform pseudo-random number |
---|
| 3549 | generator", ACM Transactions on Modeling and Computer Simulation: Special |
---|
| 3550 | Issue on Uniform Random Number Generation, Vol. 8, No. 1, January 1998, |
---|
| 3551 | pp. 3-30. http://www.math.keio.ac.jp/matumoto/emt.html.</li> |
---|
| 3552 | |
---|
| 3553 | <li>Donald E. Knuth, "The Art of Computer Programming, Vol. 2", 3rd ed., |
---|
| 3554 | 1997, pp. 1-193.</li> |
---|
| 3555 | |
---|
| 3556 | <li>Carter Bays and S.D. Durham, "Improving a poor random number |
---|
| 3557 | generator", ACM Transactions on Mathematical Software, Vol. 2, 1979, pp. |
---|
| 3558 | 59-64.</li> |
---|
| 3559 | |
---|
| 3560 | <li>Martin Lüscher, "A portable high-quality random number generator |
---|
| 3561 | for lattice field theory simulations.", Computer Physics Communications, |
---|
| 3562 | Vol. 79, 1994, pp. 100-110.</li> |
---|
| 3563 | |
---|
| 3564 | <li>William J. Hurd, "Efficient Generation of Statistically Good |
---|
| 3565 | Pseudonoise by Linearly Interconnected Shift Registers", Technical Report |
---|
| 3566 | 32-1526, Volume XI, The Deep Space Network Progress Report for July and |
---|
| 3567 | August 1972, NASA Jet Propulsion Laboratory, 1972 and IEEE Transactions |
---|
| 3568 | on Computers Vol. 23, 1974.</li> |
---|
| 3569 | |
---|
| 3570 | <li>Pierre L'Ecuyer, "Efficient and Portable Combined Random Number |
---|
| 3571 | Generators", Communications of the ACM, Vol. 31, pp. 742-749+774, |
---|
| 3572 | 1988.</li> |
---|
| 3573 | |
---|
| 3574 | <li>Pierre L'Ecuyer, "Maximally equidistributed combined Tausworthe |
---|
| 3575 | generators", Mathematics of Computation Vol. 65, pp. 203-213, 1996.</li> |
---|
| 3576 | |
---|
| 3577 | <li>Pierre L'Ecuyer, "Good parameters and implementations for combined |
---|
| 3578 | multple recursive random number generators", Operations Research Vol. 47, |
---|
| 3579 | pp. 159-164, 1999.</li> |
---|
| 3580 | |
---|
| 3581 | <li>S. Kirkpatrick and E. Stoll, "A very fast shift-register sequence |
---|
| 3582 | random number generator", Journal of Computational Physics, Vol. 40, pp. |
---|
| 3583 | 517-526, 1981.</li> |
---|
| 3584 | |
---|
| 3585 | <li>R. C. Tausworthe, "Random numbers generated by iinear recurrence |
---|
| 3586 | modulo two", Mathematics of Computation, Vol. 19, pp. 201-209, 1965.</li> |
---|
| 3587 | |
---|
| 3588 | <li>George Marsaglia and Arif Zaman, "A New Class of Random Number |
---|
| 3589 | Generators", Annals of Applied Probability, Vol. 1, No. 3, 1991.</li> |
---|
| 3590 | </ul> |
---|
| 3591 | <hr> |
---|
| 3592 | |
---|
| 3593 | <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= |
---|
| 3594 | "http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional" |
---|
| 3595 | height="31" width="88"></a></p> |
---|
| 3596 | |
---|
| 3597 | <p>Revised |
---|
| 3598 | <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05 December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p> |
---|
| 3599 | |
---|
| 3600 | <p><i>Copyright © 2002 <a href= |
---|
| 3601 | "../../people/jens_maurer.htm">Jens Maurer</a></i></p> |
---|
| 3602 | |
---|
| 3603 | <p><i>Distributed under the Boost Software License, Version 1.0. (See |
---|
| 3604 | accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or |
---|
| 3605 | copy at <a href= |
---|
| 3606 | "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> |
---|
| 3607 | </body> |
---|
| 3608 | </html> |
---|