This chapter describes functions for generating quasi-random sequences in arbitrary dimensions.  A quasi-random sequence progressively covers a 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 gsl_qrng.h.

Quasi-random number generator initialization
============================================

 -- Function: gsl_qrng * gsl_qrng_alloc (const gsl_qrng_type * T, unsigned int D)
     This function returns a pointer to a newly-created instance of a quasi-random sequence generator of type T and dimension 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 GSL_ENOMEM.

 -- Function: void gsl_qrng_free (gsl_qrng * Q)
     This function frees all the memory associated with the generator Q.

 -- Function: void gsl_qrng_init (gsl_qrng * Q)
     This function reinitializes the generator Q to its starting point. Note that quasi-random sequences do not use a seed and always produce the same set of values.

Sampling from a quasi-random number generator
=============================================

 -- Function: int gsl_qrng_get (const gsl_qrng * Q, double X[])
     This function stores the next point from the sequence generator Q in the array X.  The space available for X must match the dimension of the generator.  The point X will lie in the range 0 < x_i < 1 for each x_i.  inlinefn

Auxiliary quasi-random number generator functions
=================================================

 -- Function: const char * gsl_qrng_name (const gsl_qrng * Q)
     This function returns a pointer to the name of the generator.

 -- Function: size_t gsl_qrng_size (const gsl_qrng * Q)
 -- Function: void * gsl_qrng_state (const gsl_qrng * Q)
     These functions return a pointer to the state of generator 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,

          void * state = gsl_qrng_state (q);
          size_t n = gsl_qrng_size (q);
          fwrite (state, n, 1, stream);

Saving and restoring quasi-random number generator state
========================================================

 -- Function: int gsl_qrng_memcpy (gsl_qrng * DEST, const gsl_qrng * SRC)
     This function copies the quasi-random sequence generator SRC into the pre-existing generator DEST, making DEST into an exact copy of SRC.  The two generators must be of the same type.

 -- Function: gsl_qrng * gsl_qrng_clone (const gsl_qrng * Q)
     This function returns a pointer to a newly created generator which is an exact copy of the generator Q.

Quasi-random number generator algorithms
========================================

The following quasi-random sequence algorithms are available,

 -- Generator: gsl_qrng_niederreiter_2
     This generator uses the algorithm described in Bratley, Fox, Niederreiter, ACM Trans. Model. Comp. Sim. 2, 195 (1992). It is valid up to 12 dimensions.

 -- Generator: gsl_qrng_sobol
     This generator uses the Sobol sequence described in Antonov, Saleev, USSR Comput. Maths. Math. Phys. 19, 252 (1980). It is valid up to 40 dimensions.

 -- Generator: gsl_qrng_halton
 -- Generator: gsl_qrng_reversehalton
     These generators use the Halton and reverse Halton sequences described in J.H. Halton, Numerische Mathematik 2, 84-90 (1960) and B. Vandewoestyne and R. Cools Computational and Applied Mathematics 189, 1&2, 341-361 (2006).  They are valid up to 1229 dimensions.

Examples
========

The following program prints the first 1024 points of the 2-dimensional Sobol sequence.

          [file qrng.c not included]

Here is the output from the program,

     $ ./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
     ....

It can be seen that successive points progressively fill-in the spaces between previous points.

References
==========

The implementations of the quasi-random sequence routines are based on the algorithms described in the following paper,

  P. Bratley and B.L. Fox and H. Niederreiter, ``Algorithm 738: Programs to Generate Niederreiter's Low-discrepancy Sequences'', ACM Transactions on Mathematical Software, Vol. 20, No. 4, December, 1994, p. 494--495.