Re: Efficient way to gen a random number in a particular range?
 From: Ilmari Karonen <usenet2@xxxxxxxxxxxxxx>
 Date: 20 Aug 2009 00:28:28 GMT
On 20090811, Ertugrul Söylemez <es@xxxxxxxx> wrote:
MTGAP schrieb:
I assume Scott is doing this because modding by a power of 2 can be
efficiently implemented with the bitwise AND operation. But it's
faster (and simpler) to do it like this:
x = prng() % 40 + 10;
Bad method, because it's biased towards 0..15. Mod 41 is also bad,
because it's biased towards 0..36. Modulo operation is only good in
this case, if your module is a power of 2. In all other cases you
should use 64 bit integer operations and do it this way:
r < prng
40*r / 2^32
This yields a number 0..39. Generally replacing 40 by n yields a number
0..n1.
That's still biased in favor of the numbers 2, 4, 7, 9, 12, 14, 17,
19, 22, 24, 27, 29, 32, 34, 37 and 39, assuming I did my math right.
Mind you, in this case the bias is only about one in a hundred
thousand, but then that's true of both methods.
Anyway, the fastest method that is completely unbiased, assuming the
underlying generator is so, is (in C code):
do { tmp = prng(); } while (tmp >= 4294967280);
x = 10 + tmp % 40;
The number 4294967280 is simply the largest multiple of 40 less than
or equal to 2**32. If you'd prefer to take the range as a parameter,
you can calculate it at runtime like this:
unsigned int random (unsigned int min, unsigned int max) {
unsigned int len, top, tmp;
len = max  min + 1; /* length of range */
if (len & (len1)) { /* not a power of 2 */
top = PRNG_MAX  PRNG_MAX % len;
do { tmp = prng(); } while (tmp >= top);
return min + tmp % len;
} else if (len) { /* power of 2, maxmin < PRNG_MAX */
return min + prng() % len;
} else return prng(); /* min == 0, max == PRNG_MAX */
}
This assumes that prng() returns uniformly distributed numbers between
0 and PRNG_MAX inclusive, where PRNG_MAX is one less than a power of
two, and that the low bits of its output are at least as random as any
others (which won't be the case for simple LCPRNGs like most C library
rand() implementations). If you're using a LCPRNG (which you really
shouldn't be doing, but some still do), use Ertugrul's method _after_
the rejection sampling, i.e. replace the line:
return min + tmp % len;
with:
return min + ((uint64_t) tmp * len) / top;
and the line:
return min + prng() % len;
with:
return min + ((uint64_t) prng() * len) / ((uint64_t) PRNG_MAX + 1);
(BTW, I spent quite some time tweaking that code, and I *believe* that
it's correct. However, I believed the same thing several times while
I was writing this before finding more bugs and odd corner cases, so I
make no guarantees. Use at your own risk, and preferably test first.)

Ilmari Karonen
To reply by email, please replace ".invalid" with ".net" in address.
.
 FollowUps:
 Re: Efficient way to gen a random number in a particular range?
 From: Ertugrul Söylemez
 Re: Efficient way to gen a random number in a particular range?
 References:
 Efficient way to gen a random number in a particular range?
 From: Dave Turner
 Re: Efficient way to gen a random number in a particular range?
 From: Scott Contini
 Re: Efficient way to gen a random number in a particular range?
 From: MTGAP
 Re: Efficient way to gen a random number in a particular range?
 From: Ertugrul Söylemez
 Efficient way to gen a random number in a particular range?
 Prev by Date: Re: modified factoring problem.
 Next by Date: Re: Friedman Squares
 Previous by thread: Re: Efficient way to gen a random number in a particular range?
 Next by thread: Re: Efficient way to gen a random number in a particular range?
 Index(es):
Relevant Pages
