htswanalysis/MACS/lib/gsl/gsl-1.11/doc/qrng.texi

   1 @cindex quasi-random sequences
   2 @cindex low discrepancy sequences
   3 @cindex Sobol sequence
   4 @cindex Niederreiter sequence
   5 This chapter describes functions for generating quasi-random sequences
   6 in arbitrary dimensions.  A quasi-random sequence progressively covers a
   7 @math{d}-dimensional space with a set of points that are uniformly
   8 distributed.  Quasi-random sequences are also known as low-discrepancy
   9 sequences.  The quasi-random sequence generators use an interface that
  10 is similar to the interface for random number generators, except that
  11 seeding is not required---each generator produces a single sequence.
  12
  13 The functions described in this section are declared in the header file
  14 @file{gsl_qrng.h}.
  15
  16 @menu
  17 * Quasi-random number generator initialization::
  18 * Sampling from a quasi-random number generator::
  19 * Auxiliary quasi-random number generator functions::
  20 * Saving and resorting quasi-random number generator state::
  21 * Quasi-random number generator algorithms::
  22 * Quasi-random number generator examples::
  23 * Quasi-random number references::
  24 @end menu
  25
  26 @node Quasi-random number generator initialization
  27 @section Quasi-random number generator initialization
  28
  29 @deftypefun {gsl_qrng *} gsl_qrng_alloc (const gsl_qrng_type * @var{T}, unsigned int @var{d})
  30 This function returns a pointer to a newly-created instance of a
  31 quasi-random sequence generator of type @var{T} and dimension @var{d}.
  32 If there is insufficient memory to create the generator then the
  33 function returns a null pointer and the error handler is invoked with an
  34 error code of @code{GSL_ENOMEM}.
  35 @end deftypefun
  36
  37 @deftypefun void gsl_qrng_free (gsl_qrng * @var{q})
  38 This function frees all the memory associated with the generator
  39 @var{q}.
  40 @end deftypefun
  41
  42 @deftypefun void gsl_qrng_init (gsl_qrng * @var{q})
  43 This function reinitializes the generator @var{q} to its starting point.
  44 Note that quasi-random sequences do not use a seed and always produce
  45 the same set of values.
  46 @end deftypefun
  47
  48 @node Sampling from a quasi-random number generator
  49 @section Sampling from a quasi-random number generator
  50
  51 @deftypefun int gsl_qrng_get (const gsl_qrng * @var{q}, double @var{x}[])
  52 This function stores the next point from the sequence generator @var{q}
  53 in the array @var{x}.  The space available for @var{x} must match the
  54 dimension of the generator.  The point @var{x} will lie in the range
  55 @math{0 < x_i < 1} for each @math{x_i}.  @inlinefn{}
  56 @end deftypefun
  57
  58 @node Auxiliary quasi-random number generator functions
  59 @section Auxiliary quasi-random number generator functions
  60
  61 @deftypefun {const char *} gsl_qrng_name (const gsl_qrng * @var{q})
  62 This function returns a pointer to the name of the generator.
  63 @end deftypefun
  64
  65 @deftypefun size_t gsl_qrng_size (const gsl_qrng * @var{q})
  66 @deftypefunx {void *} gsl_qrng_state (const gsl_qrng * @var{q})
  67 These functions return a pointer to the state of generator @var{r} and
  68 its size.  You can use this information to access the state directly.  For
  69 example, the following code will write the state of a generator to a
  70 stream,
  71
  72 @example
  73 void * state = gsl_qrng_state (q);
  74 size_t n = gsl_qrng_size (q);
  75 fwrite (state, n, 1, stream);
  76 @end example
  77 @end deftypefun
  78
  79
  80 @node Saving and resorting quasi-random number generator state
  81 @section Saving and resorting quasi-random number generator state
  82
  83 @deftypefun int gsl_qrng_memcpy (gsl_qrng * @var{dest}, const gsl_qrng * @var{src})
  84 This function copies the quasi-random sequence generator @var{src} into the
  85 pre-existing generator @var{dest}, making @var{dest} into an exact copy
  86 of @var{src}.  The two generators must be of the same type.
  87 @end deftypefun
  88
  89 @deftypefun {gsl_qrng *} gsl_qrng_clone (const gsl_qrng * @var{q})
  90 This function returns a pointer to a newly created generator which is an
  91 exact copy of the generator @var{q}.
  92 @end deftypefun
  93
  94 @node Quasi-random number generator algorithms
  95 @section Quasi-random number generator algorithms
  96
  97 The following quasi-random sequence algorithms are available,
  98
  99 @deffn {Generator} gsl_qrng_niederreiter_2
 100 This generator uses the algorithm described in Bratley, Fox,
 101 Niederreiter, @cite{ACM Trans. Model. Comp. Sim.} 2, 195 (1992). It is
 102 valid up to 12 dimensions.
 103 @end deffn
 104
 105 @deffn {Generator} gsl_qrng_sobol
 106 This generator uses the Sobol sequence described in Antonov, Saleev,
 107 @cite{USSR Comput. Maths. Math. Phys.} 19, 252 (1980). It is valid up to
 108 40 dimensions.
 109 @end deffn
 110
 111 @deffn {Generator} gsl_qrng_halton
 112 @deffnx {Generator} gsl_qrng_reverse_halton
 113 These generators use the Halton and reverse Halton sequences described
 114 in J.H. Halton, @cite{Numerische Mathematik} 2, 84-90 (1960) and
 115 B. Vandewoestyne and R. Cools @cite{Computational and Applied
 116 Mathematics} 189, 1&2, 341-361 (2006).  They are valid up to 1229
 117 dimensions.
 118 @end deffn
 119
 120 @node Quasi-random number generator examples
 121 @section Examples
 122
 123 The following program prints the first 1024 points of the 2-dimensional
 124 Sobol sequence.
 125
 126 @example
 127 @verbatiminclude examples/qrng.c
 128 @end example
 129
 130 @noindent
 131 Here is the output from the program,
 132
 133 @example
 134 $ ./a.out
 135 0.50000 0.50000
 136 0.75000 0.25000
 137 0.25000 0.75000
 138 0.37500 0.37500
 139 0.87500 0.87500
 140 0.62500 0.12500
 141 0.12500 0.62500
 142 ....
 143 @end example
 144
 145 @noindent
 146 It can be seen that successive points progressively fill-in the spaces
 147 between previous points.
 148
 149 @iftex
 150 @need 4000
 151 The following plot shows the distribution in the x-y plane of the first
 152 1024 points from the Sobol sequence,
 153 @sp 1
 154 @center @image{qrng,3.4in}
 155 @sp 1
 156 @center Distribution of the first 1024 points
 157 @center from the quasi-random Sobol sequence
 158 @end iftex
 159
 160 @node Quasi-random number references
 161 @section References
 162
 163 The implementations of the quasi-random sequence routines are based on
 164 the algorithms described in the following paper,
 165
 166 @itemize @asis
 167 P. Bratley and B.L. Fox and H. Niederreiter, ``Algorithm 738: Programs
 168 to Generate Niederreiter's Low-discrepancy Sequences'', @cite{ACM
 169 Transactions on Mathematical Software}, Vol.@: 20, No.@: 4, December, 1994,
 170 p.@: 494--495.
 171 @end itemize
 172