5 ms·

Predictably Random

24 points by Fudgel 7y ago

woliveirajr 7y ago
TL;DR: random is hard because computers are deterministic; we use Pseudo-Random, and each function that generates pseudo-random must be tested to see how random the results are.
perspective1 7y ago
I'm not in the cryptography or random space beyond using libraries, but these visualizations are very clever. It's easy to see major problems. edit: It shows small-periods but otherwise it's not all that useful (see below).
- jgrahamc 7y ago
  It's easy to see some major problems, but take a look at this: https://random.isthe.link/?code=let+x+%3D+Date.now%28%29+%26+0xFFFFFFFF%3B%0Alet+y+%3D+45342%3B%0Alet+z+%3D+65453%3B%0Alet+w+%3D+z+%5E+y%3B%0Aw+%26%3D+0xFFFFFFFF%3B%0A%0Afunction+randomD%28%29+%0A%7B%0A+++++let+t+%3D+x%3B%0A+++++t+%5E%3D+t+<<+11%3B%0A+++++t+%26%3D+0xFFFFFFFF%3B%0A+++++t+%5E%3D+t+>>+8%3B%0A+++++t+%26%3D+0xFFFFFFFF%3B%0A%0A+++++x+%3D+y%3B+y+%3D+z%3B+z+%3D+w%3B%0A+%0A+++++w+%5E%3D+w+>>+19%3B%0A+++++w+%26%3D+0xFFFFFFFF%3B%0A+++++w+%5E%3D+t%3B%0A+++++w+%26%3D+0xFFFFFFFF%3B%0A%0A++++return+w%2F0xFFFFFFFF%3B%0A%7D%0A%0Aexport+default+randomD%3B https://random.isthe.link/?code=let+x+%3D+Date.now%28%29+%26... The random number generator here is used quite often in projects and it looks pretty random. But if you look at the code you can see that it has four numbers that store state and its output can be entirely predicted from those four numbers that are consecutive outputs of the RNG.
  - tiborsaas 7y ago
    It's quite useful if you want to see if your seeded RNG matches a high quality pRNG.
  - perspective1 7y ago
    Oh wow. At some point I've thrown up my hands and just used Pcg64 because people I trust but can't possibly verify recommended it. Your post reaffirms that that was the right decision (trusting others).
    - jgrahamc 7y ago
      Worth reading Knuth on this and his attempt to create his own RNG and fail horribly: http://www.informit.com/articles/article.aspx?p=2221790 http://www.informit.com/articles/article.aspx?p=2221790
OskarS 7y ago
Hubba bubba. This is maybe not the article to read if you want to learn how to implement randomness correctly. There's... many things wrong with it. Of course randomA is terrible, you're modding it with 16! It's never going to have a period longer than 16 like that! Same with randomB, just with a slightly larger number. Both of these are just bog-standard linear congruential generators. LCGs are pretty bad for anything "serious", but for picking Tetris pieces they're fine, and they're easy to implent (or at least I thought they were, but then you see an article like this where one of them has period 16...). I don't immediately recognie randomC(), but it also looks terrible. Just shifting some bits around and adding a counter. At least it has some internal state so it it's not stupidly periodic. I haven't read up on what's the issue with V8's Math.random(), but I would have to imagine it's superior to all these three. I'm also sure there's plenty of excellent randomness libraries (and plenty of terrible ones) on NPM. Also, this kind of visual inspection will weed out truly garbage PRNGs, but it's not a good test in general. Testing for pseudo-randomness is hard, and best left to people who know what they are doing. Also also: for Tetris, you shouldn't just pick pieces at random, that's not how Tetris works nowadays. Tetris works by putting all 7 pieces in a bag, and then pulling them out at random. When the bag is empty, you fill it again with the seven pieces and start over. More info here: [0]. If you're new to programming, implementing the 7-bag system properly is a good little challenge, you'll get to learn all about the Fisher-Yates shuffle [1]. [0]: https://tetris.fandom.com/wiki/Random_Generator https://tetris.fandom.com/wiki/Random_Generator [1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- willis936 7y ago
  Or as they call it in the biz: sample without replacement.
  - OskarS 7y ago
    Essentially, yes, but the idea here is to create an endless stream but with just 7 pieces, so you restart the sampling after every bag.
- defertoreptar 7y ago
soVeryTired 7y ago
RNGs are like crypto: don't roll your own! There's some really deep number theory behind many of them. Every RNG I've seen lets you control the seed, so I'm not sure what he gains by writing his own.
- ChrisSD 7y ago
  Javascript doesn't allow setting the seed: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - soVeryTired 7y ago
    Yikes!
  - strenholme 7y ago
    Probably time to use a third party RNG for Javascript then. For example, https://gist.github.com/banksean/300494 https://gist.github.com/banksean/300494 or, if you don’t like MT19937 (shameless plug) https://github.com/samboy/rg32hash/blob/master/rg32.js https://github.com/samboy/rg32hash/blob/master/rg32.js
