[
https://issues.apache.org/jira/browse/RNG-179?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17541921#comment-17541921
]
Vladimir Sitnikov commented on RNG-179:
---------------------------------------
WOW. Thanks for the analysis!
{quote} Here the sampler is relatively slow to construct. This is due to the
construction using exact representation of the input probabilities. All
probability values are converted to rational numbers (p / q) where q is a power
of 2.{quote}
I thought integer sampling (the case when all weights are integer) does not
require going for floats, doubles, etc.
This looks like a pure int/long/long long math:
https://github.com/probcomp/fast-loaded-dice-roller/blob/master/src/c/fldr.c
> The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete
> Probability Distributions
> ------------------------------------------------------------------------------------------------
>
> Key: RNG-179
> URL: https://issues.apache.org/jira/browse/RNG-179
> Project: Commons RNG
> Issue Type: New Feature
> Components: sampling
> Reporter: Vladimir Sitnikov
> Priority: Major
> Time Spent: 10m
> Remaining Estimate: 0h
>
> It might make sense to implement Fast Loaded Dice Roller sampler.
> See https://arxiv.org/pdf/2003.03830v2.pdf,
> https://github.com/probcomp/fast-loaded-dice-roller
> The authors claim that Fast Loaded Dice Roller is faster than the Alias
> Method.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)