Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: f8153114c8
Fetching contributors…

Cannot retrieve contributors at this time

175 lines (142 sloc) 6.022 kb
@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})
@tpindex gsl_qrng
@tpindex 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 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
@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{}
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
Jump to Line
Something went wrong with that request. Please try again.