]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/ |
2 | / Copyright (c) 2009-2010 Steven Watanabe | |
3 | / | |
4 | / Distributed under the Boost Software License, Version 1.0. (See | |
5 | / accompanying file LICENSE_1_0.txt or copy at | |
6 | / http://www.boost.org/LICENSE_1_0.txt) | |
7 | ] | |
8 | ||
9 | This library provides several [prng pseudo-random number generators]. The | |
10 | quality of a [prng pseudo random number generator] crucially depends on both | |
11 | the algorithm and its parameters. This library implements the algorithms as | |
12 | class templates with template value parameters, hidden in | |
13 | `namespace boost::random`. Any particular choice of parameters is represented | |
14 | as the appropriately specializing `typedef` in `namespace boost`. | |
15 | ||
16 | [prng Pseudo-random number generators] should not be constructed (initialized) | |
17 | frequently during program execution, for two reasons. First, initialization | |
18 | requires full initialization of the internal state of the generator. Thus, | |
19 | generators with a lot of internal state (see below) are costly to initialize. | |
20 | Second, initialization always requires some value used as a "seed" for the | |
21 | generated sequence. It is usually difficult to obtain several good seed | |
22 | values. For example, one method to obtain a seed is to determine the current | |
23 | time at the highest resolution available, e.g. microseconds or nanoseconds. | |
24 | When the [prng pseudo-random number generator] is initialized again with the | |
25 | then-current time as the seed, it is likely that this is at a near-constant | |
26 | (non-random) distance from the time given as the seed for first | |
27 | initialization. The distance could even be zero if the resolution of the | |
28 | clock is low, thus the generator re-iterates the same sequence of random | |
29 | numbers. For some applications, this is inappropriate. | |
30 | ||
31 | Note that all [prng pseudo-random number generators] described below are | |
32 | __CopyConstructible and __Assignable. Copying or assigning a generator will | |
33 | copy all its internal state, so the original and the copy will generate the | |
34 | identical sequence of random numbers. Often, such behavior is not wanted. In | |
35 | particular, beware of the algorithms from the standard library such as | |
36 | `std::generate`. They take a functor argument by value, thereby invoking the | |
37 | copy constructor when called. | |
38 | ||
39 | The following table gives an overview of some characteristics of the | |
40 | generators. The cycle length is a rough estimate of the quality of the | |
41 | generator; the approximate relative speed is a performance measure, higher | |
42 | numbers mean faster random number generation. | |
43 | ||
44 | [table generators | |
45 | [[generator] [length of cycle] [approx. memory requirements] [approx. speed compared to fastest] [comment]] | |
46 | [[__minstd_rand0] [2[sup 31]-2] [`sizeof(int32_t)`] [[minstd_rand0_speed]] [-]] | |
47 | [[__minstd_rand] [2[sup 31]-2] [`sizeof(int32_t)`] [[minstd_rand_speed]] [-]] | |
48 | [[__rand48][2[sup 48]-1] [`sizeof(uint64_t)`] [[rand48_speed]] [-]] | |
49 | [[__ecuyer1988] [approx. 2[sup 61]] [`2*sizeof(int32_t)`] [[ecuyer_combined_speed]] [-]] | |
50 | [[__knuth_b] [?] [`257*sizeof(uint32_t)`] [[knuth_b_speed]] [-]] | |
51 | [[__kreutzer1986] [?] [`98*sizeof(uint32_t)`] [[kreutzer1986_speed]] [-]] | |
52 | [[__taus88] [~2[sup 88]] [`3*sizeof(uint32_t)`] [[taus88_speed]] [-]] | |
53 | [[__hellekalek1995] [2[sup 31]-1] [`sizeof(int32_t)`] [[hellekalek1995__inversive__speed]] [good uniform distribution in several dimensions]] | |
54 | [[__mt11213b] [2[sup 11213]-1] [`352*sizeof(uint32_t)`] [[mt11213b_speed]] [good uniform distribution in up to 350 dimensions]] | |
55 | [[__mt19937] [2[sup 19937]-1] [`625*sizeof(uint32_t)`] [[mt19937_speed]] [good uniform distribution in up to 623 dimensions]] | |
56 | [[__mt19937_64] [2[sup 19937]-1] [`312*sizeof(uint64_t)`] [[mt19937_64_speed]] [good uniform distribution in up to 311 dimensions]] | |
57 | [[__lagged_fibonacci607] [~2[sup 32000]] [`607*sizeof(double)`] [[lagged_fibonacci607_speed]] [-]] | |
58 | [[__lagged_fibonacci1279] [~2[sup 67000]] [`1279*sizeof(double)`] [[lagged_fibonacci1279_speed]] [-]] | |
59 | [[__lagged_fibonacci2281] [~2[sup 120000]] [`2281*sizeof(double)`] [[lagged_fibonacci2281_speed]] [-]] | |
60 | [[__lagged_fibonacci3217] [~2[sup 170000]] [`3217*sizeof(double)`] [[lagged_fibonacci3217_speed]] [-]] | |
61 | [[__lagged_fibonacci4423] [~2[sup 230000]] [`4423*sizeof(double)`] [[lagged_fibonacci4423_speed]] [-]] | |
62 | [[__lagged_fibonacci9689] [~2[sup 510000]] [`9689*sizeof(double)`] [[lagged_fibonacci9689_speed]] [-]] | |
63 | [[__lagged_fibonacci19937] [~2[sup 1050000]] [`19937*sizeof(double)`] [[lagged_fibonacci19937_speed]] [-]] | |
64 | [[__lagged_fibonacci23209] [~2[sup 1200000]] [`23209*sizeof(double)`] [[lagged_fibonacci23209_speed]] [-]] | |
65 | [[__lagged_fibonacci44497] [~2[sup 2300000]] [`44497*sizeof(double)`] [[lagged_fibonacci44497_speed]] [-]] | |
66 | [[__ranlux3] [~10[sup 171]] [`24*sizeof(int)`] [[ranlux3_speed]] [-]] | |
67 | [[__ranlux4] [~10[sup 171]] [`24*sizeof(int)`] [[ranlux4_speed]] [-]] | |
68 | [[__ranlux64_3] [~10[sup 171]] [`24*sizeof(int64_t)`] [[ranlux64_3_speed]] [-]] | |
69 | [[__ranlux64_4] [~10[sup 171]] [`24*sizeof(int64_t)`] [[ranlux64_4_speed]] [-]] | |
70 | [[__ranlux3_01] [~10[sup 171]] [`24*sizeof(float)`] [[ranlux3_speed]] [-]] | |
71 | [[__ranlux4_01] [~10[sup 171]] [`24*sizeof(float)`] [[ranlux4_speed]] [-]] | |
72 | [[__ranlux64_3_01] [~10[sup 171]] [`24*sizeof(double)`] [[ranlux64_3_speed]] [-]] | |
73 | [[__ranlux64_4_01] [~10[sup 171]] [`24*sizeof(double)`] [[ranlux64_4_speed]] [-]] | |
74 | [[__ranlux24] [~10[sup 171]] [`24*sizeof(uint32_t)`] [[ranlux24_speed]] [-]] | |
75 | [[__ranlux48] [~10[sup 171]] [`12*sizeof(uint64_t)`] [[ranlux48_speed]] [-]] | |
76 | ] | |
77 | ||
78 | As observable from the table, there is generally a quality/performance/memory | |
79 | trade-off to be decided upon when choosing a random-number generator. The | |
80 | multitude of generators provided in this library allows the application | |
81 | programmer to optimize the trade-off with regard to his application domain. | |
82 | Additionally, employing several fundamentally different random number | |
83 | generators for a given application of Monte Carlo simulation will improve | |
84 | the confidence in the results. | |
85 | ||
86 | If the names of the generators don't ring any bell and you have no idea | |
87 | which generator to use, it is reasonable to employ __mt19937 for a start: It | |
88 | is fast and has acceptable quality. | |
89 | ||
90 | [note These random number generators are not intended for use in applications | |
91 | where non-deterministic random numbers are required. See __random_device | |
92 | for a choice of (hopefully) non-deterministic random number generators.] |