3 ms·
Why not use regular rejection sampling when `limit` is known at compile-time. Does fastrange[1] have fewer rejections due to any excess random bits[2]? [1] htt
by aqrit 2y ago
Why not use regular rejection sampling when `limit` is known at compile-time.
Does fastrange[1] have fewer rejections due to any excess random bits[2]?
[1] https://github.com/lemire/fastrange https://github.com/lemire/fastrange
[2] https://github.com/swiftlang/swift/pull/39143 https://github.com/swiftlang/swift/pull/39143
- fanf2 2y agoWhat do you mean by “regular” rejection sampling? Fastrange is slightly biased because, as Steve Canon observes in that Swift PR, it is just Knuth’s multiplicative reduction. The point of this post is that it’s possible to simplify Lemire’s nearly-divisionless debiasing when the limit is known at compile time. I previously experimented with really-divisionless debiasing but I was underwhelmed with the results https://dotat.at/@/2022-04-20-really-divisionless.html https://dotat.at/@/2022-04-20-really-divisionless.html
- aqrit 2y ago> “regular” rejection sampling I was thinking naive: mask off unwanted bits then reject any value above the limit. It would seem like https://c-faq.com/lib/randrange.html https://c-faq.com/lib/randrange.html would also move the multiply --or divide by constant-- out of the loop.
- fanf2 2y agoLemire’s algorithm rejects the fewest possible samples from the random number generator, so it’s generally the fastest. The multiplication costs very little compared to the RNG.