faure_next

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

int ndim (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.

Synopsis with Optional Arguments

#include <imsls.h>

Imsls_faure *imsls_faure_sequence_init(int ndim,
IMSLS_BASE, int base,
IMSLS_SKIP, int skip,
0)

float *imsls_f_faure_next_point(Imsls_faure *state,
IMSLS_RETURN_USER, float *user,
IMSLS_RETURN_SKIP, int *skip,
0)

Optional Arguments

IMSLS_BASE, int base (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 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 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.

#include "stdio.h"

#include "imsls.h"

int main()

{

Imsls_faure *state;

float *x;

int ndim = 3;

int k;

state = imsls_faure_sequence_init(ndim, 0);

for (k = 0; k < 5; k++) {

x = imsls_f_faure_next_point(state, 0);

printf("%10.3f %10.3f %10.3f\n", x[0], x[1], x[2]);

imsls_free(x);

}

imsls_faure_sequence_free(state);

return 0;

}

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