Class HaltonSequenceGenerator

  • All Implemented Interfaces:
    RandomVectorGenerator

    public class HaltonSequenceGenerator
    extends java.lang.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:
    Halton sequence (Wikipedia), On the Halton sequence and its scramblings
    • 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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int getNextIndex()
      Returns the index i of the next point in the Halton sequence that will be returned by calling nextVector().
      double[] nextVector()
      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
    • Constructor Detail

      • 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 Detail

      • 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