2

I have read here -- without understanding much -- that it's bad to use mod range. So this typical recommendation for Objective-C

int r = arc4random() % 45;

might be a bad idea to get a number from 0 to 45 (something about the distribution and this formula having a preference for low bits). What should one use in Objective-C?




<sarcasm> I am so glad to be able to finally learn this stuff after using only high-level languages (Java et. al) all this time. Tomorrow I will try to make fire with two twigs. </sarcasm>

Dan Rosenstark
  • 68,471
  • 58
  • 283
  • 421
  • The referred not says it is bad to use rand() and mod - it says nothing about other random generators and mod. – mmmmmm Jul 13 '10 at 00:24
  • A similar question has already been asked: http://stackoverflow.com/questions/160890/generating-random-numbers-in-objective-c – Jacob Relkin Jul 13 '10 at 00:26
  • @Mark, I might be wrong but I read this DO NOT USE ` y = rand() % M; ` to mean not to use modulus. – Dan Rosenstark Jul 13 '10 at 00:29
  • See my answer but it means rand() and mod is bad not mod on its own. The note says Note rand() does not have to be a linear congruential random number generator. It's perfectly permissible for it to be something better which does not have this problem. and arc4random is something better – mmmmmm Jul 13 '10 at 00:46

1 Answers1

1

Java is just as high level as Objecive C here - in this case Java' Random.getInt() is the same as arc4random in that they both return a 32-bit pseudo-random number.

The issue raised in the URL (and I have seen elsewhere) is that rand()

could be repeating itself every 32768 values.

Whilst OSX's arc4random could have (2**1700) states.

But as in all uses of pseudo-random generators you need to be aware of their weaknesses before using them e.g. a preference for low bits in some generators and also the comment in the OpenBSD arc4random man page where it says

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.

mmmmmm
  • 32,227
  • 27
  • 88
  • 117
  • 1
    I'm not too worried about the value not being random enough, but I am worried about a non-uniform distribution. I do not have arc4random_uniform in Objective-C (that I know of). What should I use instead? – Dan Rosenstark Jul 13 '10 at 00:50
  • arc4random() % upper_bound is probably OK or get the code from OpenBSD (or use a generator from Boost) – mmmmmm Jul 13 '10 at 02:00
  • Oh, I get it now. "For linear congruential random number generators, which rand() often is, the lower bytes are much less random than the higher bytes." So if arc4random doesn't have this problem, then the modulus is no problem. That's cool. – Dan Rosenstark Jul 13 '10 at 04:46
  • 1
    It's still a problem. Suppose that your random function produces a range from 0 to 25 and your modulus is 7. Up to 20 everything is fine. However, `21 % 7 = 0`, `22 % 7 = 1`, up to `25 % 7 = 4`. This means 0 through 4 will have 1/25 more chance to be picked than 5 through 7. The easiest way around it is to "re-roll" any number from the random function that is equal to or greater than `modulus * trunc(max_rand / modulus)`. You could also just ignore the slight bias when max_rand is very large relative to the modulus. @Yar –  Aug 13 '11 at 06:52
  • @Graff I love selective rerolling, the problem is that your program has a infinitely small chance of getting caught up in an infinite loop of rerolls ;) Thanks very much for the comment. – Dan Rosenstark Aug 13 '11 at 12:43
  • 1
    @Yar Yeah that is a very small possibility, of course there are better but more complex ways of handling the problem. Anyways, the bias is normally very small. –  Aug 13 '11 at 17:04