5 ms·

> In 2018, Daniel Lemire found an algorithm that avoids the divisions nearly all the time (see also his 2019 blog post). In math/rand, adopting Lemire’s algorit

> In 2018, Daniel Lemire found an algorithm that avoids the divisions nearly all the time (see also his 2019 blog post). In math/rand, adopting Lemire’s algorithm would make Intn(1000) 20-30% faster... I recently found a super simple algorithm that appears to produce a number in the interval [0,N] with a branchless expression with a single multiplication in an extended number size. (Sorry I don't have a reference.) Say you want to generate a number, G, in interval [0,N] where N<=UInt32Max. The algorithm is: G = uint32( uint64(N)*uint64(rand.UInt32())>>32 ) It seems like this should select a number in the range with no bias. Is there something I missed?

fanf2 2y ago
Your algorithm is the first step of Lemire’s algorithm, without the followup check to debias the result. https://dotat.at/@/2020-10-29-nearly-divisionless-random-numbers.html https://dotat.at/@/2020-10-29-nearly-divisionless-random-num...
baruz 2y ago
Your results will be biased. It is tiny with small values of N, and absent when N is a power of two, but the skew becomes more obvious when your N is 2^31 + 2^30 + 1, for example.
funny_falcon 2y ago
Lemire uses your found but corrects its biases.
Someone 2y ago
> It seems like this should select a number in the range with no bias. Is there something I missed? Yes. There are many values of N that aren’t divisors of UInt32Max. As the article says: “However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4 equally likely values into 3.)”
- infogulch 2y ago
  Are you sure? Maybe this isn't a good test but it seems pretty evenly distributed to me: https://go.dev/play/p/IeJQEAclBCU https://go.dev/play/p/IeJQEAclBCU Edit: maybe this shows the bias better: https://go.dev/play/p/3eKJibIlF1a https://go.dev/play/p/3eKJibIlF1a
  - cmeacham98 2y ago
    UInt32Max (i.e. 4294967295) is divisible by 3, so your code actually is perfectly random (or more accurately, as random as go's rand package). It would be biased with N=4, for example. Regardless, with small values of N, the bias is very slight so you would need many many iterations to see the imperfection in a statically significant way.
    - infogulch 2y ago
      That makes sense. A quick search didn't reveal any good resources for how to test the quality of a random number generator in a number range. Is what I came up with the best strategy, and you just need to run it for much longer (and compare to a known-good implementation) to see the difference?
      - codeflo 2y ago
        Why would you need to “see” it? Unlike the distribution of the RNG itself, this is trivial to solve analytically.
- josephg 2y ago
  > (As a simpler example, try converting 4 equally likely values into 3.) No, but you can convert a RNG that emits 4 equally likely values into an RNG that emits 3 equally likely values. Just - anytime the RNG returns 4, try again. Here's a fun puzzle / annoying interview question: You have a biased coin. You can flip it as often as you want, but heads and tails are not equally likely. Without figuring out the bias of the coin, how do you produce purely random bits?
ironhaven 2y ago
You have written a deterministic function. If you test this function with all 4 billion uint32 on one odd interval, go and count the number of times you get each result. Now look at your results, are all of the numbers equally likely or is there bias towards some outputs? Ps: it looks like your function is exclusive like [0,N) not [0,N] Also your function is described in this blog post https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html
- infogulch 2y ago
  Correct on all counts. Thanks!
assbuttbuttass 2y ago
This maps UInt32Max input values to N output values, so there is guaranteed to be bias by pigeonhole, unless N divides Uint32Max
flyingmutant 2y ago
This algorithm produces biased result with probability 1/2^(32-bitwidth(N)). Using 64 or 128 random bits can make the bias practically undetectable. Comprehensive overview of the approach can be found here: https://github.com/apple/swift/pull/39143 https://github.com/apple/swift/pull/39143

fanf2 2y ago

Your algorithm is the first step of Lemire’s algorithm, without the followup check to debias the result. https://dotat.at/@/2020-10-29-nearly-divisionless-random-numbers.html https://dotat.at/@/2020-10-29-nearly-divisionless-random-num...

baruz 2y ago

Your results will be biased. It is tiny with small values of N, and absent when N is a power of two, but the skew becomes more obvious when your N is 2^31 + 2^30 + 1, for example.

funny_falcon 2y ago

Lemire uses your found but corrects its biases.

Someone 2y ago

> It seems like this should select a number in the range with no bias. Is there something I missed? Yes. There are many values of N that aren’t divisors of UInt32Max. As the article says: “However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4 equally likely values into 3.)”

infogulch 2y ago
Are you sure? Maybe this isn't a good test but it seems pretty evenly distributed to me: https://go.dev/play/p/IeJQEAclBCU https://go.dev/play/p/IeJQEAclBCU Edit: maybe this shows the bias better: https://go.dev/play/p/3eKJibIlF1a https://go.dev/play/p/3eKJibIlF1a
- cmeacham98 2y ago
  UInt32Max (i.e. 4294967295) is divisible by 3, so your code actually is perfectly random (or more accurately, as random as go's rand package). It would be biased with N=4, for example. Regardless, with small values of N, the bias is very slight so you would need many many iterations to see the imperfection in a statically significant way.
  - infogulch 2y ago
    That makes sense. A quick search didn't reveal any good resources for how to test the quality of a random number generator in a number range. Is what I came up with the best strategy, and you just need to run it for much longer (and compare to a known-good implementation) to see the difference?
    - codeflo 2y ago
      Why would you need to “see” it? Unlike the distribution of the RNG itself, this is trivial to solve analytically.
josephg 2y ago
> (As a simpler example, try converting 4 equally likely values into 3.) No, but you can convert a RNG that emits 4 equally likely values into an RNG that emits 3 equally likely values. Just - anytime the RNG returns 4, try again. Here's a fun puzzle / annoying interview question: You have a biased coin. You can flip it as often as you want, but heads and tails are not equally likely. Without figuring out the bias of the coin, how do you produce purely random bits?

ironhaven 2y ago

You have written a deterministic function. If you test this function with all 4 billion uint32 on one odd interval, go and count the number of times you get each result. Now look at your results, are all of the numbers equally likely or is there bias towards some outputs? Ps: it looks like your function is exclusive like [0,N) not [0,N] Also your function is described in this blog post https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html

infogulch 2y ago
Correct on all counts. Thanks!

assbuttbuttass 2y ago

This maps UInt32Max input values to N output values, so there is guaranteed to be bias by pigeonhole, unless N divides Uint32Max

flyingmutant 2y ago

This algorithm produces biased result with probability 1/2^(32-bitwidth(N)). Using 64 or 128 random bits can make the bias practically undetectable. Comprehensive overview of the approach can be found here: https://github.com/apple/swift/pull/39143 https://github.com/apple/swift/pull/39143