1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
@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})
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}.
@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
@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 @asis
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
|
