The type double function is imsls_d_faure_next_point. The functions imsls_faure_sequence_init and imsls_faure_sequence_free are precision independent.
Required Arguments for imsls_faure_sequence_init
intndim (Input) The dimension of the hyper-rectangle.
Return Value for imsls_faure_sequence_init
Returns a structure that contains information about the sequence. The structure should be freed using imsls_faure_sequence_free after it is no longer needed.
Required Arguments for imsls_faure_next_point
Imsls_faure*state (Input/Output) Structure created by a call to imsls_faure_sequence_init.
Return Value for imsls_faure_next_point
Returns the next point in the shuffled Faure sequence. To release this space, use imsls_faure_sequence_free.
Required Arguments for imsls_faure_sequence_free
Imsls_faure *state (Input/Output) Structure created by a call to imsls_faure_sequence_init.
IMSLS_BASE, intbase (Input) The base of the Faure sequence.
Default: The smallest prime greater than or equal to ndim.
IMSLS_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.
IMSLS_RETURN_USER, float*user (Output) User-supplied array of length ndim containing the current point in the sequence.
IMSLS_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 IMSLS_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 IMSLS_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 xis 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 imsls_faure_sequence_init is used to create a structure that holds the state of the sequence. Each call to imsls_f_faure_next_point returns the next point in the sequence and updates the Imsls_faure structure. The final call to imsls_faure_sequence_free frees data items, stored in the structure, that were allocated by imsls_faure_sequence_init.
