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
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int[] base
      The base numbers for each component.
      private int count
      The current index in the sequence.
      private int dimension
      Space dimension.
      private static int[] PRIMES
      The first 40 primes.
      private int[] weight
      The scrambling weights for each component.
      private static int[] WEIGHTS
      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

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

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