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

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.
@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 returns the next point @var{x} from the sequence generator
@var{q}.  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 function 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{r}.
@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
#include <stdio.h>
#include <gsl/gsl_qrng.h>

int
main (void)
@{
  int i;
  gsl_qrng * q = gsl_qrng_alloc (gsl_qrng_sobol, 2);

  for (i = 0; i < 1024; i++)
    @{
      double v[2];
      gsl_qrng_get(q, v);
      printf("%.5f %.5f\n", v[0], v[1]);
    @}

  gsl_qrng_free(q);
  return 0;
@}
@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
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}
@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'', Transactions on
Mathematical Software, Vol. 20, No. 4, December, 1994, p. 494-495.
@end itemize

