| Since modulus is such a slow operation, it's tempting to create a random integer in the range [0,r) by generating a uniform random float, multiplying by the range, and then taking the floor. The R language, which is generally reputed to have good statistical practices, takes this approach: https://github.com/wch/r-source/blob/b156e3a711967f58131e23c1b1dc1ea90e2f0c43/src/main/unique.c#L1758 But I haven't been able to find much analysis about this approach. Your Random Vector paper (http://www.agner.org/random/theory/randomvector.pdf) says "Floating point calculation methods give the
same error because we are mapping an interval of length 2^32 to another interval of incommensurable length d", but I'm not sure this is what you are referring to. For r < 2^32, is this a safe means of generating a random integer in range [0,r)? 1) Generate 52 random bits
2) Create random double [1.0,2.0)
3) Subtract one to have [0.0,1.0)
4) Multiply by r to obtain [0.0, r.0)
5) Take floor to obtain [0, r-1] My instinct is that this is equitable other than the +/-1 difference in the number of uniform floats that map to each integer. Are there other effects? Are there way to overcome this while avoiding an expensive modulus? |
Multiplying uniform floats to obtain random ints - Nathan Kurz - 2015-11-15
Multiplying uniform floats to obtain random ints new - Agner - 2015-11-17