JMSLTM Numerical Library 4.0

com.imsl.stat
Class FaureSequence

java.lang.Object
  extended bycom.imsl.stat.FaureSequence
All Implemented Interfaces:
Cloneable, RandomSequence, Serializable

public class FaureSequence
extends Object
implements Serializable, RandomSequence, Cloneable

Generates the low-discrepancy Faure sequence.

Discrepancy measures the deviation from uniformity of a point set.

The discrepancy of the point set x_1,ldots,x_n in [0,1]^d,, d ge 1, is

D_n^{(d)} = sup_E 
      left| frac{A(E;n)}{n} - lambda(E) right|,

where the supremum is over all subsets of [0,1]^d of the form

E = left[0,t_1right) times cdots  times left[0,t_dright), ,,
          0 le t_j le 1, , 1 le j le d,

lambda is the Lebesque measure, and A(E;n) is the number of the x_j contained in E.

The sequence x_1, x_2, ldots of points in [0,1]^d is a low-discrepancy sequence if there exists a constant c(d), depending only on d, such that

D_n^{(d)} le c(d) frac{(log n)^d}{n}

for all n gt 1.

Generalized Faure sequences can be defined for any prime base b ge d. The lowest bound for the discrepancy is obtained for the smallest prime b ge d, so the base defaults to the smallest prime greater than or equal to the dimension.

The generalized Faure sequence x_1, x_2, ldots, is computed as follows:

Write the positive integer n in its b-ary expansion,

n=sum_{i=0}^infty a_i(n)b^i

where a_i(n) are integers, 0 le a_j(n) lt b.

The j-th coordinate of x_n is

x_n^{(j)} = sum_{k=0}^infty sum_{d=0}^infty
          c_{kd}^{(j)} a_d(n) b^{-k-1},
          ,,  1 le j le d

The generator matrix for the series, c_{kd}^{(j)}, is defined to be

c_{kd}^{(j)} = j^{d-k} c_{kd}

and c_{kd} is an element of the Pascal matrix,

c_{kd} = left{ begin{array}{ll}
          frac{d!}{c! (d-c)!} & k le d  \
          0  & k gt d
      end{array}  right.

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 vec{x}(G(n)), where vec{x} is the generalized Faure sequence.

See Also:
Example, Serialized Form

Field Summary
static long serialVersionUID
           
 
Constructor Summary
FaureSequence(int dim)
          Creates a Faure sequence with the default base.
FaureSequence(int dim, int base, int nSkip)
          Creates a Faure sequence.
 
Method Summary
 Object clone()
          Returns a copy of this object.
 int getBase()
          Returns the base.
 long getCount()
           
 int getDimension()
          Returns the dimension of the sequence.
 int getSkip()
          Returns the number of points skipped at the beginning of the sequence.
 double nextDouble()
          Returns the first value of the next point in the sequence.
 double[] nextPoint()
          Returns the next point in the sequence.
static int nextPrime(int n)
          Returns the smallest prime greater than or equal to n.
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

public static final long serialVersionUID
See Also:
Constant Field Values
Constructor Detail

FaureSequence

public FaureSequence(int dim)
Creates a Faure sequence with the default base. The base defaults to the smallest prime equal to or greater than dim.

Parameters:
dim - is the dimension of the sequence.

FaureSequence

public FaureSequence(int dim,
                     int base,
                     int nSkip)
Creates a Faure sequence.

Parameters:
dim - is the dimension of the sequence.
base - is the base of the sequence, as described above. It must be at least as large as dim.
nSkip - is the number of initial points to skip. If negative then {it base}^{m/2-1}, where m is the number of digits needed to represent the Integer.MAX_VALUE in the base, points are skipped.
Method Detail

clone

public Object clone()
Returns a copy of this object.


getBase

public int getBase()
Returns the base.


getCount

public long getCount()

getDimension

public int getDimension()
Returns the dimension of the sequence.

Specified by:
getDimension in interface RandomSequence

getSkip

public int getSkip()
Returns the number of points skipped at the beginning of the sequence.


nextDouble

public double nextDouble()
Returns the first value of the next point in the sequence. This method is intended for use when dim is 1.

Returns:
a double array, the next sequence value.

nextPoint

public double[] nextPoint()
Returns the next point in the sequence.

Specified by:
nextPoint in interface RandomSequence
Returns:
a double array, the next point in the sequence.

nextPrime

public static int nextPrime(int n)
Returns the smallest prime greater than or equal to n.

Parameters:
n - is the first number to try as a prime.
Returns:
a prime greater than or equal to n. If n is less than or equal to 2 then 2 is returned.

JMSLTM Numerical Library 4.0

Copyright 1970-2006 Visual Numerics, Inc.
Built June 1 2006.