13

Using:

value = arc4random() % x

How can I avoid or eliminate modulo bias?

At least according to Wikipedia, modulo bias is an issue when programming games of chance.

Cœur
  • 37,241
  • 25
  • 195
  • 267
Alan
  • 1,265
  • 4
  • 22
  • 44
  • 1
    Consider re-marking Zoidberg's answer as the correct one, as it's the canonical correct answer according to the authors of arc4random(). – MikeyWard Dec 30 '12 at 21:59
  • 3
    [What is modulo bias](http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator)? – bobobobo Apr 15 '13 at 02:03

5 Answers5

49

Use arc4random_uniform(x). This does it for you.

According to the man page:

arc4random_uniform() will return a uniformly distributed random number less than upper_bound. arc4random_uniform() is recommended over constructions like arc4random() % upper_bound as it avoids "modulo bias" when the upper bound is not a power of two.

14

arc4random returns a 32-bit unsigned integer (0 to 232-1).

There will probably be no noticable modulo bias for small enough x. However, if you want to be really sure, do this:

y = 2p where 2p-1 < x ≤ 2p

val = arc4random() % y;
while(val >= x)
    val = arc4random() % y;
Can Berk Güder
  • 109,922
  • 25
  • 130
  • 137
  • If I recall, there's something like this in Python's random number generator. – Lambda Fairy Nov 12 '11 at 00:09
  • 3
    I happen to trip over same task, C implementation can be found in OpenBSD `arc4random_uniform()` at [src/sys/dev/rnd.c](http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c?rev=1.140;content-type=text%2Fplain) – SashaN Jun 13 '12 at 08:32
4
u_int32_t maxValue = ~((u_int32_t) 0);      // equal to 0xffff...
maxValue -= maxValue % x;                   // make maxValue a multiple of x
while((value = arc4random()) >= maxValue) { // loop until we get 0 ≤ value < maxValue
}
value %= x;

although unless you are using any x under a million (or more) I wouldn't worry about it

cobbal
  • 69,903
  • 20
  • 143
  • 156
2

If the maximum value of arc4random mod x is greater than x, ignore any values larger than the largest arc4random-max mod x, calling arc4random again instead.

Jason Cohen
  • 81,399
  • 26
  • 107
  • 114
1
u_int32_t maxValue = ~((u_int32_t) 0);      // equal to 0xffff...
maxValue -= maxValue % x;                   // make maxValue a multiple of x
while((value = arc4random()) >= maxValue) { // loop until we get 0 ≤ value < maxValue
}
value %= x;

Somewhat pedantic objection to cobbal's answer. It "works", that is it removes the modulo bias, but it rejects more values than are necessary. The most extreme case is x = 2^31. All values of arc4random() should be accepted here but the code as written will reject half of them.

Instead, add 1 to the initialization of maxValue (that puts it at 2^32 so you'll have to use a 64 bit int), and then it's right. You can also avoid using a 64 bit int. Test beforehand if 2^32 % x == 0, if so all arc4random() values are acceptable and you can skip the loop, otherwise you can keep maxValue at 32 bits by subtracting 2^32 % x on initialization.

JSLigon
  • 49
  • 4