@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 restoring 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})
@tindex gsl_qrng
@tindex gsl_qrng_type
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}.  @inlinefn{}
@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 restoring quasi-random number generator state
@section Saving and restoring 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

@deffn {Generator} gsl_qrng_halton
@deffnx {Generator} gsl_qrng_reversehalton
These generators use the Halton and reverse Halton sequences described
in J.H. Halton, @cite{Numerische Mathematik} 2, 84-90 (1960) and
B. Vandewoestyne and R. Cools @cite{Computational and Applied
Mathematics} 189, 1&2, 341-361 (2006).  They are valid up to 1229
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 @w{}
@item
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