Efficiently Generating a Number in a Range • Hacker News Board

Re: Efficiently Generating a Number in a Range

#11

Post by simias » Wed, Jul 25, 2018, 4:34 PM UTC

nerdponx wrote: post #3

This 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.

Note that this article is not really about RNGs themselves, but mostly how to use one to generate an unbiased number within a given range from a "raw" RNG output which typically generates a stream of 32 or 64bit integers.

Regarding the performance of RNGs themselves it's mostly bound by how "random" your want your NG to be. If you don't really care about quality and need very good performance, for instance to procedurally generate assets in a videogame, there are extremely fast and somewhat decent PRNGs out there, such as XorShift. Of course you won't use that to generate PGP keys...

Re: Efficiently Generating a Number in a Range

#12

Post by WorkLifeBalance » Wed, Jul 25, 2018, 4:34 PM UTC

dagenix wrote: post #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…

The modulo approach is biased for all ranges which don't divide the full range but only a small amount of bias at small ranges rather than a large amount of bias at large ranges.

Re: Efficiently Generating a Number in a Range

#13

Post by by » Wed, Jul 25, 2018, 4:37 PM UTC

nerdponx wrote: post #3

This 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.

I only skimmed the article, so maybe they said this, but for choosing from a small range, for example 0..51, you can get several of these from a 32 bit random number with this algorithm

https://stackoverflow.com/questions/6046918/how-to-generate-...

You should be able to run a 64 bit PRNG once and pick at least 8 random cards from a deck.

Re: Efficiently Generating a Number in a Range

#14

Post by modeless » Wed, Jul 25, 2018, 4:41 PM UTC

nightcracker wrote: post #9

smaddox wrote: post #6

Earlier 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

Melissa O'Neill's response back: http://www.pcg-random.org/posts/on-vignas-pcg-critique.html

Re: Efficiently Generating a Number in a Range

#15

Post by vinkelhake » Wed, Jul 25, 2018, 4:43 PM UTC

dagenix wrote: post #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…

The comment there is not about [-3, 17] being an obscure output range from a distribution. It is that the distribution must be able to handle a random generator that outputs numbers in that range.

I think there's a small error there in that the output type of UniformRandomBitGenerator must be actually be unsigned. The larger point still stands though. It is possible to write a conforming UniformRandomBitGenerator that has an output range of [3, 17] and it falls on the distribution to handle this.

Re: Efficiently Generating a Number in a Range

#16

Post by rootlocus » Wed, Jul 25, 2018, 4:45 PM UTC

    return min + (max - min) / 2

Oh, you want a random number?

Re: Efficiently Generating a Number in a Range

#17

Post by ballenf » Wed, Jul 25, 2018, 4:47 PM UTC

by wrote: post #13

nerdponx wrote: post #3

This 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.

I only skimmed the article, so maybe they said this, but for choosing from a small range, for example 0..51, you can get several of these from a 32 bit random number with this algorithm https://stackoverflow.com/questions/6046918/how-to-generate-... You should be able to run a 64 bit PRNG once and pick at least 8 random cards from a deck.

The article's conclusion was that the PRNG generation method used is usually not the bottleneck, but how you take that to get a result is. Don't know if that applies to the algorithm linked, but the author's point was that bottlenecks are more likely to arise in the code that surrounds the PRNG algorithm than in the call to PRNG itself.

Re: Efficiently Generating a Number in a Range

#18

Post by dagenix » Wed, Jul 25, 2018, 4:58 PM UTC

WorkLifeBalance wrote: post #12

dagenix wrote: post #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…

The modulo approach is biased for all ranges which don't divide the full range but only a small amount of bias at small ranges rather than a large amount of bias at large ranges.

I don't disagree - I just very much hate the phrase "over engineered" as I think it never adds anything to a discussion.

Re: Efficiently Generating a Number in a Range

#19

Post by dagenix » Wed, Jul 25, 2018, 5:00 PM UTC

vinkelhake wrote: post #15

dagenix wrote: post #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…

The comment there is not about [-3, 17] being an obscure output range from a distribution. It is that the distribution must be able to handle a random generator that outputs numbers in that range. I think there's a small error there in that the output type of UniformRandomBitGenerator must be actually be unsigned. The larger point still stands though. It is possible to write a conforming UniformRandomBitGenerator tha…

Ah, good call. I did slightly misinterpret what was being said. I think my overall point still stands, though.

Re: Efficiently Generating a Number in a Range

#20

Post by smaddox » Wed, Jul 25, 2018, 5:13 PM UTC

modeless wrote: post #14

nightcracker wrote: post #9

Earlier quoted context omitted.

xoshiro's response: http://pcg.di.unimi.it/pcg.php

Melissa O'Neill's response back: http://www.pcg-random.org/posts/on-vignas-pcg-critique.html

Thanks. This completely allays my concerns about the PCG's I would actually use.

Edit: And I like that MCG with 64-bit multiplicand that she shows. I might switch to that for Monte Carlo applications.