[
https://issues.apache.org/jira/browse/RNG-196?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex Herbert resolved RNG-196.
------------------------------
Fix Version/s: 1.8
Resolution: Fixed
Added a default alpha of 53 in commit:
8abfa51735d6d4371e6c65f63a568cfa63f1b6d5
> FastLoadedDiceRoller defaults can result in performance degradation for
> categories unlikely to be sampled
> ---------------------------------------------------------------------------------------------------------
>
> Key: RNG-196
> URL: https://issues.apache.org/jira/browse/RNG-196
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.3
> Reporter: Alex Herbert
> Priority: Trivial
> Fix For: 1.8
>
>
> The FastLoadedDiceRollerSampler (FLDR) uses an alpha parameter to exclude
> weights that are smaller than the largest weight. The alpha parameter
> controls the threshold for ignoring weights relative to the largest weight
> using a log2 scale.
> The default behaviour when the alpha parameter is not provided is to use
> alpha=0 and include all weights. This can result in large memory allocation
> relative to the number of categories when constructing the internal discrete
> distribution generating (DDG) tree, and a change to using BigInteger
> arithmetic for an increased construction time. The probability of observing
> the smallest weight in the resulting DDG tree is impractically small and thus
> performance is impacted for accuracy over efficiency.
> Example:
> {code:java}
> double[] weights = {1, 1, 2, Double.MIN_VALUE};
> var s1 = FastLoadedDiceRollerDiscreteSampler.of(rng, weights); // alpha=0
> var s2 = FastLoadedDiceRollerDiscreteSampler.of(rng, weights, 60); {code}
> During construction the weights are scaled to remove common trailing zero
> bits, summed exactly and the full bit length of the sum (k) used to allocate
> the DDG tree. The DDG tree is sized using bit length k multiplied by the
> number of categories + 1: k * (n+1).
> The default sampler s1 will require look-up tables of length 1076*(4+1).
> Sampler s2 will require look-up tables of length 2*(3+1). The probability of
> observing the smallest weight is w / sum(w) or approximately Double.MIN_VALUE
> / 4 = 1.2e-324.
> An improvement is to introduce a default non-zero value for alpha. A default
> of 53 would ignore any weight 2^53 smaller than the largest weight. This
> would have a sampling probability of 2^-53 (1e-16) relative to the largest
> weight. In practice it would require 2^53 samples from the FLDR to observe
> this category once. Note that use of this threshold will enable the faster
> non-BigInteger construction pathway when the number of categories is less
> than 2^10, and may use this pathway for larger numbers of categories
> depending on the number of significant bits in the weights.
> Issue identified using a security scan.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
