faure_next

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,

float *imsl_f_faure_next_point (Imsl_faure *state,

IMSL_RETURN_USER, float *user,

IMSL_RETURN_SKIP, int *skip,

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