[jira] [Updated] (RNG-160) Performance of modified Ziggurat samplers

["Alex Herbert (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/RNG-160?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Alex Herbert updated RNG-160:
-----------------------------
    Attachment: exp_overhang.jpg

> 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
>            Assignee: Alex Herbert
>            Priority: Minor
>             Fix For: 1.4
>
>         Attachments: Exp.jpg, Gaussian.jpg, exp_overhang.jpg, gauss_overhang.jpg
>
>
> 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)