Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/random/wg21-proposal.html @ 33

Last change on this file since 33 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 129.0 KB
Line 
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 &lt;Jens.Maurer@gmx.net&gt;<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&lt;lagged_fibonacci&lt;...&gt;, mersenne_twister&lt;...&gt; &gt;
419</pre>generator. For this, <code>seed(first, last)</code> will consume values
420as follows: First, seed the state of the <code>lagged_fibonacci</code>
421generator by consuming one item from [first, last) for each word of state.
422The 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
425remaining [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 &gt;=
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&lt;&gt;</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 &lt;= k
560    &lt; 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&lt; ..., 1664525, 1013904223, (1 &lt;&lt; 32)
843      &gt;</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&lt;minstd_rand0, 32&gt; (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&lt; shuffle_output&lt;<br>
937      linear_congruential&lt;int, 40014, 0, 2147483563&gt;, 32&gt;,<br>
938      linear_congruential&lt;int, 40692, 0, 2147483399&gt; &gt;
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&lt; ..., 32, 55, 24, ...&gt; (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&lt; ..., (1&lt;&lt;32), 37, 24, ...&gt;</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&lt; ..., (1&lt;&lt;32)-5, 43, 22, ...&gt;</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&uuml;scher</td>
1083
1084      <td>discard_block&lt; subtract_with_carry&lt;...&gt;, ...&gt;</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&lt; lagged_fibonacci&lt; (1&lt;&lt;24), 97, 33,
1159      ... &gt;, linear_congruential&lt; (1&lt;&lt;24)-3, 1, c, ...&gt;
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&lt; linear_feedback_shift&lt; 31, 13, 12 &gt;, 0,
1197      linear_feedback_shift&lt; 29, 2, 4 &gt;, 2, 0&gt;
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>
1610NumberGenerator ---- 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&lt;&lt;</code> and <code>operator&gt;&gt;</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&lt;class BiIter&gt; 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&lt;class Engine&gt;
1878  Engine seed(unique_seed&amp;);
1879</pre>The "seed" function retrieves some unique seed from the unique_seed
1880class and then uses the <code>seed(first, last)</code> interface of an engine
1881to implant that unique seed. Specific seeding requirements for some engine
1882can 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&nbsp;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&lt;T&gt;::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&nbsp;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&lt;T&gt;::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&nbsp;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 &lt;&lt; x</code></td>
2127
2128      <td><code>std::ostream&amp;</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 &gt;&gt; v</code></td>
2144
2145      <td><code>std::istream&amp;</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&nbsp;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 &lt;&lt; x</code></td>
2214
2215      <td><code>std::ostream&amp;</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 &gt;&gt; u</code></td>
2228
2229      <td><code>std::istream&amp;</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&lt;&lt;</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  &lt;&lt; x</code> is invoked between any of the invocations
2244  <code>x(e)</code>. If a textual representation is written using <code>os
2245  &lt;&lt; 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 &gt;&gt;
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>&lt;random&gt;</code> synopsis</h3>
2267  <pre>
2268namespace std {
2269  template&lt;class UniformRandomNumberGenerator, class Distribution&gt;
2270  class variate_generator;
2271
2272  template&lt;class IntType, IntType a, IntType c, IntType m&gt;
2273  class linear_congruential;
2274
2275  template&lt;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&gt;
2277  class mersenne_twister;
2278
2279  template&lt;class IntType, IntType m, int s, int r&gt;
2280  class subtract_with_carry;
2281
2282  template&lt;class RealType, int w, int s, int r&gt;
2283  class subtract_with_carry_01;
2284
2285  template&lt;class UniformRandomNumberGenerator, int p, int r&gt;
2286  class discard_block;
2287
2288  template&lt;class UniformRandomNumberGenerator1, int s1,
2289           class UniformRandomNumberGenerator2, int s2&gt;
2290  class xor_combine;
2291
2292  class random_device;
2293
2294  template&lt;class IntType = int&gt;
2295  class uniform_int;
2296
2297  template&lt;class RealType = double&gt;
2298  class bernoulli_distribution;
2299
2300  template&lt;class IntType = int, class RealType = double&gt;
2301  class geometric_distribution;
2302
2303  template&lt;class IntType = int, class RealType = double&gt;
2304  class poisson_distribution;
2305
2306  template&lt;class IntType = int, class RealType = double&gt;
2307  class binomial_distribution;
2308
2309  template&lt;class RealType = double&gt;
2310  class uniform_real;
2311
2312  template&lt;class RealType = double&gt;
2313  class exponential_distribution;
2314
2315  template&lt;class RealType = double&gt;
2316  class normal_distribution;
2317
2318  template&lt;class RealType = double&gt;
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>
2329template&lt;class Engine, class Distribution&gt;
2330class variate_generator
2331{
2332public:
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&lt;class T&gt;  result_type operator()(T value);
2342
2343  engine_value_type&amp; engine();
2344  const engine_value_type&amp; engine() const;
2345
2346  distribution_type&amp; distribution();
2347  const distribution_type&amp; 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
2353the form <code><em>U</em></code>, <code><em>U</em>&amp;</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>&amp;</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>
2369object with the associated uniform random number generator <code>eng</code>
2370and 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&lt;<em>T</em>&gt;::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&lt;class T&gt; result_type operator()(T value)
2399</pre><strong>Returns:</strong> <code>distribution()(e, value)</code>. For
2400the semantics of <code>e</code>, see the description of
2401<code>operator()()</code>.
2402  <pre>
2403    engine_value_type&amp; engine()
2404</pre><strong>Returns:</strong> A reference to the associated uniform random
2405number generator.
2406  <pre>
2407    const engine_value_type&amp; engine() const
2408</pre><strong>Returns:</strong> A reference to the associated uniform random
2409number generator.
2410  <pre>
2411    distribution_type&amp; distribution()
2412</pre><strong>Returns:</strong> A reference to the associated random
2413distribution.
2414  <pre>
2415    const distribution_type&amp; distribution() const
2416</pre><strong>Returns:</strong> A reference to the associated random
2417distribution.
2418  <pre>
2419    result_type min() const
2420</pre><strong>Precondition:</strong> <code>distribution().min()</code> is
2421well-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
2426well-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>
2449namespace std {
2450  template&lt;class IntType, IntType a, IntType c, IntType m&gt;
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&lt;class In&gt; linear_congruential(In&amp; first, In last);
2465    void seed(IntType x0 = 1);
2466    template&lt;class In&gt; void seed(In&amp; first, In last);
2467    result_type min() const;
2468    result_type max() const;
2469    result_type operator()();
2470  };
2471
2472  template&lt;class IntType, IntType a, IntType c, IntType m&gt;
2473  bool operator==(const linear_congruential&lt;IntType, a, c, m&gt;&amp; x,
2474                  const linear_congruential&lt;IntType, a, c, m&gt;&amp; y);
2475  template&lt;class IntType, IntType a, IntType c, IntType m&gt;
2476  bool operator!=(const linear_congruential&lt;IntType, a, c, m&gt;&amp; x,
2477                  const linear_congruential&lt;IntType, a, c, m&gt;&amp; y);
2478
2479  template&lt;class CharT, class traits,
2480           class IntType, IntType a, IntType c, IntType m&gt;
2481  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
2482                                           const linear_congruential&lt;IntType, a, c, m&gt;&amp; x); 
2483  template&lt;class CharT, class traits,
2484           class IntType, IntType a, IntType c, IntType m&gt;
2485  basic_istream&lt;CharT, traits&gt;&amp; operator&gt;&gt;(basic_istream&lt;CharT, traits&gt;&amp; is,
2486                                           linear_congruential&lt;IntType, a, c, m&gt;&amp; x);
2487}
2488</pre>The template parameter <code>IntType</code> shall denote an integral
2489type 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
2491template 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 &gt; 0 || (x0 % m) &gt; 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 &gt; 0 || (x0 % m) &gt; 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&lt;class In&gt; linear_congruential(In&amp; first, In last)
2508</pre><strong>Requires:</strong> <code>c &gt; 0 || *first &gt; 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&lt;class CharT, class traits,
2515           class IntType, IntType a, IntType c, IntType m&gt;
2516  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
2517                                           const linear_congruential&lt;IntType, a, c, m&gt;&amp; 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>
2549namespace std {
2550  template&lt;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&gt;
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&lt;class In&gt; mersenne_twister(In&amp; first, In last);
2575    void seed();
2576    void seed(UIntType value);
2577    template&lt;class In&gt; void seed(In&amp; first, In last);
2578    result_type min() const;
2579    result_type max() const;
2580    result_type operator()();
2581  };
2582
2583  template&lt;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&gt;
2585  bool operator==(const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; y,
2586                  const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; x);
2587  template&lt;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&gt;
2589  bool operator!=(const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; y,
2590                  const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; x);
2591
2592  template&lt;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&gt;
2595  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
2596                                           const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; x);
2597  template&lt;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&gt;
2600  basic_istream&lt;CharT, traits&gt;&amp; operator&gt;&gt;(basic_istream&lt;CharT, traits&gt;&amp; is,
2601                                           mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; x);
2602}
2603</pre>The template parameter <code>UIntType</code> shall denote an unsigned
2604integral type large enough to store values up to 2<sup>w</sup>-1. Also, the
2605following relations shall hold: 1&lt;=m&lt;=n. 0&lt;=r,u,s,t,l&lt;=w.
26060&lt;=a,b,c&lt;=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>
2612engine 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>
2616engine and invokes <code>seed(value)</code>.
2617  <pre>
2618    template&lt;class In&gt; mersenne_twister(In&amp; first, In last)
2619</pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
2620engine 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 &gt; 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&lt;class In&gt; void seed(In&amp; first, In last)
2634</pre><strong>Effects:</strong> Given the values z<sub>0</sub> ...
2635z<sub>n-1</sub> obtained by dereferencing [first, first+n), sets x(-n) ...
2636x(-1) to z<sub>0</sub> mod 2<sup>w</sup> ... z<sub>n-1</sub> mod
26372<sup>w</sup>.<br>
2638  <strong>Complexity:</strong> Exactly <code>n</code> dereferences of
2639  <code>first</code>.
2640  <pre>
2641    template&lt;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&gt;
2643    bool operator==(const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; y,
2644                    const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; x)
2645</pre><strong>Returns:</strong> x(i-n) == y(j-n) and ... and x(i-1) ==
2646y(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&lt;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&gt;
2654    basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
2655                                             const mersenne_twister&lt;UIntType, w, n, m, r, a, u, s, b, t, c, l&gt;&amp; x)
2656</pre><strong>Effects:</strong> Writes x(i-n), ... x(i-1) to <code>os</code>,
2657in 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) &lt; 0, else carry(i) = 0.
2664  <pre>
2665namespace std {
2666  template&lt;class IntType, IntType m, int s, int r&gt;
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&lt;class In&gt; subtract_with_carry(In&amp; first, In last);
2682    void seed(IntType value = 19780503);
2683    template&lt;class In&gt; void seed(In&amp; first, In last);
2684    result_type min() const;
2685    result_type max() const;
2686    result_type operator()();
2687  };
2688  template&lt;class IntType, IntType m, int s, int r&gt;
2689  bool operator==(const subtract_with_carry&lt;IntType, m, s, r&gt; &amp; x,
2690                  const subtract_with_carry&lt;IntType, m, s, r&gt; &amp; y);
2691
2692  template&lt;class IntType, IntType m, int s, int r&gt;
2693  bool operator!=(const subtract_with_carry&lt;IntType, m, s, r&gt; &amp; x,
2694                  const subtract_with_carry&lt;IntType, m, s, r&gt; &amp; y);
2695
2696  template&lt;class CharT, class Traits,
2697           class IntType, IntType m, int s, int r&gt;
2698  std::basic_ostream&lt;CharT,Traits&gt;&amp; operator&lt;&lt;(std::basic_ostream&lt;CharT,Traits&gt;&amp; os,
2699                                               const subtract_with_carry&lt;IntType, m, s, r&gt;&amp; f);
2700
2701  template&lt;class CharT, class Traits,
2702          class IntType, IntType m, int s, int r&gt;
2703  std::basic_istream&lt;CharT,Traits&gt;&amp; operator&gt;&gt;(std::basic_istream&lt;CharT,Traits&gt;&amp; is,
2704                                               subtract_with_carry&lt;IntType, m, s, r&gt;&amp; f);
2705}
2706</pre>The template parameter <code>IntType</code> shall denote a signed
2707integral type large enough to store values up to m-1. The following relation
2708shall hold: 0&lt;s&lt;r. Let w the number of bits in the binary
2709representation 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>
2715engine 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>
2719engine and invokes <code>seed(value)</code>.
2720  <pre>
2721    template&lt;class In&gt; subtract_with_carry(In&amp; first, In last)
2722</pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code>
2723engine and invokes <code>seed(first, last)</code>.
2724  <pre>
2725    void seed(IntType value = 19780503)
2726</pre><strong>Requires:</strong> <code>value &gt; 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&lt;class In&gt; void seed(In&amp; first, In last)
2735</pre><strong>Effects:</strong> With n=w/32+1 (rounded downward) and given
2736the 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
2740x(-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&lt;class IntType, IntType m, int s, int r&gt;
2745    bool operator==(const subtract_with_carry&lt;IntType, m, s, r&gt; &amp; x,
2746                    const subtract_with_carry&lt;IntType, m, s, r&gt; &amp; y)
2747</pre><strong>Returns:</strong> x(i-r) == y(j-r) and ... and x(i-1) ==
2748y(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&lt;class CharT, class Traits,
2754          class IntType, IntType m, int s, int r&gt;
2755    std::basic_ostream&lt;CharT,Traits&gt;&amp; operator&lt;&lt;(std::basic_ostream&lt;CharT,Traits&gt;&amp; os,
2756                                                 const subtract_with_carry&lt;IntType, m, s, r&gt;&amp; 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) &lt; 0, else carry(i) = 0.
2765  <pre>
2766namespace std {
2767  template&lt;class RealType, int w, int s, int r&gt;
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&lt;class In&gt; subtract_with_carry_01(In&amp; first, In last);
2783    void seed(unsigned int value = 19780503);
2784    template&lt;class In&gt; void seed(In&amp; first, In last);
2785    result_type min() const;
2786    result_type max() const;
2787    result_type operator()();
2788  };
2789  template&lt;class RealType, int w, int s, int r&gt;
2790  bool operator==(const subtract_with_carry_01&lt;RealType, w, s, r&gt; x,
2791                  const subtract_with_carry_01&lt;RealType, w, s, r&gt; y);
2792
2793  template&lt;class RealType, int w, int s, int r&gt;
2794  bool operator!=(const subtract_with_carry_01&lt;RealType, w, s, r&gt; x,
2795                  const subtract_with_carry_01&lt;RealType, w, s, r&gt; y);
2796
2797  template&lt;class CharT, class Traits,
2798           class RealType, int w, int s, int r&gt;
2799  std::basic_ostream&lt;CharT,Traits&gt;&amp; operator&lt;&lt;(std::basic_ostream&lt;CharT,Traits&gt;&amp; os,
2800                                               const subtract_with_carry_01&lt;RealType, w, s, r&gt;&amp; f);
2801
2802  template&lt;class CharT, class Traits,
2803           class RealType, int w, int s, int r&gt;
2804  std::basic_istream&lt;CharT,Traits&gt;&amp; operator&gt;&gt;(std::basic_istream&lt;CharT,Traits&gt;&amp; is,
2805                                               subtract_with_carry_01&lt;RealType, w, s, r&gt;&amp; f);
2806}
2807</pre>The following relation shall hold: 0&lt;s&lt;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&lt;class In&gt; subtract_with_carry_01(In&amp; first, In last)
2821</pre><strong>Effects:</strong> Constructs a
2822<code>subtract_with_carry_01</code> engine and invokes <code>seed(first,
2823last)</code>.
2824  <pre>
2825    void seed(unsigned int value = 19780503)
2826</pre><strong>Effects:</strong> With a linear congruential generator l(i)
2827having 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) =
28302<sup>-w</sup>, else sets carry(-1) = 0.<br>
2831  <strong>Complexity:</strong> O(r)
2832  <pre>
2833    template&lt;class In&gt; void seed(In&amp; first, In last)
2834</pre><strong>Effects:</strong> With n=w/32+1 (rounded downward) and given
2835the 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> *
28392<sup>32*(n-1)</sup>) * 2<sup>-w</sup> mod 1. If x(-1) == 0, sets carry(-1) =
28402<sup>-w</sup>, else sets carry(-1) = 0.<br>
2841  <strong>Complexity:</strong> O(r*n)
2842  <pre>
2843    template&lt;class RealType, int w, int s, int r&gt;
2844    bool operator==(const subtract_with_carry&lt;RealType, w, s, r&gt; x,
2845                    const subtract_with_carry&lt;RealType, w, s, r&gt; y);
2846</pre><strong>Returns:</strong> true, if and only if x(i-r) == y(j-r) and ...
2847and x(i-1) == y(j-1).<br>
2848  <strong>Complexity:</strong> O(r)
2849  <pre>
2850    template&lt;class CharT, class Traits,
2851             class RealType, int w, int s, int r&gt;
2852    std::basic_ostream&lt;CharT,Traits&gt;&amp; operator&lt;&lt;(std::basic_ostream&lt;CharT,Traits&gt;&amp; os,
2853                                                 const subtract_with_carry&lt;RealType, w, s, r&gt;&amp; f);
2854</pre><strong>Effects:</strong> Write x(i-r)*2<sup>w</sup> ...
2855x(i-1)*2<sup>w</sup>, carry(i-1)*2<sup>w</sup> to <code>os</code>, in that
2856order.<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>
2863namespace std {
2864  template&lt;class UniformRandomNumberGenerator, int p, int r&gt;
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 &amp; rng);
2879    template&lt;class In&gt; discard_block(In&amp; first, In last);
2880    void seed();
2881    template&lt;class In&gt; void seed(In&amp; first, In last);
2882    const base_type&amp; 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&lt;class UniformRandomNumberGenerator, int p, int r&gt;
2891  bool operator==(const discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; x,
2892                 (const discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; y);
2893  template&lt;class UniformRandomNumberGenerator, int p, int r,
2894    typename UniformRandomNumberGenerator::result_type val&gt;
2895  bool operator!=(const discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; x,
2896                 (const discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; y);
2897
2898  template&lt;class CharT, class traits,
2899           class UniformRandomNumberGenerator, int p, int r&gt;
2900  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
2901                                           const discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; x);
2902  template&lt;class CharT, class traits,
2903           class UniformRandomNumberGenerator, int p, int r&gt;
2904  basic_istream&lt;CharT, traits&gt;&amp; operator&gt;&gt;(basic_istream&lt;CharT, traits&gt;&amp; is,
2905                                           discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; x);
2906
2907}
2908</pre>The template parameter <code>UniformRandomNumberGenerator</code> shall
2909denote a class that satisfies all the requirements of a uniform random number
2910generator, given in tables in section x.x. r &lt;= p. The size of the state
2911is 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>
2915engine. To construct the subobject <em>b</em>, invokes its default
2916constructor. Sets <code>n = 0</code>.
2917  <pre>
2918    explicit discard_block(const base_type &amp; rng)
2919</pre><strong>Effects:</strong> Constructs a <code>discard_block</code>
2920engine. Initializes <em>b</em> with a copy of <code>rng</code>. Sets <code>n
2921= 0</code>.
2922  <pre>
2923    template&lt;class In&gt; discard_block(In&amp; first, In last)
2924</pre><strong>Effects:</strong> Constructs a <code>discard_block</code>
2925engine. To construct the subobject <em>b</em>, invokes the <code>b(first,
2926last)</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
2930sets <code>n = 0</code>.
2931  <pre>
2932    template&lt;class In&gt; void seed(In&amp; first, In last)
2933</pre><strong>Effects:</strong> Invokes <code><em>b</em>.seed(first,
2934last)</code> and sets <code>n = 0</code>.
2935  <pre>
2936    const base_type&amp; 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> &gt;= 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&lt;class CharT, class traits,
2946           class UniformRandomNumberGenerator, int p, int r&gt;
2947  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
2948                                           const discard_block&lt;UniformRandomNumberGenerator,p,r&gt; &amp; 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>
2956namespace std {
2957  template&lt;class UniformRandomNumberGenerator1, int s1,
2958           class UniformRandomNumberGenerator2, int s2&gt;
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 &amp; rng1, const base2_type &amp; rng2);
2974    template&lt;class In&gt; xor_combine(In&amp; first, In last);
2975    void seed();
2976    template&lt;class In&gt; void seed(In&amp; first, In last);
2977    const base1_type&amp; base1() const;
2978    const base2_type&amp; 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&lt;class UniformRandomNumberGenerator1, int s1,
2987           class UniformRandomNumberGenerator2, int s2&gt;
2988  bool operator==(const xor_combine&lt;UniformRandomNumberGenerator1, s1,
2989                                    UniformRandomNumberGenerator2, s2&gt; &amp; x,
2990                 (const xor_combine&lt;UniformRandomNumberGenerator1, s1,
2991                                    UniformRandomNumberGenerator2, s2&gt; &amp; y);
2992  template&lt;class UniformRandomNumberGenerator1, int s1,
2993           class UniformRandomNumberGenerator2, int s2&gt;
2994  bool operator!=(const xor_combine&lt;UniformRandomNumberGenerator1, s1,
2995                                    UniformRandomNumberGenerator2, s2&gt; &amp; x,
2996                 (const xor_combine&lt;UniformRandomNumberGenerator1, s1,
2997                                    UniformRandomNumberGenerator2, s2&gt; &amp; y);
2998
2999  template&lt;class CharT, class traits,
3000           class UniformRandomNumberGenerator1, int s1,
3001           class UniformRandomNumberGenerator2, int s2&gt;
3002  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
3003                                           const xor_combine&lt;UniformRandomNumberGenerator1, s1,
3004                                                             UniformRandomNumberGenerator2, s2&gt; &amp; x);
3005  template&lt;class CharT, class traits,
3006           class UniformRandomNumberGenerator1, int s1,
3007           class UniformRandomNumberGenerator2, int s2&gt;
3008  basic_istream&lt;CharT, traits&gt;&amp; operator&gt;&gt;(basic_istream&lt;CharT, traits&gt;&amp; is,
3009                                           xor_combine&lt;UniformRandomNumberGenerator1, s1,
3010                                                       UniformRandomNumberGenerator2, s2&gt; &amp; x);
3011
3012}
3013</pre>The template parameters <code>UniformRandomNumberGenerator1</code> and
3014<code>UniformRandomNumberGenerator1</code> shall denote classes that satisfy
3015all the requirements of a uniform random number generator, given in tables in
3016section x.x . The size of the state is the size of <code><em>b1</em></code>
3017plus 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.
3021To construct each of the subobjects <em>b1</em> and <em>b2</em>, invokes
3022their respective default constructors.
3023  <pre>
3024    xor_combine(const base1_type &amp; rng1, const base2_type &amp; rng2)
3025</pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine.
3026Initializes <em>b1</em> with a copy of <code>rng1</code> and <em>b2</em> with
3027a copy of <code>rng2</code>.
3028  <pre>
3029    template&lt;class In&gt; xor_combine(In&amp; first, In last)
3030</pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine.
3031To construct the subobject <em>b1</em>, invokes the <code>b1(first,
3032last)</code> constructor. Then, to construct the subobject <em>b2</em>,
3033invokes 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&lt;class In&gt; void seed(In&amp; first, In last)
3040</pre><strong>Effects:</strong> Invokes <code><em>b1</em>.seed(first,
3041last)</code>, then invokes <code><em>b2</em>.seed(first, last)</code>.
3042  <pre>
3043    const base1_type&amp; base1() const
3044</pre><strong>Returns:</strong> <em>b1</em>
3045  <pre>
3046    const base2_type&amp; 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>() &lt;&lt; s1) ^
3051(<em>b2</em>() &lt;&lt; s2)</code>.
3052  <pre>
3053  template&lt;class CharT, class traits,
3054           class UniformRandomNumberGenerator1, int s1,
3055           class UniformRandomNumberGenerator2, int s2&gt;
3056  basic_ostream&lt;CharT, traits&gt;&amp; operator&lt;&lt;(basic_ostream&lt;CharT, traits&gt;&amp; os,
3057                                           const xor_combine&lt;UniformRandomNumberGenerator1, s1,
3058                                                             UniformRandomNumberGenerator2, s2&gt; &amp; 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>
3064namespace std {
3065  typedef linear_congruential&lt;/* <em>implementation defined</em> */, 16807, 0, 2147483647&gt; minstd_rand0;
3066  typedef linear_congruential&lt;/* <em>implementation defined</em> */, 48271, 0, 2147483647&gt; minstd_rand;
3067
3068  typedef mersenne_twister&lt;/* <em>implementation defined</em> */,32,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18&gt; mt19937;
3069
3070  typedef subtract_with_carry_01&lt;float, 24, 10, 24&gt; ranlux_base_01;
3071  typedef subtract_with_carry_01&lt;double, 48, 10, 24&gt; ranlux64_base_01;
3072
3073  typedef discard_block&lt;subtract_with_carry&lt;/* <em>implementation defined</em> */, (1&lt;&lt;24), 10, 24&gt;, 223, 24&gt; ranlux3;
3074  typedef discard_block&lt;subtract_with_carry&lt;/* <em>implementation defined</em> */, (1&lt;&lt;24), 10, 24&gt;, 389, 24&gt; ranlux4;
3075
3076  typedef discard_block&lt;subtract_with_carry_01&lt;float, 24, 10, 24&gt;, 223, 24&gt; ranlux3_01;
3077  typedef discard_block&lt;subtract_with_carry_01&lt;float, 24, 10, 24&gt;, 389, 24&gt; ranlux4_01;
3078}
3079</pre>For a default-constructed <code>minstd_rand0</code> object, x(10000) =
30801043618065. For a default-constructed <code>minstd_rand</code> object,
3081x(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>
3103namespace 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&amp; 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&amp; );
3119    void operator=(const random_device&amp; );
3120  };
3121}
3122</pre>
3123  <pre>
3124    explicit random_device(const std::string&amp; token = /* <em>implementation-defined</em> */)
3125</pre><strong>Effects:</strong> Constructs a <code>random_device</code>
3126non-deterministic random number engine. The semantics and default value of
3127the <code>token</code> parameter are implementation-defined. [Footnote: The
3128parameter is intended to allow an implementation to differentiate between
3129different 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&lt;result_type&gt;::min()</code>
3137  <pre>
3138    result_type max() const
3139</pre><strong>Returns:</strong>
3140<code>numeric_limits&lt;result_type&gt;::max()</code>
3141  <pre>
3142    double entropy() const
3143</pre><strong>Returns:</strong> An entropy estimate for the random numbers
3144returned 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
3146pseudo-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
3151distributed between <code>min()</code> and <code>max()</code>, inclusive. It
3152is 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  &lt;= x &lt;= 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>
3191namespace std {
3192  template&lt;class IntType = int&gt;
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&lt;class UniformRandomNumberGenerator&gt;
3206    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3207    template&lt;class UniformRandomNumberGenerator&gt;
3208    result_type operator()(UniformRandomNumberGenerator&amp; 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 &lt;= 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&amp; urng, result_type n)
3226</pre><strong>Returns:</strong> A uniform random number x in the range 0
3227&lt;= x &lt; n. <em>[Note: This allows a <code>variate_generator</code>
3228object with a <code>uniform_int</code> distribution to be used with
3229std::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>
3236namespace std {
3237  template&lt;class RealType = double&gt;
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&amp; p = RealType(0.5));
3247    RealType p() const;
3248    void reset();
3249    template&lt;class UniformRandomNumberGenerator&gt;
3250    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3251  };
3252}
3253</pre>
3254  <pre>
3255    bernoulli_distribution(const RealType&amp; p = RealType(0.5))
3256</pre><strong>Requires:</strong> 0 &lt;= p &lt;= 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> &gt;= 1 with p(i) = (1-p) * p<sup>i-1</sup>. p is the
3266  parameter of the distribution.
3267  <pre>
3268namespace std {
3269  template&lt;class IntType = int, class RealType = double&gt;
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&amp; p = RealType(0.5));
3279    RealType p() const;
3280    void reset();
3281    template&lt;class UniformRandomNumberGenerator&gt;
3282    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3283  };
3284}
3285</pre>
3286  <pre>
3287    geometric_distribution(const RealType&amp; p = RealType(0.5))
3288</pre><strong>Requires:</strong> 0 &lt; p &lt; 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> &gt;= 0 with p(i) = exp(-mean) * mean<sup>i</sup> / i!.
3298  mean is the parameter of the distribution.
3299  <pre>
3300namespace std {
3301  template&lt;class IntType = int, class RealType = double&gt;
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&amp; mean = RealType(1));
3311    RealType mean() const;
3312    void reset();
3313    template&lt;class UniformRandomNumberGenerator&gt;
3314    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3315  };
3316}
3317</pre>
3318  <pre>
3319    poisson_distribution(const RealType&amp; mean = RealType(1))
3320</pre><strong>Requires:</strong> mean &gt; 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> &gt;= 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>
3332namespace std {
3333  template&lt;class IntType = int, class RealType = double&gt;
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&amp; p = RealType(0.5));
3343    IntType t() const;
3344    RealType p() const;
3345    void reset();
3346    template&lt;class UniformRandomNumberGenerator&gt;
3347    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3348  };
3349}
3350</pre>
3351  <pre>
3352    binomial_distribution(IntType t = 1, const RealType&amp; p = RealType(0.5))
3353</pre><strong>Requires:</strong> 0 &lt;= p &lt;= 1 and t &gt;= 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 &lt;= x &lt;= 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>
3373namespace std {
3374  template&lt;class RealType = double&gt;
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&lt;class UniformRandomNumberGenerator&gt;
3388    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3389  };
3390}
3391</pre>
3392  <pre>
3393    uniform_real(RealType min = RealType(0), RealType max = RealType(1))
3394</pre><strong>Requires:</strong> min &lt;= 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 &gt; 0 distributed with probability density function p(x) =
3408  lambda * exp(-lambda * x), where lambda is the parameter of the
3409  distribution.
3410  <pre>
3411namespace std {
3412  template&lt;class RealType = double&gt;
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&amp; lambda = result_type(1));
3422    RealType lambda() const;
3423    void reset();
3424    template&lt;class UniformRandomNumberGenerator&gt;
3425    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3426  };
3427}
3428</pre>
3429  <pre>
3430    exponential_distribution(const result_type&amp; lambda = result_type(1))
3431</pre><strong>Requires:</strong> lambda &gt; 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>
3446namespace std {
3447  template&lt;class RealType = double&gt;
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 &amp; rng, const result_type&amp; mean = 0,
3457                                 const result_type&amp; sigma = 1);
3458    RealType mean() const;
3459    RealType sigma() const;
3460    void reset();
3461    template&lt;class UniformRandomNumberGenerator&gt;
3462    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3463  };
3464}
3465</pre>
3466  <pre>
3467    explicit normal_distribution( const result_type&amp; mean = 0,
3468                                 const result_type&amp; sigma = 1);
3469</pre><strong>Requires:</strong> sigma &gt; 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>
3486namespace std {
3487  template&lt;class RealType = double&gt;
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&amp; alpha = result_type(1));
3497    RealType alpha() const;
3498    void reset();
3499    template&lt;class UniformRandomNumberGenerator&gt;
3500    result_type operator()(UniformRandomNumberGenerator&amp; urng);
3501  };
3502}
3503</pre>
3504  <pre>
3505    explicit gamma_distribution(const result_type&amp; alpha = result_type(1));
3506</pre><strong>Requires:</strong> alpha &gt; 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&uuml;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 &copy; 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>
Note: See TracBrowser for help on using the repository browser.