| @cindex quasi-random sequences |
| @cindex low discrepancy sequences |
| @cindex Sobol sequence |
| @cindex Niederreiter sequence |
| This chapter describes functions for generating quasi-random sequences |
| in arbitrary dimensions. A quasi-random sequence progressively covers a |
| @math{d}-dimensional space with a set of points that are uniformly |
| distributed. Quasi-random sequences are also known as low-discrepancy |
| sequences. The quasi-random sequence generators use an interface that |
| is similar to the interface for random number generators, except that |
| seeding is not required---each generator produces a single sequence. |
| |
| The functions described in this section are declared in the header file |
| @file{gsl_qrng.h}. |
| |
| @menu |
| * Quasi-random number generator initialization:: |
| * Sampling from a quasi-random number generator:: |
| * Auxiliary quasi-random number generator functions:: |
| * Saving and resorting quasi-random number generator state:: |
| * Quasi-random number generator algorithms:: |
| * Quasi-random number generator examples:: |
| * Quasi-random number references:: |
| @end menu |
| |
| @node Quasi-random number generator initialization |
| @section Quasi-random number generator initialization |
| |
| @deftypefun {gsl_qrng *} gsl_qrng_alloc (const gsl_qrng_type * @var{T}, unsigned int @var{d}) |
| This function returns a pointer to a newly-created instance of a |
| quasi-random sequence generator of type @var{T} and dimension @var{d}. |
| If there is insufficient memory to create the generator then the |
| function returns a null pointer and the error handler is invoked with an |
| error code of @code{GSL_ENOMEM}. |
| @end deftypefun |
| |
| @deftypefun void gsl_qrng_free (gsl_qrng * @var{q}) |
| This function frees all the memory associated with the generator |
| @var{q}. |
| @end deftypefun |
| |
| @deftypefun void gsl_qrng_init (gsl_qrng * @var{q}) |
| This function reinitializes the generator @var{q} to its starting point. |
| Note that quasi-random sequences do not use a seed and always produce |
| the same set of values. |
| @end deftypefun |
| |
| @node Sampling from a quasi-random number generator |
| @section Sampling from a quasi-random number generator |
| |
| @deftypefun int gsl_qrng_get (const gsl_qrng * @var{q}, double @var{x}[]) |
| This function stores the next point from the sequence generator @var{q} |
| in the array @var{x}. The space available for @var{x} must match the |
| dimension of the generator. The point @var{x} will lie in the range |
| @math{0 < x_i < 1} for each @math{x_i}. |
| @end deftypefun |
| |
| @node Auxiliary quasi-random number generator functions |
| @section Auxiliary quasi-random number generator functions |
| |
| @deftypefun {const char *} gsl_qrng_name (const gsl_qrng * @var{q}) |
| This function returns a pointer to the name of the generator. |
| @end deftypefun |
| |
| @deftypefun size_t gsl_qrng_size (const gsl_qrng * @var{q}) |
| @deftypefunx {void *} gsl_qrng_state (const gsl_qrng * @var{q}) |
| These functions return a pointer to the state of generator @var{r} and |
| its size. You can use this information to access the state directly. For |
| example, the following code will write the state of a generator to a |
| stream, |
| |
| @example |
| void * state = gsl_qrng_state (q); |
| size_t n = gsl_qrng_size (q); |
| fwrite (state, n, 1, stream); |
| @end example |
| @end deftypefun |
| |
| |
| @node Saving and resorting quasi-random number generator state |
| @section Saving and resorting quasi-random number generator state |
| |
| @deftypefun int gsl_qrng_memcpy (gsl_qrng * @var{dest}, const gsl_qrng * @var{src}) |
| This function copies the quasi-random sequence generator @var{src} into the |
| pre-existing generator @var{dest}, making @var{dest} into an exact copy |
| of @var{src}. The two generators must be of the same type. |
| @end deftypefun |
| |
| @deftypefun {gsl_qrng *} gsl_qrng_clone (const gsl_qrng * @var{q}) |
| This function returns a pointer to a newly created generator which is an |
| exact copy of the generator @var{q}. |
| @end deftypefun |
| |
| @node Quasi-random number generator algorithms |
| @section Quasi-random number generator algorithms |
| |
| The following quasi-random sequence algorithms are available, |
| |
| @deffn {Generator} gsl_qrng_niederreiter_2 |
| This generator uses the algorithm described in Bratley, Fox, |
| Niederreiter, @cite{ACM Trans. Model. Comp. Sim.} 2, 195 (1992). It is |
| valid up to 12 dimensions. |
| @end deffn |
| |
| @deffn {Generator} gsl_qrng_sobol |
| This generator uses the Sobol sequence described in Antonov, Saleev, |
| @cite{USSR Comput. Maths. Math. Phys.} 19, 252 (1980). It is valid up to |
| 40 dimensions. |
| @end deffn |
| |
| @node Quasi-random number generator examples |
| @section Examples |
| |
| The following program prints the first 1024 points of the 2-dimensional |
| Sobol sequence. |
| |
| @example |
| @verbatiminclude examples/qrng.c |
| @end example |
| |
| @noindent |
| Here is the output from the program, |
| |
| @example |
| $ ./a.out |
| 0.50000 0.50000 |
| 0.75000 0.25000 |
| 0.25000 0.75000 |
| 0.37500 0.37500 |
| 0.87500 0.87500 |
| 0.62500 0.12500 |
| 0.12500 0.62500 |
| .... |
| @end example |
| |
| @noindent |
| It can be seen that successive points progressively fill-in the spaces |
| between previous points. |
| |
| @iftex |
| @need 4000 |
| The following plot shows the distribution in the x-y plane of the first |
| 1024 points from the Sobol sequence, |
| @sp 1 |
| @center @image{qrng,3.4in} |
| @sp 1 |
| @center Distribution of the first 1024 points |
| @center from the quasi-random Sobol sequence |
| @end iftex |
| |
| @node Quasi-random number references |
| @section References |
| |
| The implementations of the quasi-random sequence routines are based on |
| the algorithms described in the following paper, |
| |
| @itemize @asis |
| P. Bratley and B.L. Fox and H. Niederreiter, ``Algorithm 738: Programs |
| to Generate Niederreiter's Low-discrepancy Sequences'', @cite{ACM |
| Transactions on Mathematical Software}, Vol.@: 20, No.@: 4, December, 1994, |
| p.@: 494--495. |
| @end itemize |
| |