Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/random/random-generators.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 17 years ago

added boost
File size: 34.0 KB
RevLine 
[12]1
2<html>
3
4<head>
5<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
6
7<title>Boost Random Number Library Generators</title>
8</head>
9
10<body bgcolor="#FFFFFF" text="#000000">
11
12<h1>Random Number Library Generators</h1>
13
14<ul>
15<li><a href="#intro">Introduction</a>
16<li><a href="#synopsis">Synopsis</a>
17<li><a href="#const_mod">Class template
18<code>random::const_mod</code></a>
19<li><a href="#linear_congruential">Class template
20<code>random::linear_congruential</code></a>
21<li><a href="#rand48">Class <code>rand48</code></a>
22<li><a href="#additive_combine">Class template
23<code>random::additive_combined</code></a>
24<li><a href="#shuffle_output">Class template
25<code>random::shuffle_output</code></a>
26<li><a href="#inversive_congruential">Class template
27<code>random::inversive_congruential</code></a>
28<li><a href="#mersenne_twister">Class template
29<code>random::mersenne_twister</code></a>
30<li><a href="#lagged_fibonacci">Class template
31<code>random::lagged_fibonacci</code></a>
32<li><a href="#performance">Performance</a>
33</ul>
34
35<h2><a name="intro">Introduction</a></h2>
36
37This library provides several pseudo-random number generators.  The
38quality of a pseudo-random number generator crucially depends on both
39the algorithm and its parameters.  This library implements the
40algorithms as class templates with template value parameters, hidden
41in namespace <code>boost::random</code>.  Any particular choice of
42parameters is represented as the appropriately specializing
43<code>typedef</code> in namespace <code>boost</code>.
44<p>
45
46Pseudo-random number generators should not be constructed
47(initialized) frequently during program execution, for two reasons.
48First, initialization requires full initialization of the internal
49state of the generator.  Thus, generators with a lot of internal state
50(see below) are costly to initialize.  Second, initialization always
51requires some value used as a "seed" for the generated sequence.  It
52is usually difficult to obtain several good seed values.  For example,
53one method to obtain a seed is to determine the current time at the
54highest resolution available, e.g. microseconds or nanoseconds.  When
55the pseudo-random number generator is initialized again with the
56then-current time as the seed, it is likely that this is at a
57near-constant (non-random) distance from the time given as the seed
58for first initialization.  The distance could even be zero if the
59resolution of the clock is low, thus the generator re-iterates the
60same sequence of random numbers.  For some applications, this is
61inappropriate.
62<p>
63
64Note that all pseudo-random number generators described below are
65CopyConstructible and Assignable.  Copying or assigning a generator
66will copy all its internal state, so the original and the copy will
67generate the identical sequence of random numbers.  Often, such
68behavior is not wanted.  In particular, beware of the algorithms from
69the standard library such as std::generate.  They take a functor
70argument by value, thereby invoking the copy constructor when called.
71<p>
72
73The following table gives an overview of some characteristics of the
74generators.  The cycle length is a rough estimate of the quality of
75the generator; the approximate relative speed is a performance
76measure, higher numbers mean faster random number generation.
77
78<p>
79<table border="1">
80<tr>
81<th>generator</th>
82<th>length of cycle</th>
83<th>approx. memory requirements</th>
84<th>approx. relative speed</th>
85<th>comment</th>
86</tr>
87
88<tr>
89<td><a href="#minstd_rand"><code>minstd_rand</code></a></td>
90<td>2<sup>31</sup>-2</td>
91<td><code>sizeof(int32_t)</code></td>
92<td>40</td>
93<td>-</td>
94</tr>
95
96<tr>
97<td><a href="#rand48"><code>rand48</code></a></td>
98<td>2<sup>48</sup>-1</td>
99<td><code>sizeof(uint64_t)</code></td>
100<td>80</td>
101<td>-</td>
102</tr>
103
104<tr>
105<td><code>lrand48</code> (C library)</td>
106<td>2<sup>48</sup>-1</td>
107<td>-</td>
108<td>20</td>
109<td>global state</td>
110</tr>
111
112<tr>
113<td><a href="#ecuyer1988"><code>ecuyer1988</code></a></td>
114<td>approx. 2<sup>61</sup></td>
115<td><code>2*sizeof(int32_t)</code></td>
116<td>20</td>
117<td>-</td>
118</tr>
119
120<tr>
121<td><code><a href="#kreutzer1986">kreutzer1986</a></code></td>
122<td>?</td>
123<td><code>1368*sizeof(uint32_t)</code></td>
124<td>60</td>
125<td>-</td>
126</tr>
127
128<tr>
129<td><code><a href="#hellekalek1995">hellekalek1995</a></code></td>
130<td>2<sup>31</sup>-1</td>
131<td><code>sizeof(int32_t)</code></td>
132<td>3</td>
133<td>good uniform distribution in several dimensions</td>
134</tr>
135
136<tr>
137<td><code><a href="#mt11213b">mt11213b</a></code></td>
138<td>2<sup>11213</sup>-1</td>
139<td><code>352*sizeof(uint32_t)</code></td>
140<td>100</td>
141<td>good uniform distribution in up to 350 dimensions</td>
142</tr>
143
144<tr>
145<td><code><a href="#mt19937">mt19937</a></code></td>
146<td>2<sup>19937</sup>-1</td>
147<td><code>625*sizeof(uint32_t)</code></td>
148<td>100</td>
149<td>good uniform distribution in up to 623 dimensions</td>
150</tr>
151
152<tr>
153<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci607</a></code></td>
154<td>approx. 2<sup>32000</sup></td>
155<td><code>607*sizeof(double)</code></td>
156<td>150</td>
157<td>-</td>
158</tr>
159
160<tr>
161<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci1279</a></code></td>
162<td>approx. 2<sup>67000</sup></td>
163<td><code>1279*sizeof(double)</code></td>
164<td>150</td>
165<td>-</td>
166</tr>
167
168<tr>
169<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci2281</a></code></td>
170<td>approx. 2<sup>120000</sup></td>
171<td><code>2281*sizeof(double)</code></td>
172<td>150</td>
173<td>-</td>
174</tr>
175
176<tr>
177<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci3217</a></code></td>
178<td>approx. 2<sup>170000</sup></td>
179<td><code>3217*sizeof(double)</code></td>
180<td>150</td>
181<td>-</td>
182</tr>
183
184<tr>
185<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci4423</a></code></td>
186<td>approx. 2<sup>230000</sup></td>
187<td><code>4423*sizeof(double)</code></td>
188<td>150</td>
189<td>-</td>
190</tr>
191
192<tr>
193<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci9689</a></code></td>
194<td>approx. 2<sup>510000</sup></td>
195<td><code>9689*sizeof(double)</code></td>
196<td>150</td>
197<td>-</td>
198</tr>
199
200<tr>
201<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci19937</a></code></td>
202<td>approx. 2<sup>1050000</sup></td>
203<td><code>19937*sizeof(double)</code></td>
204<td>150</td>
205<td>-</td>
206</tr>
207
208<tr>
209<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci23209</a></code></td>
210<td>approx. 2<sup>1200000</sup></td>
211<td><code>23209*sizeof(double)</code></td>
212<td>140</td>
213<td>-</td>
214</tr>
215
216<tr>
217<td><code><a href="#lagged_fibonacci_spec">lagged_fibonacci44497</a></code></td>
218<td>approx. 2<sup>2300000</sup></td>
219<td><code>44497*sizeof(double)</code></td>
220<td>60</td>
221<td>-</td>
222</tr>
223
224</table>
225
226<p>
227As observable from the table, there is generally a
228quality/performance/memory trade-off to be decided upon when choosing
229a random-number generator.  The multitude of generators provided in
230this library allows the application programmer to optimize the
231trade-off with regard to his application domain.  Additionally,
232employing several fundamentally different random number generators for
233a given application of Monte Carlo simulation will improve the
234confidence in the results.
235<p>
236
237If the names of the generators don't ring any bell and you have no
238idea which generator to use, it is reasonable to employ
239<code>mt19937</code> for a start: It is fast and has acceptable
240quality.
241
242<p>
243<em>Note:</em> These random number generators are not intended for use
244in applications where non-deterministic random numbers are required.
245See <a href="nondet_random.html">nondet_random.html</a> for a choice
246of (hopefully) non-deterministic random number generators.
247
248<p>
249In this description, I have refrained from documenting those members
250in detail which are already defined in the
251<a href="random-concepts.html">concept documentation</a>.
252
253
254<h2><a name="synopsis">Synopsis of the generators</a> available from header
255<code>&lt;boost/random.hpp&gt;</code></h2>
256
257<pre>
258namespace boost {
259  namespace random {
260    template&lt;class IntType, IntType m&gt;
261    class const_mod;
262    template&lt;class IntType, IntType a, IntType c, IntType m, IntType val&gt;
263    class linear_congruential;
264  }
265  class rand48;
266  typedef random::linear_congruential&lt; /* ... */ &gt; minstd_rand0;
267  typedef random::linear_congruential&lt; /* ... */ &gt; minstd_rand;
268
269  namespace random {
270    template&lt;class DataType, int w, int n, int m, int r, DataType a, int u,
271        int s, DataType b, int t, DataType c, int l, IntType val&gt;
272    class mersenne_twister;
273  }
274  typedef random::mersenne_twister&lt; /* ... */ &gt; mt11213b;
275  typedef random::mersenne_twister&lt; /* ... */ &gt; mt19937;
276
277  namespace random {
278    template&lt;class FloatType, unsigned int  p, unsigned int q&gt;
279    class lagged_fibonacci;
280  }
281  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci607;
282  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci1279;
283  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci2281;
284  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci3217;
285  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci4423;
286  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci9689;
287  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci19937;
288  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci23209;
289  typedef random::lagged_fibonacci&lt; /* ... */ &gt; lagged_fibonacci44497; 
290} // namespace boost
291</pre>
292
293
294<h2><a name="const_mod">Class template
295<code>random::const_mod</code></a></h2>
296
297<h3>Synopsis</h3>
298
299<pre>
300template&lt;class IntType, IntType m&gt;
301class random::const_mod
302{
303public:
304  template&lt;IntType c&gt;
305  static IntType add(IntType x);
306
307  template&lt;IntType a&gt;
308  static IntType mult(IntType x);
309
310  template&lt;IntType a, IntType c&gt;
311  static IntType mult_add(IntType x);
312
313  static IntType invert(IntType x);
314private:
315  const_mod();         // don't instantiate
316};
317</pre>
318
319<h3>Description</h3>
320
321Class template <code>const_mod</code> provides functions performing
322modular arithmetic, carefully avoiding overflows.  All member
323functions are static; there shall be no objects of type
324<code>const_mod&lt;&gt;</code>.
325<p>
326
327The template parameter <code>IntType</code> shall denote an integral
328type, <code>m</code> is the modulus.
329<p>
330
331<em>Note:</em> For modulo multiplications with large m, a trick allows
332fast computation under certain conditions, see
333<blockquote>
334"A more portable FORTRAN random number generator", Linus Schrage, ACM
335Transactions on Mathematical Software, Vol. 5, No. 2, June 1979, pp. 132-138
336</blockquote>
337
338
339<h3>Member functions</h3>
340
341<pre>template&lt;IntType c&gt; static IntType add(IntType x)</pre>
342
343<strong>Returns:</strong> (x+c) mod m
344
345<pre>template&lt;IntType a&gt; static IntType mult(IntType x)</pre>
346
347<strong>Returns:</strong> (a*x) mod m
348
349<pre>template&lt;IntType a, IntType c&gt; static IntType
350mult_add(IntType x)</pre>
351
352<strong>Returns:</strong> (a*x+c) mod m
353
354<pre>static IntType invert(IntType x)</pre>
355
356<strong>Returns:</strong> i so that (a*i) mod m == 1
357<br>
358<strong>Precondition:</strong> m is prime
359
360
361<h2><a name="linear_congruential">Class template
362<code>random::linear_congruential</code></a></h2>
363
364<h3>Synopsis</h3>
365
366<pre>
367#include &lt;<a href="../../boost/random/linear_congruential.hpp">boost/random/linear_congruential.hpp</a>&gt;
368
369template&lt;class IntType, IntType a, IntType c, IntType m, IntType val&gt;
370class linear_congruential
371{
372public:
373  typedef IntType result_type;
374  static const IntType multiplier = a;
375  static const IntType increment = c;
376  static const IntType modulus = m;
377  static const bool has_fixed_range = true;
378  static const result_type min_value;
379  static const result_type max_value;
380  explicit linear_congruential_fixed(IntType x0 = 1);
381  // compiler-generated copy constructor and assignment operator are fine
382  void seed(IntType x0);
383  IntType operator()();
384};
385
386typedef random::linear_congruential&lt;long, 16807L, 0, 2147483647L,
387     1043618065L&gt; minstd_rand0;
388typedef random::linear_congruential&lt;long, 48271L, 0, 2147483647L,
389     399268537L&gt; minstd_rand;
390</pre>
391
392<h3>Description</h3>
393
394Instantiations of class template <code>linear_congruential</code>
395model a <a href="random-concepts.html#pseudo-rng">pseudo-random number
396generator</a>.  Linear congruential pseudo-random number generators
397are described in:
398<blockquote>
399&quot;Mathematical methods in large-scale computing units&quot;, D. H. Lehmer,
400Proc. 2nd Symposium on Large-Scale Digital Calculating Machines,
401Harvard University Press, 1951, pp. 141-146
402</blockquote>
403
404Let x(n) denote the sequence of numbers returned by
405some pseudo-random number generator.  Then for the linear congruential
406generator, x(n+1) := (a * x(n) + c) mod m.  Parameters for the
407generator are x(0), a, c, m.
408
409The template parameter <code>IntType</code> shall denote an
410integral type.  It must be large enough to hold values a, c, and m.
411The template parameters a and c must be smaller than m.
412
413<p>
414
415<em>Note:</em> The quality of the generator crucially depends on the
416choice of the parameters.  User code should use one of the sensibly
417parameterized generators such as <code>minstd_rand</code> instead.
418<br>
419For each choice of the parameters a, c, m, some distinct type is
420defined, so that the <code>static</code> members do not interfere with
421regard to the one definition rule.
422
423<h3>Members</h3>
424
425<pre>explicit linear_congruential(IntType x0 = 1)</pre>
426
427<strong>Effects:</strong> Constructs a
428<code>linear_congruential</code> generator with x(0) :=
429<code>x0</code>.
430
431<pre>void seed(IntType x0)</pre>
432
433<strong>Effects:</strong> Changes the current value x(n) of the
434generator to <code>x0</code>.
435
436<h3><a name="minstd_rand">Specializations</a></h3>
437
438The specialization <code>minstd_rand0</code> was originally suggested
439in
440<blockquote>
441A pseudo-random number generator for the System/360, P.A. Lewis,
442A.S. Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, 1969,
443pp. 136-146
444</blockquote>
445
446It is examined more closely together with <code>minstd_rand</code> in
447<blockquote>
448"Random Number Generators: Good ones are hard to find", Stephen
449K. Park and Keith W. Miller, Communications of the ACM, Vol. 31,
450No. 10, October 1988, pp. 1192-1201
451</blockquote>
452
453
454<h2><a name="rand48">Class <code>rand48</code></h2>
455
456<h3>Synopsis</h3>
457<pre>
458#include &lt;<a href="../../boost/random/linear_congruential.hpp">boost/random/linear_congruential.hpp</a>&gt;
459
460class rand48
461{
462public:
463  typedef int32_t result_type;
464  static const bool has_fixed_range = true;
465  static const int32_t min_value = 0;
466  static const int32_t max_value = 0x7fffffff;
467 
468  explicit rand48(int32_t x0 = 1);
469  explicit rand48(uint64_t x0);
470  // compiler-generated copy ctor and assignment operator are fine
471  void seed(int32_t x0);
472  void seed(uint64_t x0);
473  int32_t operator()();
474};
475</pre>
476
477<h3>Description</h3>
478
479Class <code>rand48</code> models a
480<a href="random-concepts.html#pseudo-rng">pseudo-random number
481generator</a>.  It uses the linear congruential algorithm with the
482parameters a = 0x5DEECE66D, c = 0xB, m = 2**48.  It delivers identical
483results to the <code>lrand48()</code> function available on some
484systems (assuming <code>lcong48</code> has not been called).
485<p>
486It is only available on systems where <code>uint64_t</code> is
487provided as an integral type, so that for example static in-class
488constants and/or enum definitions with large <code>uint64_t</code>
489numbers work.
490
491<h3>Constructors</h3>
492
493<pre>rand48(int32_t x0)</pre>
494
495<strong>Effects:</strong> Constructs a <code>rand48</code> generator
496with x(0) := (<code>x0</code> << 16) | 0x330e.
497
498<pre>rand48(uint64_t x0)</pre>
499
500<strong>Effects:</strong> Constructs a <code>rand48</code> generator
501with x(0) := <code>x0</code>.
502
503<h3>Seeding</h3>
504<pre>void seed(int32_t x0)</pre>
505
506<strong>Effects:</strong> Changes the current value x(n) of the
507generator to (<code>x0</code> << 16) | 0x330e.
508
509<pre>void seed(uint64_t x0)</pre>
510
511<strong>Effects:</strong> Changes the current value x(n) of the
512generator to <code>x0</code>.
513
514
515<h2><a name="additive_combine">Class template
516<code>random::additive_combine</code></a></h2>
517
518<h3>Synopsis</h3>
519
520<pre>
521#include &lt;<a href="../../boost/random/additive_combine.hpp">boost/random/additive_combine.hpp</a>&gt;
522
523template&lt;class MLCG1, class MLCG2, typename MLCG1::result_type val&gt;
524class random::additive_combine
525{
526public:
527  typedef MLCG1 first_base;
528  typedef MLCG2 second_base;
529  typedef typename MLCG1::result_type result_type;
530  static const bool has_fixed_range = true;
531  static const result_type min_value = 1;
532  static const result_type max_value = MLCG1::max_value-1;
533  additive_combine();
534  additive_combine(typename MLCG1::result_type seed1,
535                   typename MLCG2::result_type seed2);
536  result_type operator()();
537  bool validation(result_type x) const;
538};
539
540typedef random::additive_combine&lt;
541    random::linear_congruential&lt;int32_t, 40014, 0, 2147483563, 0&gt;,
542    random::linear_congruential&lt;int32_t, 40692, 0, 2147483399, 0&gt;,
543  /* unknown */ 0&gt; ecuyer1988;
544
545</pre>
546
547<h3>Description</h3>
548
549Instatiations of class template <code>additive_combine</code> model a
550<a href="random-concepts.html#pseudo-rng">pseudo-random number
551generator</a>.  It combines two multiplicative linear congruential
552number generators, i.e. those with c = 0.  It is described in
553<blockquote>
554"Efficient and Portable Combined Random Number Generators", Pierre
555L'Ecuyer, Communications of the ACM, Vol. 31, No. 6, June 1988,
556pp. 742-749, 774
557</blockquote>
558
559The template parameters <code>MLCG1</code> and <code>MLCG2</code>
560shall denote two different linear congruential number generators, each
561with c = 0.  Each invocation returns a random number X(n) := (MLCG1(n)
562- MLCG2(n)) mod (m1 - 1), where m1 denotes the modulus of
563<code>MLCG1</code>.
564
565<p>
566The template parameter <code>val</code> is the validation value
567checked by <code>validation</code>.
568
569
570<h3>Members</h3>
571
572<pre>additive_combine()</pre>
573
574<strong>Effects:</strong> Constructs an <code>additive_combine</code>
575generator using the default constructors of the two base generators.
576
577<pre>additive_combine(typename MLCG1::result_type seed1,
578                 typename MLCG2::result_type seed2)</pre>
579
580<strong>Effects:</strong> Constructs an <code>additive_combine</code>
581generator, using <code>seed1</code> and <code>seed2</code> as the
582constructor argument to the first and second base generator,
583respectively.
584
585
586<h3><a name="ecuyer1988">Specialization</a></h3>
587
588The specialization <code>ecuyer1988</code> was suggested in the above
589paper.
590
591
592<h2><a name="shuffle_output">Class template
593<code>random::shuffle_output</code></a></h2>
594
595<h3>Synopsis</h3>
596
597<pre>
598#include &lt;<a href="../../boost/random/shuffle_output.hpp">boost/random/shuffle_output.hpp</a>&gt;
599
600template&lt;class UniformRandomNumberGenerator, int k,
601  typename UniformRandomNumberGenerator::result_type val = 0&gt;
602class random::shuffle_output
603{
604public:
605  typedef UniformRandomNumberGenerator base_type;
606  typedef typename base_type::result_type result_type;
607  static const bool has_fixed_range = false;
608
609  shuffle_output();
610  template&lt;class T&gt; explicit shuffle_output(T seed);
611  explicit shuffle_output(const base_type &amp; rng);
612  template&lt;class T&gt; void seed(T s);
613
614  result_type operator()();
615  result_type min() const;
616  result_type max() const;
617  bool validation(result_type) const;
618};
619</pre>
620
621<h3>Description</h3>
622
623Instatiations of class template <code>shuffle_output</code> model a
624<a href="random-concepts.html#pseudo-rng">pseudo-random number
625generator</a>. It mixes the output of some (usually linear
626congruential) uniform random number generator to get better
627statistical properties.  According to Donald E. Knuth, "The Art of
628Computer Programming, Vol. 2", the algorithm is described in
629<blockquote>
630"Improving a poor random number generator", Carter Bays and
631S.D. Durham, ACM Transactions on Mathematical Software, Vol. 2, 1979,
632pp. 59-64.
633</blockquote>
634The output of the base generator is buffered in an array of length
635k. Every output X(n) has a second role: It gives an index into the
636array where X(n+1) will be retrieved.  Used array elements are
637replaced with fresh output from the base generator.
638
639<p>
640
641Template parameters are the base generator and the array length k,
642which should be around 100.  The template parameter
643<code>val</code> is the validation value checked by
644<code>validation</code>.
645
646
647<h3>Members</h3>
648
649<pre>shuffle_output()</pre>
650
651<strong>Effects:</strong> Constructs a <code>shuffle_output</code>
652generator by invoking the default constructor of the base generator.
653<p>
654<strong>Complexity:</strong> Exactly k+1 invocations of the base
655generator.
656
657<pre>template&lt;class T&gt; explicit shuffle_output(T seed)</pre>
658
659<strong>Effects:</strong> Constructs a <code>shuffle_output</code>
660generator by invoking the one-argument constructor of the base
661generator with the parameter <code>seed</code>.
662<p>
663<strong>Complexity:</strong> Exactly k+1 invocations of the base
664generator.
665
666<pre>explicit shuffle_output(const base_type & rng)</pre>
667
668<strong>Precondition:</strong> The template argument
669<code>UniformRandomNumberGenerator</code> shall denote a
670CopyConstructible type.
671<p>
672<strong>Effects:</strong> Constructs a <code>shuffle_output</code>
673generator by using a copy of the provided generator.
674<p>
675<strong>Complexity:</strong> Exactly k+1 invocations of the base
676generator.
677
678<pre>template&lt;class T&gt; void seed(T s)</pre>
679
680<strong>Effects:</strong> Invokes the one-argument <code>seed</code>
681method of the base generator with the parameter <code>seed</code> and
682re-initializes the internal buffer array.
683<p>
684<strong>Complexity:</strong> Exactly k+1 invocations of the base
685generator.
686
687
688<h3><a name="kreutzer1986">Specializations</a></h3>
689
690According to Harry Erwin (private e-mail), the specialization
691<code>kreutzer1986</code> was suggested in:
692<blockquote>
693"System Simulation: programming Styles and Languages (International
694Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December
6951986.
696</blockquote>
697
698
699<h2><a name="inversive_congruential">Class template
700<code>random::inversive_congruential</code></a></h2> 
701
702<h3>Synopsis</h3>
703
704<pre>
705#include &lt;<a href="../../boost/random/inversive_congruential.hpp">boost/random/inversive_congruential.hpp</a>&gt;
706
707template&lt;class IntType, IntType a, IntType b, IntType p&gt;
708class random::inversive_congruential
709{
710public:
711  typedef IntType result_type;
712  static const bool has_fixed_range = true;
713  static const result_type min_value = (b == 0 ? 1 : 0);
714  static const result_type max_value = p-1;
715  static const result_type multiplier = a;
716  static const result_type increment = b;
717  static const result_type modulus = p;
718  explicit inversive_congruential(IntType y0 = 1);
719  void seed(IntType y0);
720  IntType operator()();
721};
722
723typedef random::inversive_congruential&lt;int32_t, 9102, 2147483647-36884165, 2147483647&gt; hellekalek1995;
724</pre>
725
726<h3>Description</h3>
727
728Instantiations of class template <code>inversive_congruential</code> model a
729<a href="random-concepts.html#pseudo-rng">pseudo-random number
730generator</a>.  It uses the inversive congruential algorithm (ICG)
731described in
732<blockquote>
733"Inversive pseudorandom number generators: concepts, results and
734links", Peter Hellekalek, In: "Proceedings of the 1995 Winter
735Simulation Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and
736D. Goldsman (editors), 1995, pp. 255-262.
737<a href="ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps">ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps</a>
738</blockquote>
739
740The output sequence is defined by x(n+1) = (a*inv(x(n)) - b) (mod p),
741where x(0), a, b, and the prime number p are parameters of the
742generator.  The expression inv(k) denotes the multiplicative inverse
743of k in the field of integer numbers modulo p, with inv(0) := 0.
744
745<p>
746
747The template parameter <code>IntType</code> shall denote a signed
748integral type large enough to hold p; a, b, and p are the parameters
749of the generators.
750<p>
751<em>Note:</em> The implementation currently uses the Euclidian
752Algorithm to compute the multiplicative inverse.  Therefore, the
753inversive generators are about 10-20 times slower than the others (see
754section"<a href="#performance">performance</a>").  However, the paper
755talks of only 3x slowdown, so the Euclidian Algorithm is probably not
756optimal for calculating the multiplicative inverse.
757
758
759<h3>Members</h3>
760
761<pre>inversive_congruential(IntType y0 = 1)</pre>
762
763<strong>Effects:</strong> Constructs an
764<code>inversive_congruential</code> generator with
765<code>y0</code> as the initial state.
766
767<pre>void seed(IntType y0)</pre>
768
769<strong>Effects:</strong>
770Changes the current state to <code>y0</code>.
771
772
773<h3><a name="hellekalek1995">Specialization</a></h3>
774
775The specialization <code>hellekalek1995</code> was suggested in the
776above paper.
777
778
779<h2><a name="mersenne_twister">Class template
780<code>random::mersenne_twister</code></a></h2>
781
782<h3>Synopsis</h3>
783
784<pre>
785#include &lt;<a href="../../boost/random/mersenne_twister.hpp">boost/random/mersenne_twister.hpp</a>&gt;
786
787template&lt;class DataType, int w, int n, int m, int r, DataType a, int u,
788int s, DataType b, int t, DataType c, int l, IntType val&gt;
789class random::mersenne_twister
790{
791public:
792  typedef DataType result_type;
793  static const bool has_fixed_range = true;
794  static const result_type min_value;
795  static const result_type max_value;
796  mersenne_twister();
797  explicit mersenne_twister(DataType value);
798  template&lt;class Generator&gt; explicit mersenne_twister(Generator &amp; gen);
799  // compiler-generated copy ctor and assignment operator are fine
800  void seed();
801  void seed(DataType value);
802  template&lt;class Generator&gt; void seed(Generator &amp; gen);
803  result_type operator()();
804  bool validation(result_type) const;
805};
806
807typedef mersenne_twister&lt;uint32_t,351,175,19,0xccab8ee7,11,7,0x31b6ab00,15,0xffe50000,17, /* unknown */ 0&gt; mt11213b;
808typedef mersenne_twister&lt;uint32_t,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18, 3346425566U&gt; mt19937;
809</pre>
810
811<h3>Description</h3>
812
813Instantiations of class template <code>mersenne_twister</code> model a
814<a href="random-concepts.html#pseudo-rng">pseudo-random number
815generator</a>.  It uses the algorithm described in
816
817<blockquote>
818"Mersenne Twister: A 623-dimensionally equidistributed uniform
819pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura,
820ACM Transactions on Modeling and Computer Simulation: Special Issue
821on Uniform Random Number Generation, Vol. 8, No. 1, January 1998,
822pp. 3-30.
823<!-- <a href="http://www.math.keio.ac.jp/matumoto/emt.html">http://www.math.keio.ac.jp/matumoto/emt.html</a> -->
824</blockquote>
825
826<em>Note:</em> The boost variant has been implemented from scratch
827and does not derive from or use mt19937.c provided on the above WWW
828site. However, it was verified that both produce identical output.
829<br>
830The seeding from an integer was changed in April 2005 to address a
831<a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>.
832
833<br>
834The quality of the generator crucially depends on the choice of the
835parameters.  User code should employ one of the sensibly parameterized
836generators such as <code>mt19937</code> instead.
837<br>
838The generator requires considerable amounts of memory for the storage
839of its state array.  For example, <code>mt11213b</code> requires about
8401408 bytes and <code>mt19937</code> requires about 2496 bytes.
841
842<h3>Constructors</h3>
843
844<pre>mersenne_twister()</pre>
845
846<strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
847and calls <code>seed()</code>.
848
849<pre>explicit mersenne_twister(result_type value)</pre>
850
851<strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
852and calls <code>seed(value)</code>.
853
854<pre>template&lt;class Generator&gt; explicit mersenne_twister(Generator &amp; gen)</pre>
855
856<strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
857and calls <code>seed(gen)</code>.
858<p>
859<em>Note:</em> When using direct-initialization syntax with an lvalue
860(e.g. in the variable definition <code>Gen gen2(gen);</code>), this
861templated constructor will be preferred over the compiler-generated
862copy constructor.  For variable definitions which should copy the
863state of another <code>mersenne_twister</code>, use e.g. <code>Gen
864gen2 = gen;</code>, which is copy-initialization syntax and guaranteed
865to invoke the copy constructor.
866
867<h3>Seeding</h3>
868
869<pre>void seed()</pre>
870
871<strong>Effects:</strong> Calls <code>seed(result_type(5489))</code>.
872
873<pre>void seed(result_type value)</pre>
874
875<strong>Effects:</strong> 
876Sets the state x(0) to v mod 2<sup>w</sup>.  Then,
877iteratively,<br> sets x(i) to (i + 1812433253 * (x(i-1) <em>xor</em>
878(x(i-1) <em>rshift</em> w-2))) mod 2<sup>w</sup> for i = 1 .. n-1.
879x(n) is the first value to be returned by operator().
880
881<pre>template&lt;class Generator&gt; void seed(Generator &amp; gen)</pre>
882
883<strong>Effects:</strong> Sets the state of this
884<code>mersenne_twister</code> to the values returned by <code>n</code>
885invocations of <code>gen</code>.
886
887<p>
888
889<strong>Complexity:</strong> Exactly <code>n</code> invocations of
890<code>gen</code>.
891<p>
892<em>Note:</em> When invoking <code>seed</code> with an lvalue,
893overload resolution chooses the function template unless the type of
894the argument exactly matches <code>result_type</code>.  For other
895integer types, you should convert the argument to
896<code>result_type</code> explicitly.
897
898<h3><a name="mt11213b"></a><a name="mt19937">Specializations</a></h3>
899
900The specializations <code>mt11213b</code> and <code>mt19937</code> are
901from the paper cited above.
902
903<h2><a name="lagged_fibonacci">Class template
904<code>random::lagged_fibonacci</code></a></h2>
905
906<h3>Synopsis</h3>
907
908<pre>
909#include &lt;<a href="../../boost/random/lagged_fibonacci.hpp">boost/random/lagged_fibonacci.hpp</a>&gt;
910
911template&lt;class FloatType, unsigned int p, unsigned int q&gt;
912class lagged_fibonacci
913{
914public:
915  typedef FloatType result_type;
916  static const bool has_fixed_range = false;
917  static const unsigned int long_lag = p;
918  static const unsigned int short_lag = q;
919  result_type min() const { return 0.0; }
920  result_type max() const { return 1.0; }
921  lagged_fibonacci();
922  explicit lagged_fibonacci(uint32_t value);
923  template&lt;class Generator&gt;
924  explicit lagged_fibonacci(Generator & gen);
925  // compiler-generated copy ctor and assignment operator are fine
926  void seed(uint32_t value = 331u);
927  template&lt;class Generator&gt; void seed(Generator & gen);
928  result_type operator()();
929  bool validation(result_type x) const;
930};
931
932typedef random::lagged_fibonacci&lt;double, 607, 273&gt; lagged_fibonacci607;
933typedef random::lagged_fibonacci&lt;double, 1279, 418&gt; lagged_fibonacci1279;
934typedef random::lagged_fibonacci&lt;double, 2281, 1252&gt; lagged_fibonacci2281;
935typedef random::lagged_fibonacci&lt;double, 3217, 576&gt; lagged_fibonacci3217;
936typedef random::lagged_fibonacci&lt;double, 4423, 2098&gt; lagged_fibonacci4423;
937typedef random::lagged_fibonacci&lt;double, 9689, 5502&gt; lagged_fibonacci9689;
938typedef random::lagged_fibonacci&lt;double, 19937, 9842&gt; lagged_fibonacci19937;
939typedef random::lagged_fibonacci&lt;double, 23209, 13470&gt; lagged_fibonacci23209;
940typedef random::lagged_fibonacci&lt;double, 44497, 21034&gt; lagged_fibonacci44497;
941</pre>
942
943<h3>Description</h3>
944
945Instantiations of class template <code>lagged_fibonacci</code> model a
946<a href="random-concepts.html#pseudo-rng">pseudo-random number
947generator</a>.  It uses a lagged Fibonacci algorithm with two lags p
948and q, evaluated in floating-point arithmetic:  x(i) = x(i-p) + x(i-q)
949(mod 1) with p > q.  See
950
951<blockquote>
952"Uniform random number generators for supercomputers", Richard Brent,
953Proc. of Fifth Australian Supercomputer Conference, Melbourne,
954Dec. 1992, pp. 704-706.
955</blockquote>
956
957<p>
958<em>Note:</em> The quality of the generator crucially depends on the
959choice of the parameters.  User code should employ one of the sensibly
960parameterized generators such as <code>lagged_fibonacci607</code>
961instead.
962<br>
963The generator requires considerable amounts of memory for the storage
964of its state array.  For example, <code>lagged_fibonacci607</code>
965requires about 4856 bytes and <code>lagged_fibonacci44497</code>
966requires about 350 KBytes.
967
968<h3>Constructors</h3>
969
970<pre>lagged_fibonacci()</pre>
971<strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code>
972generator and calls <code>seed()</code>.
973
974<pre>explicit lagged_fibonacci(uint32_t value)</pre>
975<strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code>
976generator and calls <code>seed(value)</code>.
977
978<pre>template&lt;class Generator&gt; explicit lagged_fibonacci(Generator &amp; gen)</pre>
979<strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code>
980generator and calls <code>seed(gen)</code>.
981
982<h3>Seeding</h3>
983
984<pre>void seed()</pre>
985<strong>Effects:</strong> Calls <code>seed(331u)</code>.
986
987<pre>void seed(uint32_t value)</pre>
988<strong>Effects:</strong> Constructs a <code>minstd_rand0</code>
989generator with the constructor parameter <code>value</code> and calls
990<code>seed</code> with it.
991
992<pre>template&lt;class Generator&gt; void seed(Generator &amp; gen)</pre>
993<strong>Effects:</strong> Sets the state of this
994<code>lagged_fibonacci</code> to the values returned by <code>p</code>
995invocations of <code>uniform_01&lt;gen, FloatType&gt;</code>.
996<br>
997<strong>Complexity:</strong> Exactly <code>p</code> invocations of
998<code>gen</code>.
999
1000<h3><a name="lagged_fibonacci_spec"></a>Specializations</h3>
1001The specializations <code>lagged_fibonacci607</code>
1002... <code>lagged_fibonacci44497</code> (see above) use well tested
1003lags. (References will be added later.)
1004
1005
1006<h2><a name="performance">Performance</a></h2>
1007
1008The test program <a href="random_speed.cpp">random_speed.cpp</a>
1009measures the execution times of the
1010<a href="../../boost/random.hpp">random.hpp</a> implementation of the above
1011algorithms in a tight loop.  The performance has been evaluated on a
1012Pentium Pro 200 MHz with gcc 2.95.2, Linux 2.2.13, glibc 2.1.2.
1013
1014<p>
1015
1016<table border=1>
1017<tr><th>class</th><th>time per invocation [usec]</th></tr>
1018<tr><td>rand48</td><td>0.096</td></tr>
1019<tr><td>rand48 run-time configurable</td><td>0.697</td></tr>
1020<tr><td>lrand48 glibc 2.1.2</td><td>0.844</td></tr>
1021<tr><td>minstd_rand</td><td>0.174</td></tr>
1022<tr><td>ecuyer1988</td><td>0.445</td></tr>
1023<tr><td>kreutzer1986</td><td>0.249</td></tr>
1024<tr><td>hellekalek1995 (inversive)</td><td>4.895</td></tr>
1025<tr><td>mt11213b</td><td>0.165</td></tr>
1026<tr><td>mt19937</td><td>0.165</td></tr>
1027<tr><td>mt19937 original</td><td>0.185</td></tr>
1028<tr><td>lagged_fibonacci607</td><td>0.111</td></tr>
1029<tr><td>lagged_fibonacci4423</td><td>0.112</td></tr>
1030<tr><td>lagged_fibonacci19937</td><td>0.113</td></tr>
1031<tr><td>lagged_fibonacci23209</td><td>0.122</td></tr>
1032<tr><td>lagged_fibonacci44497</td><td>0.263</td></tr>
1033</table>
1034
1035<p>
1036The measurement error is estimated at +/- 10 nsec.
1037
1038<p>
1039<hr>
1040Jens Maurer, 2001-04-15
1041
1042</body>
1043</html>
Note: See TracBrowser for help on using the repository browser.