4 ms·

Which random number generator to use can be a heated discussion, with strong opinions. math.random() and rand() can have issues using poor random number genera

Which random number generator to use can be a heated discussion, with strong opinions. math.random() and rand() can have issues using poor random number generators like LCGs instead of good random number generators. The default “good” random number generator is the “Mersenne Twister” (most of the time, the 32-bit MT19937 version). It generates numbers which look quite random while not being cryptographically strong (the problem with crypto-strong generators is that they tend to be slower, and can still cause legal issues in some jurisdictions). A lot of languages use this for the default random number generator. Some people really like using xorshift generators; with the right parameters, xorshift can generate high quality numbers while being much simpler than MT19937. One version of this which some use is JKISS32; it’s small and makes good numbers. Random number generators can be tested using a series of tests called “dieharder”; another test for RNGs is “bigcrush” which takes hours, sometimes days, to fully run. These tests make sure the random number generators are statistically random, using a large number of tests of the generator. My favorite pseudo random number generator is a cryptographically strong one: RadioGatún[32]. It’s simple, fast, doesn’t require special seeding of its state (unlike MT19937), and allows the seed to be an arbitrary string instead of just being a number. It passes all dieharder tests, but I haven’t had a chance to test it with bigcrush yet. I have a GitHub repo with implementations of it I have done in various languages (C, Python2, Python3, Javascript, C++, etc.)

edflsafoiewq 7y ago
I would not recommend MT. It fails many tests, that state is big, the code is complex, and it's not very fast. For non-crypto PRNGs, I'd reach for PCG or one of Vigna's generators.
- strenholme 7y ago
  I tend to agree, but I need to point out that MT19937 doesn’t fail “many” tests. It fails, at most, two of the bigcrush tests: https://en.wikipedia.org/wiki/Talk:Mersenne_Twister https://en.wikipedia.org/wiki/Talk:Mersenne_Twister and look for the “TestU01” discussion on that page. The biggest problem with MT19937, besides its complexity and large state size, is that it needs to have its state properly seeded. Like I said, it’s a heated debate which random number generator is the best one.
  - FabHK 7y ago
    It is surprisingly heated debate, and it's hard to extract good advice from experts (I've asked Art Owen, Monte Carlo expert at Stanford, for up-to-date advice (he recommended MT19937 some 15 years ago), and he was very hesitant to utter any strong recommendations...) Having said that, I think most projects should move on from MT19937 by now, defaulting to a cryptographically secure PRNG, and allowing to switch to a faster one (such as PCG or xoroshiro) when desired.
    - strenholme 7y ago
      MT19937 is probably not the best PRNG out there, but the nice thing about it is that, for a long time, there was a pretty strong consensus among programmers that it was the PRNG to use. It’s a better choice than a simple LCG, which is what programmers tend to use if they’re not using MT. There are a lot of crypto-strong RNGs out there (AES on OFB mode? Counter Mode? SHA-3 in SHAKE128 or SHAKE256? Salsa20 or ChaCha? Or, do what I do and use RadioGatún[32]), so not much standardization on that front. With non crypto, we have in this thread already mentioned PCG ( http://www.pcg-random.org/ http://www.pcg-random.org/ ), JKISS32, xoroshiro, and Vigna’s generators. There are others. Again, not much standardization.
      - FabHK 7y ago
        I thought the xoroshiros are basically Vigna's? Developed further from precursors. But you're right, there's no successor anointed yet to MT19937, but it's about time. Wish some real expert in the field would publish an authoritative account (but opinionated enough to make real choices) that programming language devs could point to, and across the board implement: * safe (ie, a cryptographically secure PRNG) <- default * fast (if your application needs speed more than security against adversaries, such as Monte Carlo integration) * others (if you really know what you're doing) EDIT to add: it feels a bit like the old chestnut about IBM: nobody ever gets fired for choosing the Mersenne Twister...
  - edflsafoiewq 7y ago
    You're right, I shouldn't have said many. But there are RNGs which are faster, smaller, and simpler and fail fewer tests, so I don't know why MT would ever be used. It could win in period I guess, if anyone could ever use that large a period. It is a heated debate, but it should be easier to agree that some RNG is not the best one than to agree it is.

edflsafoiewq 7y ago

I would not recommend MT. It fails many tests, that state is big, the code is complex, and it's not very fast. For non-crypto PRNGs, I'd reach for PCG or one of Vigna's generators.

strenholme 7y ago
I tend to agree, but I need to point out that MT19937 doesn’t fail “many” tests. It fails, at most, two of the bigcrush tests: https://en.wikipedia.org/wiki/Talk:Mersenne_Twister https://en.wikipedia.org/wiki/Talk:Mersenne_Twister and look for the “TestU01” discussion on that page. The biggest problem with MT19937, besides its complexity and large state size, is that it needs to have its state properly seeded. Like I said, it’s a heated debate which random number generator is the best one.
- FabHK 7y ago
  It is surprisingly heated debate, and it's hard to extract good advice from experts (I've asked Art Owen, Monte Carlo expert at Stanford, for up-to-date advice (he recommended MT19937 some 15 years ago), and he was very hesitant to utter any strong recommendations...) Having said that, I think most projects should move on from MT19937 by now, defaulting to a cryptographically secure PRNG, and allowing to switch to a faster one (such as PCG or xoroshiro) when desired.
  - strenholme 7y ago
    MT19937 is probably not the best PRNG out there, but the nice thing about it is that, for a long time, there was a pretty strong consensus among programmers that it was the PRNG to use. It’s a better choice than a simple LCG, which is what programmers tend to use if they’re not using MT. There are a lot of crypto-strong RNGs out there (AES on OFB mode? Counter Mode? SHA-3 in SHAKE128 or SHAKE256? Salsa20 or ChaCha? Or, do what I do and use RadioGatún[32]), so not much standardization on that front. With non crypto, we have in this thread already mentioned PCG ( http://www.pcg-random.org/ http://www.pcg-random.org/ ), JKISS32, xoroshiro, and Vigna’s generators. There are others. Again, not much standardization.
    - FabHK 7y ago
      I thought the xoroshiros are basically Vigna's? Developed further from precursors. But you're right, there's no successor anointed yet to MT19937, but it's about time. Wish some real expert in the field would publish an authoritative account (but opinionated enough to make real choices) that programming language devs could point to, and across the board implement: * safe (ie, a cryptographically secure PRNG) <- default * fast (if your application needs speed more than security against adversaries, such as Monte Carlo integration) * others (if you really know what you're doing) EDIT to add: it feels a bit like the old chestnut about IBM: nobody ever gets fired for choosing the Mersenne Twister...
- edflsafoiewq 7y ago
  You're right, I shouldn't have said many. But there are RNGs which are faster, smaller, and simpler and fail fewer tests, so I don't know why MT would ever be used. It could win in period I guess, if anyone could ever use that large a period. It is a heated debate, but it should be easier to agree that some RNG is not the best one than to agree it is.