Uploaded image for project: 'Commons RNG'
  1. Commons RNG
  2. RNG-160

Performance of modified Ziggurat samplers

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Reopened
    • Minor
    • Resolution: Unresolved
    • 1.4
    • 1.4
    • sampling
    • None

    Description

      The modified ziggurat algorithm implemented in RNG-151 has a variation for sampling from the overhang regions at the ziggurat edges, region A below:

                  \
        ----------+\
                  | \
           B      |A \
        -------------+\
                     | \
      

      Note: Region B is the ziggurat layer which is entirely within the distribution PDF.

      These overhangs can be convex, concave or an inflection (change from convex to concave). Samples from the region A must be below the distribution density curve (PDF). When sampling from region A, the sampler will create a random point (x,y) uniformly within the rectangle. This is tested to determine if it is below the curve. Convex and concave curves can use a fast method that knows the largest possible triangle that fits above or below the curve. If a sampled point (x,y) is within these triangles then the actual curve position (pdf( x)) for the point x does not need to be computed. This can save time if the pdf is computationally expensive. In the case of exponential (exp(-x)) or Gaussian (exp(-0.5 * x * x)) this involves a call to Math.exp.

      The current sampler implements the fast look-up method. The alternative is to always compute pdf( x) and determine if y is below the curve. This is known as 'simple overhangs'.

      Investigate the use of simple overhangs on the performance of the sampler.

      Note: The Marsaglia version of the ziggurat sampler uses the 'simple overhangs' method.

      Attachments

        1. exp_normal.jpg
          133 kB
          Alex Herbert
        2. exp_overhang.jpg
          179 kB
          Alex Herbert
        3. Exp.jpg
          101 kB
          Alex Herbert
        4. gauss_normal.jpg
          108 kB
          Alex Herbert
        5. gauss_overhang.jpg
          182 kB
          Alex Herbert
        6. Gaussian.jpg
          84 kB
          Alex Herbert

        Issue Links

          Activity

            People

              aherbert Alex Herbert
              aherbert Alex Herbert
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated: