Efficiently Generating a Number in a Range
pcg-random.org
Efficiently Generating a Number in a Range
1–10 of 41 posts
Re: Efficiently Generating a Number in a Range
#2Personally I'm a fan of the xoshiro[1] generator I have found it to be faster and give more equiprobable outputs.
Re: Efficiently Generating a Number in a Range
#3This is well-timed. I don't know much about different random number generators but I do know that we recently had an problem where RNG was a serious performance bottleneck.
Re: Efficiently Generating a Number in a Range
#4Personally I'm a fan of the xoshiro[1] generator I have found it to be faster and give more equiprobable outputs. [1] http://xoshiro.di.unimi.it
The article discusses the xoshiro RNG, and some better alternatives: “One other concern we might have is that some generators have weak low-order bits. For example, the Xoroshiro+ and Xoshiro+ families of PRNGs have low-order bits that fail statistical tests.“
The xoshiro page mentions this too, and says it won’t matter if you are generating random floats, but the article is generating random ints.
The RNG isn’t the point of the article though. It’s discussing the speed and correctness of what happens after the RNG but before you use the results.
Re: Efficiently Generating a Number in a Range
#5Personally I'm a fan of the xoshiro[1] generator I have found it to be faster and give more equiprobable outputs. [1] http://xoshiro.di.unimi.it
Note that this article is not about the random number generating scheme, but about post-processing to get a random number within a certain range. That said, the author specifically points out xoshiro as a random number generating scheme to watch out for:
One other concern we might have is that some generators have weak low-order bits. For example, the Xoroshiro+ and Xoshiro+ families of PRNGs have low-order bits that fail statistical tests. When we perform % 52 (because 52 is even) we pass the lowest bit straight through into the output.
Re: Efficiently Generating a Number in a Range
#6Personally I'm a fan of the xoshiro[1] generator I have found it to be faster and give more equiprobable outputs. [1] http://xoshiro.di.unimi.it
xoshiro has flaws: http://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.h...
Re: Efficiently Generating a Number in a Range
#7> Let's move from an over-engineered approach to an under-engineered one.
The article says this to deride C++s implementation as being too complicated because it supports ranges such as [-3,17] and then promptly goes on to discuss how a modulo based implementation is very biased if the upper end of the range is above 2^31. It's not really clear why the former use case is unimportant but the latter isn't.
It just goes to show that one person's niche use case is another person's main use case. I wish people would just avoid the judgemental term "over engineered" and instead focus on matching appropriate algorithms to appropriate use cases.
Re: Efficiently Generating a Number in a Range
#8[deleted]
Re: Efficiently Generating a Number in a Range
#9Personally I'm a fan of the xoshiro[1] generator I have found it to be faster and give more equiprobable outputs. [1] http://xoshiro.di.unimi.it
xoshiro has flaws: http://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.h...
xoshiro's response: http://pcg.di.unimi.it/pcg.php
Re: Efficiently Generating a Number in a Range
#10Earlier quoted context omitted.
xoshiro has flaws: http://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.h...
xoshiro's response: http://pcg.di.unimi.it/pcg.php
Interesting read, thanks! The deflection about xoshiro is not particularly convincing, though. It's much more likely that you'll want to multiply your random stream by a multiple of 57 than you'll want to xor it with a 43-bit-shifted version of itself. He also doesn't appear to counter the complaint about the generator getting stuck around 0: http://www.pcg-random.org/posts/xoshiro-repeat-flaws.html
The other parts of the post definitely concern me about using the PCG's described, though. Also, it's interesting to see how PCG can be predicted. I would not have known how to attack it.