Chapter 12: Random Number Generation > faure_next_point

faure_next_point

     

Computes a shuffled Faure sequence.

Synopsis

#include <imsls.h>

Imsls_faure* imsls_faure_sequence_init (int ndim,, 0)

float* imsls_f_faure_next_point (Imsls_faure *state,, 0)

void imsls_faure_sequence_free (Imsls_faure *state)

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)

floatimsls_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 bd. The lowest bound for the discrepancy is obtained for the smallest prime bd, 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]);
             free(x);

   }

 

   imsls_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


RW_logo.jpg
Contact Support