Package org.apache.commons.rng.sampling.distribution

Class ZigguratSampler

java.lang.Object
org.apache.commons.rng.sampling.distribution.ZigguratSampler
All Implemented Interfaces:
ContinuousSampler, SharedStateContinuousSampler, SharedStateSampler<SharedStateContinuousSampler>
Direct Known Subclasses:
ZigguratSampler.Exponential, ZigguratSampler.NormalizedGaussian
public abstract class ZigguratSampler extends Object implements SharedStateContinuousSampler
Modified ziggurat method for sampling from Gaussian and exponential distributions.

Uses the algorithm from:

McFarland, C.D. (2016)
"A modified ziggurat algorithm for generating exponentially and normally distributed pseudorandom numbers".
Journal of Statistical Computation and Simulation 86, 1281-1294.

Note: The algorithm is a modification of the Marsaglia and Tsang "Ziggurat" method. The modification improves performance by:

  1. Creating layers of the ziggurat entirely inside the probability density function (area B); this allows the majority of samples to be obtained without checking if the value is in the region of the ziggurat layer that requires a rejection test.
  2. For samples not within the main ziggurat (area A) alias sampling is used to choose a layer and rejection of points above the PDF is accelerated using precomputation of triangle regions entirely below or above the curve. 
           \
 ----------+\
           | \
    B      |A \
 -------------+\
              | \

Sampling uses UniformRandomProvider.nextLong().

Since:
1.4
See Also:

  • Field Details

    • MASK_INT8

      private static final int MASK_INT8
      Mask to extract the lowest 8-bits from an integer.
      See Also:

    • MAX_INT64

      private static final long MAX_INT64
      Mask to create an unsigned long from a signed long. This is the maximum value of a 64-bit long.
      See Also:

    • TWO_POW_63

      private static final double TWO_POW_63
      2^63.
      See Also:

    • rng

      private final UniformRandomProvider rng
      Underlying source of randomness.

  • Constructor Details

    • ZigguratSampler

      ZigguratSampler(UniformRandomProvider rng)
      Parameters:
      rng - Generator of uniformly distributed random numbers.

  • Method Details

    • toString

      String toString(String type)
      Generate a string to represent the sampler.
      Parameters:
      type - Sampler type (e.g. "exponential").
      Returns:
      the string

    • nextLong

      long nextLong()
      Generates a long.
      Returns:
      the long

    • randomInt63

      long randomInt63()
      Generates a positive long in [0, 2^63).

      In the c reference implementation RANDOM_INT63() obtains the current random value and then advances the RNG. This implementation obtains a new value from the RNG. Thus the java implementation must ensure a previous call to the RNG is cached if RANDOM_INT63() is called without first advancing the RNG.

      Returns:
      the long

    • interpolate

      static double interpolate(double[] v, int j, long u)
      Compute the value of a point using linear interpolation of a data table of values using the provided uniform deviate. 
        value = v[j] + u * (v[j-1] - v[j])

      This can be used to generate the (x,y) coordinates of a point in a rectangle with the upper-left corner at j and lower-right corner at j-1: 

      
    X[j],Y[j]
        |\ |
        | \|
        |  \
        |  |\    Ziggurat overhang j (with hypotenuse not pdf(x))
        |  | \
        |  u2 \
        |      \
        |-->u1  \
        +-------- X[j-1],Y[j-1]

   x = X[j] + u1 * (X[j-1] - X[j])
   y = Y[j] + u2 * (Y[j-1] - Y[j])
      Parameters:
      v - Ziggurat data table. Values assumed to be scaled by 2^-63.
      j - Index j. Value assumed to be above zero.
      u - Uniform deviate. Value assumed to be in [0, 2^63).
      Returns:
      value