Puzzling behavior from Java.Random.nextInt()

user_8887287 0
Viewed 107

I'm implementing a SkipList. At one point in the algorithm, we are to toss a coin, and do something over and over as long as it keeps coming up heads, and stop as soon as we see tails. I was letting odd numbers represent "heads" by using:

while (R.nextInt() % 2 == 1)

But this yielded a heads only about 25% of the time (out of 50,000-ish calls). Changing it to

while (R.nextBoolean())

produces heads half of the time, as expected. R is instantiated as a Random, seeded with System.currentTimeMillis(). It appears that the bit stream generated by Random is not so uniformly distributed after all. Has anyone else seen such behavior?

I also tried it with:

while (Math.random() >= 0.5)

and got the 50/50 (give-or-take) behavior I was expecting.

It also seems to work just fine with:

while (R.nextInt(2) == 1)

It just doesn't seem to generate 32-bit integers with the LSB 0 anywhere NEAR half of the time. Seems that, at the bit level, we should be able to expect randomness, too. Maybe it's the linear congruence they're using; maybe I'm missing something, but this seems to be a problem. I realize there are "better" PRNGs available, and I already have a couple of perfectly viable work-arounds; I just wanted to report what I observed.

java
2 Answers

nextInt()
Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence.

Integer types are signed in Java, and possible results of doing modulo 2 operation are: -1 (negative odd), 0 (even), 1 (positive odd).

nextInt() % 2 would be equal to 1 only for positive odd integers, that's why you get only 25%. You need a small change in the condition:

 while (R.nextInt() % 2 != 0)
user_47592000

In Java (n*2+1) % 2 is -1 if n is negative. (This is quite annoying as it doesn't make much mathematical sense but it is what it is. It is however consistent with how the / operator works, so (a/b)*b+(a%b)=a for all a and b, unless integer overflow happens.)

Since Random.nextInt() returns a signed random number, the modulo will be 0 50% of the time, -1 25% of the time and 1 25% of the time.

Of course you can switch to r.nextInt() % 2 != 0 or r.nextInt() == 0 but the most readable solution is indeed just using r.nextBoolean().

user_5744790
Related