[RNG-160] Performance of modified Ziggurat samplers

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.4
• Fix Version/s: 1.4
• Component/s: sampling
• Assignee: Alex Herbert
• Reporter: Alex Herbert
• Created: 12/Aug/21 09:27
• Updated: 10/Oct/22 11:54
• Resolved: 05/Apr/22 15:15

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.

Issue Links

• is related to: RNG-151 Modified Ziggurat algorithm for normal and exponential sampling