Pinbenterjamin 7y ago
Kind of unrelated, but I recently tested out a scenario for the Dotnet Environment that worked really well; I created a 'Random' service that lives for the length of the execution of the application. This service has an instance of Random that persists with the object, and exposes simple methods with min/max parameters. I register the service in a unity container, and then immediately resolve it, causing the Random type inside of the random service to instantiate. Then anywhere I want to generate a random number, I inject that service. This works because, as long as you persist a single instance of 'Random', two calls to 'Next' or 'NextDouble' won't result in the same number.
willis936 7y ago
Why not use RDRAND? Also you can always choose well-established, arbitrarily complex psuedo random algorithms. If you want to guarantee low correlation you could use PRBS (whatever shift amount you need, 31 may be enough for most scenarios) with the same shift register values and seeds that are maximally equidistant.
- lvh 7y ago
  Article mentions he wants to make the seed explicit so he can reproduce the same (randomly selected) environment. You can use any stream cipher you want instead, of course, but in my experience for video games the problem isn’t “I need a random bit” (which AES CTR is very good at but MT or any PCG/LCG is really just as fit for purpose) but “I need to sample from this weird distribution”. Stuff goes wrong as soon as someone needs to do something as simple as sampling from a set of cardinality not exactly a power of two let alone something more complex.
strenholme 7y ago
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
The article is amateurish, and it neither reflects the range and complexity of issues surrounding PRNGs, nor does it offer any good advice (except maybe "don't just use the first PRNG you come across"). A better introduction is the PCG website (it's biased towards PCG, but a) that's not a bad choice for many use cases, and b) it raises and discusses many issues regarding PRNG choice). http://www.pcg-random.org http://www.pcg-random.org EDIT to add: and FWIW, any serious PRNG of course allows seeding, and then the issue boils down to choosing a shared seed.
grayed-down 7y ago
Test and debate all you want, but if your application needs random data and it has access or intermittent access to the internet, use the Cesium isotope 137 :) https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/
deleted 7y ago
[deleted]

24 points by Fudgel 7y ago

TL;DR: random is hard because computers are deterministic; we use Pseudo-Random, and each function that generates pseudo-random must be tested to see how random the results are.

perspective1 7y ago

I'm not in the cryptography or random space beyond using libraries, but these visualizations are very clever. It's easy to see major problems. edit: It shows small-periods but otherwise it's not all that useful (see below).

jgrahamc 7y ago
It's easy to see some major problems, but take a look at this: https://random.isthe.link/?code=let+x+%3D+Date.now%28%29+%26+0xFFFFFFFF%3B%0Alet+y+%3D+45342%3B%0Alet+z+%3D+65453%3B%0Alet+w+%3D+z+%5E+y%3B%0Aw+%26%3D+0xFFFFFFFF%3B%0A%0Afunction+randomD%28%29+%0A%7B%0A+++++let+t+%3D+x%3B%0A+++++t+%5E%3D+t+<<+11%3B%0A+++++t+%26%3D+0xFFFFFFFF%3B%0A+++++t+%5E%3D+t+>>+8%3B%0A+++++t+%26%3D+0xFFFFFFFF%3B%0A%0A+++++x+%3D+y%3B+y+%3D+z%3B+z+%3D+w%3B%0A+%0A+++++w+%5E%3D+w+>>+19%3B%0A+++++w+%26%3D+0xFFFFFFFF%3B%0A+++++w+%5E%3D+t%3B%0A+++++w+%26%3D+0xFFFFFFFF%3B%0A%0A++++return+w%2F0xFFFFFFFF%3B%0A%7D%0A%0Aexport+default+randomD%3B https://random.isthe.link/?code=let+x+%3D+Date.now%28%29+%26... The random number generator here is used quite often in projects and it looks pretty random. But if you look at the code you can see that it has four numbers that store state and its output can be entirely predicted from those four numbers that are consecutive outputs of the RNG.
- tiborsaas 7y ago
  It's quite useful if you want to see if your seeded RNG matches a high quality pRNG.
- perspective1 7y ago
  Oh wow. At some point I've thrown up my hands and just used Pcg64 because people I trust but can't possibly verify recommended it. Your post reaffirms that that was the right decision (trusting others).
  - jgrahamc 7y ago
    Worth reading Knuth on this and his attempt to create his own RNG and fail horribly: http://www.informit.com/articles/article.aspx?p=2221790 http://www.informit.com/articles/article.aspx?p=2221790

