17

Whenever I run the following program the returned values are always 6 or 13.

#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;

//void randomLegs();
//void randomPush();
//void randomPull();
//void randomMisc();


int main(int argc, const char * argv[])
{
    srand(time(NULL));
    //randomLegs();
    cout << rand() % 14;
    return 0;
}

I have run the program close to a hundred times during today and yesterday.

Can anyone tell me what I'm doing wrong?

Thank you.

EDIT: By the way, if I change the range of rand() to say 13 or 15 it works just fine.

Taylan Aydinli
  • 4,333
  • 15
  • 39
  • 33
Kenneth
  • 343
  • 1
  • 2
  • 10

3 Answers3

42

Per wikipedia, the multiplier being used in Apple's MCG random number generator is 16807. This is divisible by 7, so the first random number produced after srand() will have only one bit of entropy mod 14 (that is, it can only take on two values).

It's a crappy RNG they've got there. An easy solution, though, is just to call rand() a few times right after srand, and discard the results.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • 7
    +1, beautiful explanation! I wasn't aware how flaky these things could be. Usually the explanation I see for "why you should never modulo over a short range" is just that it's not uniform around the edges. – Leeor Nov 28 '13 at 13:35
  • 17
    Incidentally, an even simpler workaround is to wait about 18 million years, and then try the program again. At that point, the value returned by `time()` will be great enough to push the entropy "around the corner" into the low-order bits. Give that a try, and let our descendants know how it works out. :-D – Sneftel Nov 28 '13 at 13:37
  • That's why [`rand() % 7` always return 0](http://stackoverflow.com/q/7866754/995714) – phuclv Sep 23 '15 at 15:48
10

I can reproduce the problem on Mac OS X 10.9 with Xcode 5 - it looks like it might actually be a bug, or at least a limitation with rand()/srand() on OS X 10.9.

I recommend you use arc4random() instead, which works a lot better than rand(), and which doesn't require that you randomize the seed:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, const char * argv[])
{
    cout << (arc4random() % 14) << endl;
    return 0;
}

Test:

$ g++ -Wall -O3 srand.cpp && ./a.out
5
$ ./a.out
8
$ ./a.out
0
$ ./a.out
8
$ ./a.out
11
$ ./a.out
8
$ ./a.out
3
$ ./a.out
13
$ ./a.out
9
$
Paul R
  • 208,748
  • 37
  • 389
  • 560
  • 2
    Thank you Paul. This solution is simple and it solves my problem. – Kenneth Nov 28 '13 at 13:27
  • 5
    Why use another library, if the Standard library has alternatives too? See ``, in particular `std::mt19937` which is a known-good RNG. It also comes with `std::uniform_int_distribution` – MSalters Nov 28 '13 at 17:21
  • 2
    @MSalters: `arc4random()` is pretty standard on Mac OS X, iOS, and various BSD platforms, and doesn't require an additional library. – Paul R Nov 28 '13 at 18:42
  • 1
    @MSalters `arc4random()` is in the BSD C library, it doesn't require any additional setup. Also, not everyone can use or assume the availability of C++11 for various reasons. –  Feb 02 '14 at 13:01
  • 5
    @PaulR Exactly. Also, an even better solution would be to use `arc4random_uniform(MAX)` instead of `arc4random() % MAX`. –  Feb 02 '14 at 13:02
3

rand() % 14 is often a poor random number generator. You'll probably get better results with this

(int)(14*(rand()/(RAND_MAX + 1.0)))
john
  • 85,011
  • 4
  • 57
  • 81
  • 2
    This is the only non-deleted answer left! Hang in there @john! – Moo-Juice Nov 28 '13 at 12:09
  • Just to clarify. I'm not the one deleting answers. – Kenneth Nov 28 '13 at 13:22
  • @user3045273, don't worry - they were deleted by their owners. – Moo-Juice Nov 28 '13 at 13:22
  • If the answer given by Sneftel is correct, then this would be a valid solution. I want my downvote back! – john Nov 28 '13 at 13:38
  • This actually isn't better. It just produces a different unequally weighted distribution. Pretend that `rand()` generates values from 0 to 9, inclusive. If you distribute those values into 9 buckets, at least one bucket will get 2 or more values, regardless of how you decide to distribute the values. The solution is to **discard** some values, so that the number of generated values is a multiple of the number of buckets. For this case, find the largest multiple of 14 that's less than or equal to RAND_MAX, and whenever `rand()` generates a value that's larger than that multiple, try again. – Pete Becker Nov 28 '13 at 14:09
  • 2
    John's solution produces a value with about 3.8 bits of entropy, versus the original code which produced 1 (and extremely close to the theoretical maximum). So yes, it actually is better. – Sneftel Nov 28 '13 at 14:54