SSJ
V. labo.

umontreal.iro.lecuyer.hups
Class RadicalInverse

java.lang.Object
  extended by umontreal.iro.lecuyer.hups.RadicalInverse

public class RadicalInverse
extends Object

RadicalInverse

This class implements basic methods for working with radical inverses of integers in an arbitrary basis b. These methods are used in classes that implement point sets and sequences based on the van der Corput sequence (the Hammersley nets and the Halton sequence, for example).

We recall that for a k-digit integer i whose digital b-ary expansion is

i = a0 + a1b + ... + ak-1bk-1,

the radical inverse in base b is

ψb(i) = a0b-1 + a1b-2 + ... + ak-1b-k.

The van der Corput sequence in base b is the sequence ψb(0), ψb(1), ψb(2),...

Note that ψb(i) cannot always be represented exactly as a floating-point number on the computer (e.g., if b is not a power of two). For an exact representation, one can use the integer

bkψb(i) = ak-1 + ... + a1bk-2 + a0bk-1,

which we called the integer radical inverse representation. This representation is simply a mirror image of the digits of the usual b-ary representation of i.

It is common practice to permute locally the values of the van der Corput sequence. One way of doing this is to apply a permutation to the digits of i before computing ψb(i). That is, for a permutation π of the digits {0,..., b - 1},

ψb(i) = $\displaystyle \htsum_{{r=0}}^{{k-1}}$arb-r-1

is replaced by

[tex2html_wrap_indisplay534]π(ar)b-r-1.

Applying such a permutation only changes the order in which the values of ψb(i) are enumerated. For every integer k, the first bk values that are enumerated remain the same (they are the values of ψb(i) for i = 0,..., bk - 1), but they are enumerated in a different order. Often, different permutations π will be applied for different coordinates of a point set.

