ceph/src/boost/libs/random/doc/generators.qbk

   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.]