11

I am using rand() to generate either 0 or 1 (rand() % 2). I am seeding it using the current time (srand(time(NULL))).

After much debugging, I realised that rand() never returns an even (odd) number 16 or more times in a row.

Is this a known issue? Is there a better PRNG that comes with C?

I am running on Windows 7 using Visual Studio 2010.

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
Benjy Kessler
  • 7,356
  • 6
  • 41
  • 69
  • 9
    `rand never returns an even (odd) number 16 or more times in a row` - well... How many times are you testing it? Less than `2^16` times? – Mysticial Jul 10 '12 at 16:53
  • The probability of getting 16 odds in a row is `(1/2)^16`. That's pretty low... – Tudor Jul 10 '12 at 16:54
  • Around a billion times, enough for 16 even (odd) numbers to appear 128 times roughly (if my calculations are correct). – Benjy Kessler Jul 10 '12 at 16:55
  • 5
    In some (older) implementations of `rand`, the lower-order bits were less random than higher-order ones. Try `(rand()>RAND_MAX/2?1:0)` – Shahbaz Jul 10 '12 at 16:56
  • In my own experience, I believe `rand()` is deterministic when built in VS under a debug configuration, even if you seed it – Dan F Jul 10 '12 at 17:00
  • 2
    Modulo bias might be a problem. See http://stackoverflow.com/a/10984975/562769 – Martin Thoma Jul 10 '12 at 17:03
  • @DanF: all pseudo-RNGs are deterministic, given a seed. This is actually a feature in many applications. It makes debugging possible (with the same seed, the program runs the same way). It's only a problem when you really need true randomness, for cryptographic purposes. – sfstewman Jul 10 '12 at 17:26
  • @sfstewman, yes, I am aware that PRNGs are deterministic, since its just an algorithm to spit out a number, but like I said, even if you seed it with a pseudo-random value (such as the current time) `rand` would always spit out the same values each time you ran under debug – Dan F Jul 10 '12 at 17:27
  • @moose Modulo bias isn't a problem for power-of-two moduli with any sane implementation, since `RAND_MAX` typically is a power of two minus 1. – Daniel Fischer Jul 10 '12 at 19:10
  • Acually I think when you want random bits from rand(), don't just use one bit and throw away the others, but use them all, like this: `v=rand(); b1= v&1; b2 = v&2; b3 = v&4;...`. – U. Windl Aug 25 '19 at 22:51

4 Answers4

15

Instead of using rand()%2, try rand()>(RAND_MAX/2). You can only assume rand() to be uniform on the interval [0, RAND_MAX].

Edit: This was suggested by Shahbaz in the comments, which I only noticed after I posted this answer.

Edit: ArjunShankar called me out on my previous wording: "rand() is only specified to be uniform on the interval [0, RAND_MAX]"

From the C99 standard:

The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.

Technically, uniformity (or equidistributed) is not specified, but is the de-facto standard used for implementations of commonly used PRNG's (e.g. Mersenne Twister). This is to allow a programmer to easily create a custom PRNG with a non-uniform distribution. Without this property, a programmer is forced to implement a custom PRNG from scratch.

jxh
  • 69,070
  • 8
  • 110
  • 193
  • "*rand() is only specified to be uniform on the interval [0, RAND_MAX]*" - The [Microsoft documentation for `rand`](http://msdn.microsoft.com/en-us/library/398ax69y%28v=vs.71%29.aspx) doesn't say anything about uniformity. Is there some other source? – ArjunShankar Jul 10 '12 at 17:08
  • Okay, I checked C99 as well. No guarantee on uniformity over the range. Of course, this does not mean your solution is incorrect. It is very possible that this in fact does achieve the kind of sequences the OP is testing for. – ArjunShankar Jul 10 '12 at 17:12
  • Neat answer. +1 because I would like to have the OP try it. Also because `rand` comes pretty cheap. – ArjunShankar Jul 10 '12 at 17:36
2

I'd suggest using a better RNG. You're running on Windows so you can use rand_s: It's a Microsoft extension that uses the Windows cryptographic RNG.

Aaron Klotz
  • 11,287
  • 1
  • 28
  • 22
  • 1
    Cryptographic RNG is **slow** and really overkill for most applications. It's cryptographic (and really, really slow compared to pRNGs) because the bits are actually random, from external events, and not pseudo-random. This also makes it much harder to debug. – sfstewman Jul 10 '12 at 17:24
  • 2
    @sfstewman I would suggest that the tradeoffs are for the author of the question to evaluate and decide upon. – Aaron Klotz Jul 10 '12 at 17:27
  • 1
    Your answer, while it would solve the OP's problem, also creates new ones. Cryptographic RNGs aren't really suitable for generating billions of random bits at a time. This would be compounded by the modulo-2 of the OP's code throwing away all but one of the bits from each call to `rand_s`. That's 31 or 63 bits of pure entropy gone. You should at least warn the OP and suggest that they could use each and every bit from `rand_s`, not just the LSB. – sfstewman Jul 10 '12 at 17:35
1

rand() is well-known to suck. random() is a bit better (sometimes), but drand48() and its family are much better.

In you need better than that, look into the mersene twister or other PRNG libraries. Or check out /dev/random if that can provide enough data for your needs.

evil otto
  • 10,348
  • 25
  • 38
  • googling suggests not. There are other random number generating functions available on windows, like CryptGenRandom, or you could use an external library like MT - http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html – evil otto Jul 10 '12 at 17:10
  • 1
    `rand()` has historically had problems. See George Marsaglia's [famous article](http://www.pnas.org/content/61/1/25.full.pdf+html) for the mathematics. Your C library may or may not still have this problem. For anything that requires serious randomness, the Mersenne Twister (link provided by @evilotto) or another modern pRNG is best. – sfstewman Jul 10 '12 at 17:20
0

Well, You can use Algorithms for Mersenne Twister or WELL. The code for WELL is on here(I don't have enough reputations) https://i.stack.imgur.com/q6VPL.pngenter image description here

Tushar Gupta - curioustushar
  • 58,085
  • 24
  • 103
  • 107