NAG Library Function Document

nag_quasi_random_uniform (g05yac)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

To generate multidimensional quasi-random sequences with a uniform probability distribution.

2 Specification

#include <nag.h>

#include <nagg05.h>

void	nag_quasi_random_uniform (Nag_QuasiRandom_State state, Nag_QuasiRandom_Sequence seq, Integer iskip, Integer idim, double quasi[], Nag_QuasiRandom gf, NagError fail)

3 Description

Low discrepancy (quasi-random) sequences are used in numerical integration, simulation and optimization. Like pseudorandom numbers they are uniformly distributed but they are not statistically independent, rather they are designed to give more even distribution in multidimensional space (uniformity). Therefore they are often more efficient than pseudorandom numbers in multidimensional Monte–Carlo methods.

nag_quasi_random_uniform (g05yac) generates a set of points

x^{1}, x^{2}, \dots, x^{N}

with high uniformity in the

S

-dimensional unit cube

I^{S} = {[0, 1]}^{S}

. One measure of the uniformity is the discrepancy which is defined as follows:

Given a set of points $x^{1}, x^{2}, \dots, x^{N} \in I^{S}$ and a subset $G \subset I^{S}$ , define the counting function $S_{N} (G)$ as the number of points $x^{i} \in G$ . For each $x = (x_{1}, x_{2}, \dots, x_{S}) \in I^{S}$ , let $G_{x}$ be the rectangular $s$ -dimensional region
$G_{x} = [0, x_{1}) \times [0, x_{2}) \times \dots \times [0, x_{S})$
with volume $x_{1}, x_{2}, \dots, x_{S}$ . Then the discrepancy of the points $x^{1}, x^{2}, \dots, x^{N}$ is
$D_{N}^{*} (x^{1}, x^{2}, \dots, x^{N}) = \sup_{x \in I^{S}} |S_{N} (G_{x}) - N x_{1}, x_{2}, \dots, x_{S}| .$
The discrepancy of the first $N$ terms of such a sequence has the form
$D_{N}^{*} (x^{1}, x^{2}, \dots, x^{N}) \leq C_{S} {(\log N)}^{S} + O ({(\log N)}^{S - 1}) for all N \geq 2 .$

The principal aim in the construction of low-discrepancy sequences is to find sequences of points in $I^{S}$ with a bound of this form where the constant $C_{S}$ is as small as possible.

nag_quasi_random_uniform (g05yac) generates the low-discrepancy sequences proposed by Sobol, Faure and Niederreiter.

4 References

Bratley P and Fox B L (1988) Algorithm 659: implementing Sobol's quasirandom sequence generator ACM Trans. Math. Software 14(1) 88–100

Fox B L (1986) Algorithm 647: implementation and relative efficiency of quasirandom sequence generators ACM Trans. Math. Software 12(4) 362–376

5 Arguments

1: state – Nag_QuasiRandom_StateInput

On entry: the type of operation to perform.

$state = Nag_QuasiRandom_Init$: The first call for initialization, and there is no output via array quasi.
$state = Nag_QuasiRandom_Cont$: The sequence has been initialized by a prior call to nag_quasi_random_uniform (g05yac) with $state = Nag_QuasiRandom_Init$ . Random numbers are output via array quasi.
$state = Nag_QuasiRandom_Finish$: The final call to release memory, and no further random numbers are required for output via array quasi.

Constraint:

state = Nag_QuasiRandom_Init

Nag_QuasiRandom_Cont

Nag_QuasiRandom_Finish

2: seq – Nag_QuasiRandom_SequenceInput

On entry: the type of sequence to generate.

$seq = Nag_QuasiRandom_Sobol$: A Sobol sequence.
$seq = Nag_QuasiRandom_Nied$: A Niederreiter sequence.
$seq = Nag_QuasiRandom_Faure$: A Faure sequence.

Constraint:

seq = Nag_QuasiRandom_Sobol

Nag_QuasiRandom_Nied

Nag_QuasiRandom_Faure

3: iskip – IntegerInput

On entry: the number of terms in the sequence to skip on initialization.

$iskip = 0$: All the terms of the sequence are generated.
$iskip = k$: The first $k$ terms of the sequence are ignored and the first term of the sequence now corresponds to the $k$ th term of the sequence when $iskip = 0$ .

seq = Nag_QuasiRandom_Faure

, iskip is not referenced.

Constraint: if

seq = Nag_QuasiRandom_Nied

Nag_QuasiRandom_Sobol

and

state = Nag_QuasiRandom_Init

iskip \geq 0

4: idim – IntegerInput

On entry: the number of dimensions required.

Constraint:

1 \leq idim \leq 40

5: quasi[idim] – doubleOutput

On exit: the random numbers.

state = Nag_QuasiRandom_Cont

quasi [k - 1]

contains the random number for the

k

th dimension.

6: gf – Nag_QuasiRandom *Communication Structure

Workspace used to communicate information between calls to nag_quasi_random_uniform (g05yac). The contents of this structure should not be changed between calls.

7: fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_BAD_PARAM: On entry, seq is not valid: $seq = "〈value〉"$ .
NE_INITIALIZATION: Incorrect initialization.
NE_INT: On entry, $idim = 〈value〉$ .
Constraint: $idim \leq 40$ .; On entry, $idim = 〈value〉$ .
Constraint: $idim \geq 1$ .; On entry, $iskip = 〈value〉$ .
Constraint: $iskip \geq 0$ .; On entry, value of skip too large: $iskip = 〈value〉$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_TOO_MANY_CALLS: Too many calls to generator.

7 Accuracy

Not applicable.

8 Further Comments

The maximum length of the generated sequences is

2^{29} - 1

, this should be adequate for practical purposes. In the case of the Niederreiter generator nag_quasi_random_uniform (g05yac) jumps to the appropriate starting point, while for the Sobol generator it simply steps through the sequence. In consequence the Sobol generator with large values of iskip will take a significant amount of time.