Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

OpenBSD bug in the random() function

banu.com

Post reply on HN
Print view View original

1–10 of 29 posts

Re: OpenBSD bug in the random() function

#3

Post by Yrlec »

While not exactly a bug, but if you run this code in Java:

  for(int i = 0; i
It prints the following sequence (at least on JDK 7 and Win 7):

  0.730967787376657
  0.7308781907032909
  0.7311469360199058
  0.731057369148862
  0.7306094602878371
  0.730519863614471
  0.7307886238322471
  0.7306990420600421
  0.7302511331990172
  0.7301615514268123
I know that you're not supposed to recreate the Random-instance like that but it's still a bit odd that the initial values in each sequence are so similar to each other.

Re: OpenBSD bug in the random() function

#5

Post by Yrlec »

Yrlec wrote: post #3

While not exactly a bug, but if you run this code in Java: for(int i = 0; i It prints the following sequence (at least on JDK 7 and Win 7): 0.730967787376657 0.7308781907032909 0.7311469360199058 0.731057369148862 0.7306094602878371 0.730519863614471 0.7307886238322471 0.7306990420600421 0.7302511331990172 0.7301615514268123 I know that you're not supposed to recreate the Random-instance like that but it's still a bi…

Any reason for the down-vote? I honestly want to learn.

Re: OpenBSD bug in the random() function

#6

Post by tedunangst »

Yrlec wrote: post #3

While not exactly a bug, but if you run this code in Java: for(int i = 0; i It prints the following sequence (at least on JDK 7 and Win 7): 0.730967787376657 0.7308781907032909 0.7311469360199058 0.731057369148862 0.7306094602878371 0.730519863614471 0.7307886238322471 0.7306990420600421 0.7302511331990172 0.7301615514268123 I know that you're not supposed to recreate the Random-instance like that but it's still a bi…

I know nothing about java's random number generator, but your seeds are also very similar to each other.

Re: OpenBSD bug in the random() function

#7

Post by gcp »

Yrlec wrote: post #5
Yrlec wrote: post #3

While not exactly a bug, but if you run this code in Java: for(int i = 0; i It prints the following sequence (at least on JDK 7 and Win 7): 0.730967787376657 0.7308781907032909 0.7311469360199058 0.731057369148862 0.7306094602878371 0.730519863614471 0.7307886238322471 0.7306990420600421 0.7302511331990172 0.7301615514268123 I know that you're not supposed to recreate the Random-instance like that but it's still a bi…

Any reason for the down-vote? I honestly want to learn.

The Java Random class uses a 48-bit LCG with a 35-bit multiplier. Because of this, small seed values won't be able to "wrap around" the full range of the LCG and will cause starting sequences that are all but random relative to each other.

Put differently, you're seeing that 35/48 = 0.73.

I'd consider this a bug in Java, but it's a common one. Qt has the same problem. Could have been avoided by cycling the seed through the LCG once, instead of using XOR.

Re: OpenBSD bug in the random() function

#9

Post by Yrlec »

gcp wrote: post #7
Yrlec wrote: post #5

Earlier quoted context omitted.

Any reason for the down-vote? I honestly want to learn.

The Java Random class uses a 48-bit LCG with a 35-bit multiplier. Because of this, small seed values won't be able to "wrap around" the full range of the LCG and will cause starting sequences that are all but random relative to each other. Put differently, you're seeing that 35/48 = 0.73. I'd consider this a bug in Java, but it's a common one. Qt has the same problem. Could have been avoided by cycling the seed throu…

Interesting, thanks! Any particular reason they limit the multiplier to 35 bits and the output to 48 bits?

Edit: just noticed that Java limits the output to 32 bits, not 48 (http://en.wikipedia.org/wiki/Linear_congruential_generator). How does it create 64 bit values, like long and double?

Re: OpenBSD bug in the random() function

#10

Post by saalweachter »

calloc wrote: post #4

Or why maybe using random() is a terrible idea. Use arc4random() instead on FreeBSD/OpenBSD/Mac OS X for a MUCH better random number generation, and best of all it is auto-seeded. Obligatory XKCD: http://xkcd.com/221/

Obligatory Dilbert: http://dilbert.com/strips/comic/2001-10-25/
Post reply on HN