.. index::
   single: quasi-random sequences
   single: low discrepancy sequences
   single: Sobol sequence
   single: Niederreiter sequence

**********************
Quasi-Random Sequences
**********************

.. include:: include.rst

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

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

.. type:: gsl_qrng

   This is a workspace for computing quasi-random sequences.

.. 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 :data:`T` and dimension :data:`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 :macro:`GSL_ENOMEM`.

.. function:: void gsl_qrng_free (gsl_qrng * q)

   This function frees all the memory associated with the generator
   :data:`q`.

.. function:: void gsl_qrng_init (gsl_qrng * q)

   This function reinitializes the generator :data:`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 :data:`q`
   in the array :data:`x`.  The space available for :data:`x` must match the
   dimension of the generator.  The point :data:`x` will lie in the range
   :math:`0 < x_i < 1` for each :math:`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)
              void * gsl_qrng_state (const gsl_qrng * q)

   These functions return a pointer to the state of generator :data:`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 :data:`src` into the
   pre-existing generator :data:`dest`, making :data:`dest` into an exact copy
   of :data:`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 :data:`q`.

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

The following quasi-random sequence algorithms are available,

.. type:: gsl_qrng_type

   .. var:: gsl_qrng_type * 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.

   .. var:: gsl_qrng_type * 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.

   .. var:: gsl_qrng_type * gsl_qrng_halton
            gsl_qrng_type * 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.

.. include:: examples/qrng.c
   :code:

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. 

:numref:`fig_qrng` shows the distribution in the x-y plane of the first
1024 points from the Sobol sequence,

.. _fig_qrng:

.. figure:: /images/qrng.png
   :scale: 60%

   Distribution of the first 1024 points 
   from the quasi-random Sobol sequence

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.