RadicalInverse (Java Libraries for Stochastic Simulation)

java.lang.Object
- umontreal.iro.lecuyer.hups.RadicalInverse

```
public class RadicalInverse
extends java.lang.Object
```
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 = a₀ + a₁b + ... + a_k-1b^k-1,
the radical inverse in base b is

ψ_b(i) = a₀b^-1 + a₁b^-2 + ^... + a_k-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

b^kψ_b(i) = a_k-1 + ^... + a₁b^k-2 + a₀b^k-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) = ∑_r=0^k-1a_rb^-r-1
is replaced by

∑_r=0^k-1π(a_r)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 b^k values that are enumerated remain the same (they are the values of ψ_b(i) for i = 0,..., b^k - 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. 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

Constructors
Constructor and Description

RadicalInverse(int b, double x0)
Initializes the base of this object to b and its first value of x to x0.

Constructors
Constructor and Description
`RadicalInverse(int b, double x0)` Initializes the base of this object to b and its first value of x to `x0`.

Method Summary

Methods
Modifier and Type	Method and Description
`static void`	`getFaurePermutation(int b, int[] pi)` Computes the Faure permutation σ_b of the set {0,…, b - 1} and puts it in array `pi`.
`static int[]`	`getPrimes(int n)` Provides an elementary method for obtaining the first n prime numbers larger than 1.
`static int`	`integerRadicalInverse(int b, int i)` Computes the integer radical inverse of i in base b, equal to b^kψ_b(i) if i has k b-ary digits.
`double`	`nextRadicalInverse()` A fast method that incrementally computes the radical inverse x_i+1 in base b from x_i = ψ_b(i), using addition with rigthward carry as described in Wang and Hickernell.
`static double`	`nextRadicalInverse(double invb, double x)` A fast method that incrementally computes the radical inverse x_i+1 in base b from x_i = `x` = ψ_b(i), using addition with rigthward carry.
`static int`	`nextRadicalInverseDigits(int b, int k, int[] idigits)` Given the k digits of the integer radical inverse of i in `bdigits`, in base b, this method replaces them by the digits of the integer radical inverse of i + 1 and returns their number.
`static double`	`permutedRadicalInverse(int b, int[] pi, int i)` Computes the radical inverse of i in base b, where the digits are permuted using the permutation π.
`static double`	`radicalInverse(int b, long i)` Computes the radical inverse of i in base b.
`static void`	`reverseDigits(int k, int[] bdigits, int[] idigits)` Given the k b-ary digits of i in `bdigits`, returns the k digits of the integer radical inverse of i in `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)
```
    Initializes the base of this object to b and its first value of x to x0.
    
    Parameters:
    b - Base
    x0 - Initial value of x
- Method Detail
  - getPrimes
```
public static int[] getPrimes(int n)
```
    Provides an elementary method for obtaining the first n prime numbers larger than 1. Creates and returns an array that contains these numbers. This is useful for determining the prime bases for the different coordinates of the Halton sequence and Hammersley nets.
    
    Parameters:
    n - number of prime numbers to return
    
    Returns:
    an array with the first n prime numbers
  - radicalInverse
```
public static double radicalInverse(int b,
                    long i)
```
    Computes the radical inverse of i in base b. If i = ∑_r=0^k-1a_rb^r, the method computes and returns
    
    x = ∑_r=0^k-1a_rb^-r-1.
    
    Parameters:
    b - base used for the operation
    i - the value for which the radical inverse will be computed
    
    Returns:
    the radical inverse of i in base b
  - nextRadicalInverse
```
public static double nextRadicalInverse(double invb,
                        double x)
```
    A fast method that incrementally computes the radical inverse x_i+1 in base b from x_i = x = ψ_b(i), using addition with rigthward carry. The parameter invb is equal to 1/b. Using long incremental streams (i.e., calling this method several times in a row) cause increasing inaccuracy in x. Thus the user should recompute the radical inverse directly by calling radicalInverse every once in a while (i.e. in every few thousand calls).
    
    Parameters:
    invb - 1/b where b is the base
    x - the inverse x_i
    
    Returns:
    the radical inverse x_i+1
  - nextRadicalInverse
```
public double nextRadicalInverse()
```
    A fast method that incrementally computes the radical inverse x_i+1 in base b from x_i = ψ_b(i), using addition with rigthward carry as described in Wang and Hickernell. Since using long incremental streams (i.e., calling this method several times in a row) cause increasing inaccuracy in x, the method recomputes the radical inverse directly from i by calling radicalInverse once in every 1000 calls.
    
    Returns:
    the radical inverse x_i+1
  - reverseDigits
```
public static void reverseDigits(int k,
                 int[] bdigits,
                 int[] idigits)
```
    Given the k b-ary digits of i in bdigits, returns the k digits of the integer radical inverse of i in idigits. This simply reverses the order of the digits.
    
    Parameters:
    k - number of digits in arrays
    bdigits - digits in original order
    idigits - digits in reverse order
  - integerRadicalInverse
```
public static int integerRadicalInverse(int b,
                        int i)
```
    Computes the integer radical inverse of i in base b, equal to b^kψ_b(i) if i has k b-ary digits.
    
    Parameters:
    b - base used for the operation
    i - the value for which the integer radical inverse will be computed
    
    Returns:
    the integer radical inverse of i in base b
  - nextRadicalInverseDigits
```
public static int nextRadicalInverseDigits(int b,
                           int k,
                           int[] idigits)
```
    Given the k digits of the integer radical inverse of i in bdigits, in base b, this method replaces them by the digits of the integer radical inverse of i + 1 and returns their number. The array must be large enough to hold this new number of digits.
    
    Parameters:
    b - base
    k - initial number of digits in arrays
    idigits - digits of integer radical inverse
    
    Returns:
    new number of digits in arrays
  - getFaurePermutation
```
public static void getFaurePermutation(int b,
                       int[] pi)
```
    Computes the Faure permutation σ_b of the set {0,…, b - 1} and puts it in array pi. See the description in the introduction above.
    
    Parameters:
    b - the base
    pi - an array of size at least b, to be filled with the permutation
  - permutedRadicalInverse
```
public static double permutedRadicalInverse(int b,
                            int[] pi,
                            int i)
```
    Computes the radical inverse of i in base b, where the digits are permuted using the permutation π. If i = ∑_r=0^k-1a_rb^r, the method will compute and return
    
    x = ∑_r=0^k-1π[a_r]b^-r-1.
    
    Parameters:
    b - base b used for the operation
    pi - an array of length at least b containing the permutation used during the computation
    i - the value for which the radical inverse will be computed
    
    Returns:
    the radical inverse of i in base b

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

σ[c]	=	c
σ[i]	=	τ[i], if 0 <= τ[i] < c
σ[i]	=	τ[i] + 1, if c <= τ[i] < 2c

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

Class RadicalInverse

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

RadicalInverse

Method Detail

getPrimes

radicalInverse

nextRadicalInverse

nextRadicalInverse

reverseDigits

integerRadicalInverse

nextRadicalInverseDigits

getFaurePermutation

permutedRadicalInverse