Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualBacterius

Posted 27 December 2012 - 06:12 PM

Using rand() is perfectly fine *if* you only need a uniform distribution. There are a lot of times where this isn't the case (for example, generating white noise, where you want a gaussian distribution). In those cases you'll need some kind of random number generator. I'd recommend the boost::random library, which lets you specify any distribution you want. 

 

Not true. The default LCG included in most rand() implementations does not produce a uniform distribution. Look up "random numbers fall mainly in the planes" from G. Marsaglia. Mersenne Twister does a much better job, though, so if you can use that easily without changing much code, I'd definitely recommend it. It's just that usually, this is good enough for most applications which don't require a perfectly uniform distribution, even a rough approximation usually suffices.

 

Also you can derive any statistical distribution from a uniform distribution - or any other distribution, for that matter - via inverse transform sampling (essentially, invert the cumulative distribution function). For an example with a normal distribution, check out the Box-Muller transform, or the Ziggurat algorithm.

 

 

 

Also, if you want a "truly random" number and you're on linux, call srand() once with a number read from /dev/rand or /dev/urand. These files provide about as close to a truly random number as you can get. Your sequence will still be predictable *if* you know the seed, but with a truly random seed, your numbers are also less predictable (i.e. "more" random).

Again, no. Even if your seed is highly unpredictable, the default LCG will not produce a proper uniform sequence. In fact, it doesn't even matter what your seed is, since a good LCG is a proper permutation - you'll just be starting at a different place in the cycle. A similar argument holds for Mersenne Twister, though it's not a permutation iirc. At least in the context of a game, if you're talking cryptography it's obviously different.

 

 

 

If you're wondering why you can't just read from /dev/rand or /dev/urand all the time when you need a random number, technically you *can,* you just *shouldn't,* since it depletes the random-ness of the numbers in the file, and can affect other programs running on the machine that need random numbers, like ssh. 

This really depends how much entropy you need. There are methods to stretch a single 128-bit value into an effectively infinite bitstream which is computationally indistinguishable from a truly uniformly random bitstream, but this is really going off-topic and overkill in this context. I don't wanna be "that guy" SOTL was talking about mellow.png


#1Bacterius

Posted 27 December 2012 - 06:10 PM

Using rand() is perfectly fine *if* you only need a uniform distribution. There are a lot of times where this isn't the case (for example, generating white noise, where you want a gaussian distribution). In those cases you'll need some kind of random number generator. I'd recommend the boost::random library, which lets you specify any distribution you want. 

Not true. The default LCG included in most rand() implementations does not produce a uniform distribution. Look up "random numbers fall mainly in the planes" from G. Marsaglia. Mersenne Twister does a much better job, though, so if you can use that easily without changing much code, I'd definitely recommend it. It's just that usually, this is good enough for most applications which don't require a perfectly uniform distribution, even a rough approximation usually suffices.

 

Also you can derive any statistical distribution from a uniform distribution - or any other distribution, for that matter - via inverse transform sampling (essentially, invert the cumulative distribution function). For an example with a normal distribution, check out the Box-Muller transform, or the Ziggurat algorithm.

 

 

 

Also, if you want a "truly random" number and you're on linux, call srand() once with a number read from /dev/rand or /dev/urand. These files provide about as close to a truly random number as you can get. Your sequence will still be predictable *if* you know the seed, but with a truly random seed, your numbers are also less predictable (i.e. "more" random).

Again, no. Even if your seed is highly unpredictable, the default LCG will not produce a proper uniform sequence. In fact, it doesn't even matter what your seed is, since a good LCG is a proper permutation - you'll just be starting at a different place in the cycle. A similar argument holds for Mersenne Twister, though it's not a permutation iirc.

 

 

 

If you're wondering why you can't just read from /dev/rand or /dev/urand all the time when you need a random number, technically you *can,* you just *shouldn't,* since it depletes the random-ness of the numbers in the file, and can affect other programs running on the machine that need random numbers, like ssh. 

This really depends how much entropy you need. There are methods to stretch a single 128-bit value into an effectively infinite bitstream which is computationally indistinguishable from a truly uniformly random bitstream, but this is really going off-topic and overkill in this context. I don't wanna be "that guy" SOTL was talking about mellow.png


PARTNERS