Alex Herbert created RNG-160:
--------------------------------
Summary: Performance of modified Ziggurat samplers
Key: RNG-160
URL: https://issues.apache.org/jira/browse/RNG-160
Project: Commons RNG
Issue Type: Improvement
Components: sampling
Affects Versions: 1.4
Reporter: Alex Herbert
Fix For: 1.4
The modified ziggurat algorithm implemented in RNG-151 has a variation for
sampling from the overhang regions at the ziggurat edges, region A below:
{noformat}
\
----------+\
| \
B |A \
-------------+\
| \
{noformat}
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.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