The permutation π can be deterministic or random. One (deterministic) possibility implemented here is the Faure permutation σb of {0,..., b - 1} defined as follows[#!rFAU92a!#]. For b = 2, take σ = I, the identical permutation. For even b = 2c > 2, take

σ[i] = 2τ[i]        i = 0, 1,…, c - 1  
σ[i + c] = 2τ[i] + 1        i = 0, 1,…, c - 1  

where τ[i] is the Faure permutation for base c. For odd b = 2c + 1, take
σ[c] = c  
σ[i] = τ[i],         if 0≤τ[i] < c  
σ[i] = τ[i] + 1,         if cτ[i] < 2c  

for 0≤i < c, and take
σ[i] = τ[i - 1],         if 0≤τ[i - 1] < c  
σ[i] = τ[i - 1] + 1,         if cτ[i - 1] < 2c  

for c < i≤2c, and where τ[i] is the Faure permutation for base c. The Faure permutations give very small discrepancies (amongst the best known today) for small bases.


Constructor Summary
RadicalInverse(int b, double x0)
          .
 
Method Summary
static void getFaureLemieuxPermutation(int coordinate, int[] pi)
          .
static void getFaurePermutation(int b, int[] pi)
          .
static int[] getPrimes(int n)
          .
static int integerRadicalInverse(int b, int i)
          .
 double nextRadicalInverse()
          .
static double nextRadicalInverse(double invb, double x)
          .
static int nextRadicalInverseDigits(int b, int k, int[] idigits)
          .
static double permutedRadicalInverse(int b, int[] pi, long i)
          .
static double radicalInverse(int b, long i)
          .
static int radicalInverseInteger(int b, double x)
          .
static long radicalInverseLong(int b, double x)
          [tabb86]
bbase used for the operation xthe value for which the radical inverse will be computed the radical inverse of x in base b
static void reverseDigits(int k, int[] bdigits, int[] idigits)
          .
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

RadicalInverse

public RadicalInverse(int b,
                      double x0)
. \begin{tabb}
 Initializes the base of this object to $b$
 and its first value of $x$\ to \texttt{x0}.
 \end{tabb}
bBase x0Initial value of x

Method Detail

getPrimes

public static int[] getPrimes(int n)
. \begin{tabb}
 Provides an elementary method for obtaining the first $n$\ prime
 ...
 ...he different coordinates of the Halton sequence and Hammersley nets.
 \end{tabb}
nnumber of prime numbers to return an array with the first n prime numbers


radicalInverse

public static double radicalInverse(int b,
                                    long i)
. \begin{tabb}
 Computes the radical inverse of $i$\ in base $b$.
 If $i=\htsum_{r...
 ...displaymath}
 x = \htsum_{r=0}^{k-1} a_r b^{-r-1}.
 \end{displaymath} \end{tabb}
bbase used for the operation ithe value for which the radical inverse will be computed the radical inverse of i in base b


radicalInverseInteger

public static int radicalInverseInteger(int b,
                                        double x)
. \begin{tabb}
 Computes the radical inverse of $x$\ in base $b$.
 If $x$\ has more ...
 ...egin{displaymath}
 i = \htsum_{r=0}^{k-1} a_r b^r.
 \end{displaymath} \end{tabb}
bbase used for the operation xthe value for which the radical inverse will be computed the radical inverse of x in base b


radicalInverseLong

public static long radicalInverseLong(int b,
                                      double x)
[tabb86]
bbase used for the operation xthe value for which the radical inverse will be computed the radical inverse of x in base b


nextRadicalInverse

public static double nextRadicalInverse(double invb,
                                        double x)
. \begin{tabb}
 A fast method that incrementally computes the radical inverse $x_{...
 ...nverse}{} every once in a while (i.e. in every few
 thousand calls).
 \end{tabb}
invb1/b where b is the base xthe inverse xi the radical inverse xi+1


nextRadicalInverse

public double nextRadicalInverse()
. \begin{tabb}
 A fast method that incrementally computes the radical inverse $x_{...
 ...$i$\ by calling
 \method{radicalInverse}{} once in every 1000 calls.
 \end{tabb}
the radical inverse xi+1
\begin{hide}
 \par
 \end{hide}


reverseDigits

public static void reverseDigits(int k,
                                 int[] bdigits,
                                 int[] idigits)
. \begin{tabb}
 Given the $k$\ $b$-ary digits of $i$\ in \texttt{bdigits}, returns...
 ... in \texttt{idigits}.
 This simply reverses the order of the digits.
 \end{tabb}
knumber of digits in arrays bdigitsdigits in original order idigitsdigits in reverse order


integerRadicalInverse

public static int integerRadicalInverse(int b,
                                        int i)
. \begin{tabb}
 Computes the integer radical inverse of $i$\ in base $b$,
 equal to $b^k \psi_b(i)$\ if $i$\ has $k$\ $b$-ary digits.
 \end{tabb}
bbase used for the operation ithe value for which the integer radical inverse will be computed the integer radical inverse of i in base b


nextRadicalInverseDigits

public static int nextRadicalInverseDigits(int b,
                                           int k,
                                           int[] idigits)
. \begin{tabb}
 Given the $k$\ digits of the integer radical inverse of $i$\ in \t...
 ....
 The array must be large enough to hold this new number of digits.
 \end{tabb}
bbase kinitial number of digits in arrays idigitsdigits of integer radical inverse new number of digits in arrays


getFaureLemieuxPermutation

public static void getFaureLemieuxPermutation(int coordinate,
                                              int[] pi)
. \begin{tabb}
 Computes the permutations as proposed in\cite{vFAU09a} $\sigma_b$\ of the set
 $\{0, \ldots, b - 1\}$\ and puts it in array \texttt{pi}.
 \end{tabb}
coordinatethe coordinate pian array of size at least b, to be filled with the permutation


getFaurePermutation

public static void getFaurePermutation(int b,
                                       int[] pi)
. \begin{tabb}
 Computes the Faure permutation\cite{rFAU92a} $\sigma_b$\ of the se...
 ...tion and reference?}
 See the description in the introduction above.
 \end{tabb}
bthe base pian array of size at least b, to be filled with the permutation


permutedRadicalInverse

public static double permutedRadicalInverse(int b,
                                            int[] pi,
                                            long i)
. \begin{tabb}
 Computes the radical inverse of $i$\ in base $b$, where the digits...
 ...aymath}
 x = \htsum_{r=0}^{k-1} \pi[a_r] b^{-r-1}.
 \end{displaymath} \end{tabb}
bbase b used for the operation pian array of length at least b containing the permutation used during the computation ithe value for which the radical inverse will be computed the radical inverse of i in base b


SSJ
V. labo.

To submit a bug or ask questions, send an e-mail to Pierre L'Ecuyer.