Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

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

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