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> |
---|