OskarS 7y ago

Hubba bubba. This is maybe not the article to read if you want to learn how to implement randomness correctly. There's... many things wrong with it. Of course randomA is terrible, you're modding it with 16! It's never going to have a period longer than 16 like that! Same with randomB, just with a slightly larger number. Both of these are just bog-standard linear congruential generators. LCGs are pretty bad for anything "serious", but for picking Tetris pieces they're fine, and they're easy to implent (or at least I thought they were, but then you see an article like this where one of them has period 16...). I don't immediately recognie randomC(), but it also looks terrible. Just shifting some bits around and adding a counter. At least it has some internal state so it it's not stupidly periodic. I haven't read up on what's the issue with V8's Math.random(), but I would have to imagine it's superior to all these three. I'm also sure there's plenty of excellent randomness libraries (and plenty of terrible ones) on NPM. Also, this kind of visual inspection will weed out truly garbage PRNGs, but it's not a good test in general. Testing for pseudo-randomness is hard, and best left to people who know what they are doing. Also also: for Tetris, you shouldn't just pick pieces at random, that's not how Tetris works nowadays. Tetris works by putting all 7 pieces in a bag, and then pulling them out at random. When the bag is empty, you fill it again with the seven pieces and start over. More info here: [0]. If you're new to programming, implementing the 7-bag system properly is a good little challenge, you'll get to learn all about the Fisher-Yates shuffle [1]. [0]: https://tetris.fandom.com/wiki/Random_Generator https://tetris.fandom.com/wiki/Random_Generator [1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

willis936 7y ago
Or as they call it in the biz: sample without replacement.
- OskarS 7y ago
  Essentially, yes, but the idea here is to create an endless stream but with just 7 pieces, so you restart the sampling after every bag.
defertoreptar 7y ago

soVeryTired 7y ago

RNGs are like crypto: don't roll your own! There's some really deep number theory behind many of them. Every RNG I've seen lets you control the seed, so I'm not sure what he gains by writing his own.

ChrisSD 7y ago
Javascript doesn't allow setting the seed: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- soVeryTired 7y ago
  Yikes!
- strenholme 7y ago
  Probably time to use a third party RNG for Javascript then. For example, https://gist.github.com/banksean/300494 https://gist.github.com/banksean/300494 or, if you don’t like MT19937 (shameless plug) https://github.com/samboy/rg32hash/blob/master/rg32.js https://github.com/samboy/rg32hash/blob/master/rg32.js

Pinbenterjamin 7y ago

Kind of unrelated, but I recently tested out a scenario for the Dotnet Environment that worked really well; I created a 'Random' service that lives for the length of the execution of the application. This service has an instance of Random that persists with the object, and exposes simple methods with min/max parameters. I register the service in a unity container, and then immediately resolve it, causing the Random type inside of the random service to instantiate. Then anywhere I want to generate a random number, I inject that service. This works because, as long as you persist a single instance of 'Random', two calls to 'Next' or 'NextDouble' won't result in the same number.

willis936 7y ago

Why not use RDRAND? Also you can always choose well-established, arbitrarily complex psuedo random algorithms. If you want to guarantee low correlation you could use PRBS (whatever shift amount you need, 31 may be enough for most scenarios) with the same shift register values and seeds that are maximally equidistant.

lvh 7y ago
Article mentions he wants to make the seed explicit so he can reproduce the same (randomly selected) environment. You can use any stream cipher you want instead, of course, but in my experience for video games the problem isn’t “I need a random bit” (which AES CTR is very good at but MT or any PCG/LCG is really just as fit for purpose) but “I need to sample from this weird distribution”. Stuff goes wrong as soon as someone needs to do something as simple as sampling from a set of cardinality not exactly a power of two let alone something more complex.

strenholme 7y ago

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

The article is amateurish, and it neither reflects the range and complexity of issues surrounding PRNGs, nor does it offer any good advice (except maybe "don't just use the first PRNG you come across"). A better introduction is the PCG website (it's biased towards PCG, but a) that's not a bad choice for many use cases, and b) it raises and discusses many issues regarding PRNG choice). http://www.pcg-random.org http://www.pcg-random.org EDIT to add: and FWIW, any serious PRNG of course allows seeding, and then the issue boils down to choosing a shared seed.

grayed-down 7y ago

Test and debate all you want, but if your application needs random data and it has access or intermittent access to the internet, use the Cesium isotope 137 :) https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/

deleted 7y ago

[deleted]