# 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 2009-08-11, 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..n-1.

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 & (len-1)) { /* 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, max-min < 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 e-mail, please replace ".invalid" with ".net" in address.

.

**Follow-Ups**:**Re: Efficient way to gen a random number in a particular range?***From:*Ertugrul Söylemez

**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

- 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):