Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_33_1/libs/random/wg21-proposal.html @ 13

Last change on this file since 13 was 12, checked in by landauf, 17 years ago
added boost
File size: 119.9 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: