public class FaureSequence extends Object implements Serializable, RandomSequence, Cloneable
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_1\right) \times \cdots \times \left[0,t_d\right), \,\, 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.
| Constructor and Description |
|---|
FaureSequence(int dim)
Creates a Faure sequence with the default base.
|
FaureSequence(int dim,
int base,
int nSkip)
Creates a Faure sequence.
|
| Modifier and Type | Method and Description |
|---|---|
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.
|
public FaureSequence(int dim)
dim - is the dimension of the sequence.public FaureSequence(int dim,
int base,
int nSkip)
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.public int getSkip()
public int getDimension()
getDimension in interface RandomSequencepublic int getBase()
public long getCount()
public double[] nextPoint()
nextPoint in interface RandomSequencedouble array, the next point in the sequence.public double nextDouble()
double array, the next sequence value.public static int nextPrime(int n)
n - is the first number to try as a prime.Copyright © 2020 Rogue Wave Software. All rights reserved.