IMSL C Math Library
faure_next_point
Computes a shuffled Faure sequence.
Synopsis
#include <imsl.h>
Imsl_faure *imsl_faure_sequence_init (int ndim, …, 0)
float *imsl_f_faure_next_point (Imsl_faure *state, …, 0)
void imsl_faure_sequence_free (Imsl_faure *state)
The type double function is imsl_d_faure_next_point. The functions imsl_faure_sequence_init and imsl_faure_sequence_free are precision independent.
Required Arguments for imsl_faure_sequence_init
int ndim (Input)
The dimension of the hyper-rectangle.
Return Value for imsl_faure_sequence_init
Returns a structure that contains information about the sequence. The structure should be freed using imsl_faure_sequence_free after it is no longer needed.
Required Arguments for imsl_faure_next_point
Imsl_faure *state (Input/Output)
Structure created by a call to imsl_faure_sequence_init.
Return Value for imsl_faure_next_point
Returns the next point in the shuffled Faure sequence. To release this space, use imsl_free.
Required Arguments for imsl_faure_sequence_free
Imsl_faure *state (Input/Output)
Structure created by a call to imsl_faure_sequence_init.
Synopsis with Optional Arguments
#include <imsl.h>
float *imsl_faure_sequence_init (int ndim,
IMSL_BASE, int base,
IMSL_SKIP, int skip,
0)
float *imsl_f_faure_next_point (Imsl_faure *state,
IMSL_RETURN_USER, float *user,
IMSL_RETURN_SKIP, int *skip,
0)
Optional Arguments
IMSL_BASE, int base (Input)
The base of the Faure sequence.
Default: The smallest prime greater than or equal to ndim.
IMSL_SKIP, int *skip (Input)
The number of points to be skipped at the beginning of the Faure sequence.
Default: , where and B is the largest representable integer.
IMSL_RETURN_USER, float *user (Output)
User-supplied array of length ndim containing the current point in the sequence.
IMSL_RETURN_SKIP, int *skip (Output)
The current point in the sequence. The sequence can be restarted by initializing a new sequence using this value for IMSL_SKIP, and using the same dimension for ndim.
Description
Discrepancy measures the deviation from uniformity of a point set.
The discrepancy of the point set , is
where the supremum is over all subsets of [0, 1]d of the form
λ is the Lebesque measure, and is the number of the xj contained in E.
The sequence x1, x2, …of points [0,1]d is a low-discrepancy sequence if there exists a constant c(d), depending only on d, such that
for all n>1.
Generalized Faure sequences can be defined for any prime base b≥d. The lowest bound for the discrepancy is obtained for the smallest prime b≥d, so the optional argument IMSL_BASE defaults to the smallest prime greater than or equal to the dimension.
The generalized Faure sequence x1, x2, …, is computed as follows:
Write the positive integer n in its b-ary expansion,
where ai(n) are integers, .
The j-th coordinate of xn is
The generator matrix for the series, , is defined to be
and is an element of the Pascal matrix,
It is faster to compute a shuffled Faure sequence than to compute the Faure sequence itself. It can be shown that this shuffling preserves the low-discrepancy property.
The shuffling used is the b-ary Gray code. The function G(n) maps the positive integer n into the integer given by its b-ary expansion.
The sequence computed by this function is x(G(n)), where x is the generalized Faure sequence.
Example
In this example, five points in the Faure sequence are computed. The points are in the three-dimensional unit cube.
Note that imsl_faure_sequence_init (see Synopsis) is used to create a structure that holds the state of the sequence. Each call to imsl_f_faure_next_point returns the next point in the sequence and updates the Imsl_faure structure. The final call to imsl_fauer_sequence_free (see Synopsis) frees data items, stored in the structure, that were allocated by imsl_faure_sequence_init.
 
#include <stdio.h>
#include <imsl.h>
 
 
int main()
{
Imsl_faure *state;
float *x;
int ndim = 3;
int k;
state = imsl_faure_sequence_init(ndim, 0);
 
for (k = 0; k < 5; k++) {
x = imsl_f_faure_next_point(state, 0);
printf("%10.3f %10.3f %10.3f\n", x[0], x[1], x[2]);
imsl_free(x);
}
 
imsl_faure_sequence_free(state);
}
Output
 
0.334 0.493 0.064
0.667 0.826 0.397
0.778 0.270 0.175
0.111 0.604 0.509
0.445 0.937 0.842