[jira] [Resolved] (RNG-69) GeometricSampler

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

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

Alex Herbert resolved RNG-69.
-----------------------------
    Resolution: Implemented

Changes that effect the public API are marked as Implemented (not Done).

> GeometricSampler
> ----------------
>
>                 Key: RNG-69
>                 URL: https://issues.apache.org/jira/browse/RNG-69
>             Project: Commons RNG
>          Issue Type: New Feature
>          Components: sampling
>    Affects Versions: 1.3
>            Reporter: Alex Herbert
>            Assignee: Alex Herbert
>            Priority: Minor
>              Labels: Performance
>             Fix For: 1.3
>
>          Time Spent: 1h
>  Remaining Estimate: 0h
>
> Sampling from a Geometric distribution is currently implemented using the {{InverseTransformDiscreteSampler}}.
> This samples using the inverse cumulative probability function of the Geometric distribution and effectively computes:
> {code:java}
> // p = probability of success
> // precompute
> double log1mProbabilityOfSuccess = FastMath.log1p(-p);
> // To sample
> double u = rng.nextDouble();
> Math.max(0, (int) Math.ceil(Math.log1p(-u)/log1mProbabilityOfSuccess-1));
> {code}
> Thus there is a call to {{Math.log1p}} for every sample.
> It is possible to sample from a Geometric using a related underlying exponential sampler:
> [Geometric distribution - related distributions|https://en.wikipedia.org/wiki/Geometric_distribution#Related_distributions]
> Here the probability of success (p) is converted into a mean for an exponential distribution:
> {code:java}
> // Use a related exponential distribution:
> // λ = −ln(1 − probabilityOfSuccess)
> // exponential mean = 1 / λ
> final double exponentialMean = 1.0 / (-Math.log1p(-probabilityOfSuccess));
> exponentialSampler = new AhrensDieterExponentialSampler(rng, exponentialMean);
> // To sample return the floor of the exponential sample
> return (int) Math.floor(exponentialSampler.sample());
> {code}
> The {{AhrensDieterExponentialSampler}} has been optimised to avoid calling Math.log. It only uses {{nextDouble}}. Using this method a geometric sampler can be created that outperforms the inverse sampling method.
> I have created a test version of this method. It passes the test for the Geometric distribution when added to the {{DiscreteSamplersList}} in the test suite. Here is a performance result using JMH:
> ||Success probability||RNG||Method||Score||Error||Relative Speed||
> |0.1|JDK|GeometricInverseTranformSampler|786086.7|22427.75|1.00|
> |0.1|JDK|GeometricSampler|511206.08|38722.29|0.65|
> |0.1|MWC_256|GeometricInverseTranformSampler|656838.86|3501.26|1.00|
> |0.1|MWC_256|GeometricSampler|358833.81|121652.51|0.55|
> |0.1|SPLIT_MIX_64|GeometricInverseTranformSampler|602642.45|4192.85|1.00|
> |0.1|SPLIT_MIX_64|GeometricSampler|289775.51|7279.83|0.48|
> |0.3|JDK|GeometricInverseTranformSampler|776525.54|3286.05|1.00|
> |0.3|JDK|GeometricSampler|524565.79|39613.82|0.68|
> |0.3|MWC_256|GeometricInverseTranformSampler|638300.02|4217.91|1.00|
> |0.3|MWC_256|GeometricSampler|344942.66|2493.33|0.54|
> |0.3|SPLIT_MIX_64|GeometricInverseTranformSampler|600476.53|10686.48|1.00|
> |0.3|SPLIT_MIX_64|GeometricSampler|300886.79|6718.99|0.50|
> Performance is roughly half (1/2) the run-time for a fast RNG (SPLIT_MIX_64) and 2/3 the runtime for a slow RNG (JDK).
>  



--
This message was sent by Atlassian Jira
(v8.3.4#803005)