Objective C: Modulo bias

Question

Using

   value = arc4random() % x

How can I avoid or eliminate modulo bias?

Thanks all.

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

Answer 1

Use the method below. It avoids "modulo bias" and it`s fast on iphone . Save you some cpu cycles.

IF you want 4-7:

(random() / (float)RAND_MAX )*3+4

OR if you want 0-8

(random() / (float)RAND_MAX )+8

Answer 2

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

Answer 3

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.

Answer 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;

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.

Answer 5

arc4random returns a 32-bit unsigned integer (0 to 2³²-1).

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

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

val = arc4random() % y;
while(val >= x)
    val = arc4random() % y;

Answer 6

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.