Class HaltonSequenceGenerator

java.lang.Object
org.apache.commons.math3.random.HaltonSequenceGenerator
All Implemented Interfaces:
RandomVectorGenerator

public class HaltonSequenceGenerator extends Object implements RandomVectorGenerator
Implementation of a Halton sequence.

A Halton sequence is a low-discrepancy sequence generating points in the interval [0, 1] according to

   H(n) = d_0 / b + d_1 / b^2 .... d_j / b^j+1

   with

   n = d_j * b^j-1 + ... d_1 * b + d_0 * b^0
 
For higher dimensions, subsequent prime numbers are used as base, e.g. { 2, 3, 5 } for a Halton sequence in R^3.

Halton sequences are known to suffer from linear correlation for larger prime numbers, thus the individual digits are usually scrambled. This implementation already comes with support for up to 40 dimensions with optimal weight numbers from H. Chi: Scrambled quasirandom sequences and their applications.

The generator supports two modes:

Since:
3.3
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final int[]
    The base numbers for each component.
    private int
    The current index in the sequence.
    private final int
    Space dimension.
    private static final int[]
    The first 40 primes.
    private final int[]
    The scrambling weights for each component.
    private static final int[]
    The optimal weights used for scrambling of the first 40 dimension.
  • Constructor Summary

    Constructors
    Constructor
    Description
    HaltonSequenceGenerator(int dimension)
    Construct a new Halton sequence generator for the given space dimension.
    HaltonSequenceGenerator(int dimension, int[] bases, int[] weights)
    Construct a new Halton sequence generator with the given base numbers and weights for each dimension.
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    Returns the index i of the next point in the Halton sequence that will be returned by calling nextVector().
    double[]
    Generate a random vector.
    protected int
    scramble(int i, int j, int b, int digit)
    Performs scrambling of digit d_j according to the formula:
    double[]
    skipTo(int index)
    Skip to the i-th point in the Halton sequence.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • PRIMES

      private static final int[] PRIMES
      The first 40 primes.
    • WEIGHTS

      private static final int[] WEIGHTS
      The optimal weights used for scrambling of the first 40 dimension.
    • dimension

      private final int dimension
      Space dimension.
    • count

      private int count
      The current index in the sequence.
    • base

      private final int[] base
      The base numbers for each component.
    • weight

      private final int[] weight
      The scrambling weights for each component.
  • Constructor Details

    • HaltonSequenceGenerator

      public HaltonSequenceGenerator(int dimension) throws OutOfRangeException
      Construct a new Halton sequence generator for the given space dimension.
      Parameters:
      dimension - the space dimension
      Throws:
      OutOfRangeException - if the space dimension is outside the allowed range of [1, 40]
    • HaltonSequenceGenerator

      public HaltonSequenceGenerator(int dimension, int[] bases, int[] weights) throws NullArgumentException, OutOfRangeException, DimensionMismatchException
      Construct a new Halton sequence generator with the given base numbers and weights for each dimension. The length of the bases array defines the space dimension and is required to be > 0.
      Parameters:
      dimension - the space dimension
      bases - the base number for each dimension, entries should be (pairwise) prime, may not be null
      weights - the weights used during scrambling, may be null in which case no scrambling will be performed
      Throws:
      NullArgumentException - if base is null
      OutOfRangeException - if the space dimension is outside the range [1, len], where len refers to the length of the bases array
      DimensionMismatchException - if weights is non-null and the length of the input arrays differ
  • Method Details

    • nextVector

      public double[] nextVector()
      Generate a random vector.
      Specified by:
      nextVector in interface RandomVectorGenerator
      Returns:
      a random vector as an array of double.
    • scramble

      protected int scramble(int i, int j, int b, int digit)
      Performs scrambling of digit d_j according to the formula:
         ( weight_i * d_j ) mod base
       
      Implementations can override this method to do a different scrambling.
      Parameters:
      i - the dimension index
      j - the digit index
      b - the base for this dimension
      digit - the j-th digit
      Returns:
      the scrambled digit
    • skipTo

      public double[] skipTo(int index) throws NotPositiveException
      Skip to the i-th point in the Halton sequence.

      This operation can be performed in O(1).

      Parameters:
      index - the index in the sequence to skip to
      Returns:
      the i-th point in the Halton sequence
      Throws:
      NotPositiveException - if index < 0
    • getNextIndex

      public int getNextIndex()
      Returns the index i of the next point in the Halton sequence that will be returned by calling nextVector().
      Returns:
      the index of the next point