[
https://issues.apache.org/jira/browse/RNG-69?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex D Herbert updated RNG-69:
------------------------------
Description:
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).
was:
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:
||probabilityOfSuccess||randomSourceName||Method||Score||Error||Relative Speed||
|0.1|JDK|runGeometricInverseTranformSampler|786086.7|22427.75|1.00|
|0.1|JDK|runGeometricSampler|511206.08|38722.29|0.65|
|0.1|MWC_256|runGeometricInverseTranformSampler|656838.86|3501.26|1.00|
|0.1|MWC_256|runGeometricSampler|358833.81|121652.51|0.55|
|0.1|SPLIT_MIX_64|runGeometricInverseTranformSampler|602642.45|4192.85|1.00|
|0.1|SPLIT_MIX_64|runGeometricSampler|289775.51|7279.83|0.48|
|0.3|JDK|runGeometricInverseTranformSampler|776525.54|3286.05|1.00|
|0.3|JDK|runGeometricSampler|524565.79|39613.82|0.68|
|0.3|MWC_256|runGeometricInverseTranformSampler|638300.02|4217.91|1.00|
|0.3|MWC_256|runGeometricSampler|344942.66|2493.33|0.54|
|0.3|SPLIT_MIX_64|runGeometricInverseTranformSampler|600476.53|10686.48|1.00|
|0.3|SPLIT_MIX_64|runGeometricSampler|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).
> 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 D Herbert
> Priority: Minor
> Labels: Performance
>
> 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
(v7.6.3#76005)
