6 ms·

Random in the wild

173 points by donmcc 12y ago

anders 12y ago
> Perhaps there is a reason why software like Lua, Python, and Ruby all include their own implementation of a Mersenne Twister. As far as I know, Lua does not include Mersenne Twister. math.random() is just C rand().
- mbq 12y ago
  Also MT still has to be seeded, it is not crypto-safe and its quality/computational load ratio is not too good.
  - Scaevolus 12y ago
    It's far more complex than it needs to be. If you want a fast, high quality deterministic RNG, use something from the xorshift family.
    - edwintorok 12y ago
      This is a good article describing fast non-cryptographic RNGs: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand... http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand... CMRES is quite impressive, I get ~1500 MB/s out of it. Quite useful for generating large unique files for various testcases.
- pygy_ 12y ago
  This is correct for the standard Lua interpreter [0]. LuaJIT bundles its own Tausworthe PRNG [1]. ———— 0. http://www.lua.org/manual/5.2/manual.html#pdf-math.random http://www.lua.org/manual/5.2/manual.html#pdf-math.random 1. http://luajit.org/extensions.html#math_random http://luajit.org/extensions.html#math_random
- Karunamon 12y ago
  I've noticed that Ruby's RNG is not that great. I've got a couple of small IRC bot scripts, one is a dice roller, the other is one that takes random items from a Google spreadsheet (using simple Random#rand in the first case, and Array#sample in the second). The dice seems biased to certain numbers, and the spreadsheet has the same items come up more than mundane statistics would otherwise suggest. (A 1/50 roll landing on the same item 2-3 times in a row, multiple times per day?) It's gotten to the point where my users don't want to use my bot for RPGs. I'll have to see if using SecureRandom#random_number produces any different results
clarry 12y ago
I would've appreciated if you'd annotated each snippet with the source so as to make it easier for us to find the program it came from. One interesting question to ask next would be, what do these programs do with their random numbers? And so, does the quality of the stream or the non-repeatability of it matter at all?
- waterhouse 12y ago
  Since he's mocking and snarking at each snippet, I think adding pointers to the sources would make it come off as an incitement to make fun of the authors, and rather more mean than he intended. An alternative would be to add direct citations but tone down the snark. I think Ted wanted to focus on the code examples themselves, and to make an overarching point about how "rand" is actually used in practice. That said, if you want to figure it out, he did say they were "selected examples" from this list of projects: http://marc.info/?l=openbsd-tech&m=141776286105814&w=2 http://marc.info/?l=openbsd-tech&m=141776286105814&w=2 Also, you may be able to google for exact text matches with the code. (You might find other projects that have the exact same problem--but that is likely good enough.)
  - moron4hire 12y ago
    There was a particularly egregious example near the end that a simple Google search definitively found only one copy.
sarciszewski 12y ago
For cryptography, there's really no reason to use rand(), mt_rand(), or the other insecure variants. No excuse, I should say. Just use urandom. Or getentropy() if your OS supports it. If you're not using it for cryptographic purposes, then I don't see why it matters. :)
- jsnell 12y ago
  There are all kinds of apps that might not need crypto quality randomness, but do at least need the random number streams to be different between invocations of the program! A Monte Carlo simulation that always gets the same results isn't going to be too hot. A game that seeds the RNG with 16 bits of entropy will be fine for a single player, but not for a community. (Think of FreeCell or Minesweeper in Windows, though those might even have been just 15 bits).
  - sarciszewski 12y ago
    > There are all kinds of apps that might not need crypto quality randomness, but do at least need the random number streams to be different between invocations of the program! If you need high quality randomness, you probably should use urandom. If no where else, when the program is first executed. And if you're on Windows: https://github.com/php/php-src/blob/e6ea376a91514c59d21f4b53ccbb8c06fa42447b/win32/winutil.c#L80-L123 https://github.com/php/php-src/blob/e6ea376a91514c59d21f4b53...
    - pbsd 12y ago
      On Windows, the easy way is to call `rand_s`: http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx
  - conistonwater 12y ago
    > A Monte Carlo simulation that always gets the same results isn't going to be too hot. A Monte Carlo simulation absolutely needs to be able to produce the same numbers every time if you want to have a hope of debugging it. In a release version, yes, sure. But even there, people will still have concerns about replicating other people's results, so being careful with random seeds is important.
colmmacc 12y ago
My own favourite random() in the wild bug is one that I've come across many many times: /* Generate a random number 0...5 inclusive */ int r = random() % 6; The problem is that this results in a bias towards certain values, because the random() return space is probably not a whole multiple of the number you are modding. It's easier if you think what would happen if RAND_MAX were "10". Then the results 0,1,2,3,4 each have two opportunities of being selected for r, but "5" only has one. So 5 is half as likely as any other number. Terrible! Using float/double random()'s don't always help either, because floating point multiplication has non-uniform errors. Instead, what you really need is: int random_n(int top) { if (top <= 0) { return -1; } while(1) { int r = random(top); if (r < (RAND_MAX - (RAND_MAX % top))) { return r; } } return -1; } Although it's better to replace random() itself with something that uses real entropy.
- conistonwater 12y ago
  On my machine RAND_MAX is 2^31-1. So getting the probability wrong in the way you describe means a relative error of one in two billion. That's really quite small for non-critical applications.
  - clarry 12y ago
    Doesn't matter what your RAND_MAX is if you're taking the result modulo anything that's not a power of two.
    - conistonwater 12y ago
      No, it does matter. If RAND_MAX is really large, the relative error in "incorrect" probabilities is really small. Unless you have a critical need for it to be precisely correct, the error is basically negligible.
      - christianmann 12y ago
        And if you have a need for it to be precisely correct, I have bad news for you about the word "random".
sjolsen 12y ago
This sort of code is one of the motivations behind improving the random number generation facilities available in C++. If you're using C++ or you're using C and have the option to link with C++, I strongly recommend looking at the random number library introduced in C++11 [1]. In addition to letting you specify a statistical distribution (including a proper uniform distribution for both integral and floating-point types), it lets you choose between various PRNG engines with various trade-offs. It also provides a way to source hardware entropy with which to seed an engine, and it's all pretty easy to use. *[1] en.cppreference.com/w/cpp/numeric
- nepalisaathi 12y ago
  Proper link en.cppreference.com/w/cpp/numeric
- jacobparker 12y ago
  Language lawyer note: std::random_device isn't guaranteed to be hardware-based, or anything in particular: http://en.cppreference.com/w/cpp/numeric/random/random_device http://en.cppreference.com/w/cpp/numeric/random/random_devic... (GNU libstdc++ will use rdrand if possible, otherwise it will read from /dev/urandom: https://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2B%2B-v3/src/c%2B%2B11/random.cc;hb=HEAD https://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2B...)
  - sjolsen 12y ago
    You are correct; and of course, any hardware-level behaviour is likely to be implementation defined. I should note that MSVC [1] guarantees "non-deterministic and cryptographically secure" behaviour; and that libc++ [2] uses the "cryptographically secure" rand_s [3] on Windows, NaCl on other platforms where NaCl is available, and /dev/urandom where it isn't. [1] http://msdn.microsoft.com/en-us/library/bb982250.aspx http://msdn.microsoft.com/en-us/library/bb982250.aspx [2] https://github.com/llvm-mirror/libcxx/blob/master/src/random.cpp https://github.com/llvm-mirror/libcxx/blob/master/src/random... [3] http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx
- 12y ago
viraptor 12y ago
With all the comments author makes about nonstandard and crazy behaviour, he actually misses some practical solutions and makes fun of them. "The one operation that was not observed was substracting the pid from the time. More research into this subject is warranted." It's actually simple (even if still not effective on pid wraparound) - pid numbers grow, at a rate of at least 1 per program execution. Time grows at around 1 second per second. If you substituted pid from time, there's a good chance you would get the same seed by running the app twice in a row. So it's added instead, so that it always grows. And we pretend the wraparound happens very rarely. Broken behaviour? Sure. Practical solution that works for 99% cases where non-critical randomness is required? Definitely.
mijoharas 12y ago
My favourite bit is: "Take 16 bytes of random data. No, wait, make that 15 bytes. Then hash it to four bytes to really squeeze the entropy in. Then seed." Good article

173 points by donmcc 12y ago

> Perhaps there is a reason why software like Lua, Python, and Ruby all include their own implementation of a Mersenne Twister. As far as I know, Lua does not include Mersenne Twister. math.random() is just C rand().

mbq 12y ago
Also MT still has to be seeded, it is not crypto-safe and its quality/computational load ratio is not too good.
- Scaevolus 12y ago
  It's far more complex than it needs to be. If you want a fast, high quality deterministic RNG, use something from the xorshift family.
  - edwintorok 12y ago
    This is a good article describing fast non-cryptographic RNGs: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand... http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand... CMRES is quite impressive, I get ~1500 MB/s out of it. Quite useful for generating large unique files for various testcases.
pygy_ 12y ago
This is correct for the standard Lua interpreter [0]. LuaJIT bundles its own Tausworthe PRNG [1]. ———— 0. http://www.lua.org/manual/5.2/manual.html#pdf-math.random http://www.lua.org/manual/5.2/manual.html#pdf-math.random 1. http://luajit.org/extensions.html#math_random http://luajit.org/extensions.html#math_random
Karunamon 12y ago
I've noticed that Ruby's RNG is not that great. I've got a couple of small IRC bot scripts, one is a dice roller, the other is one that takes random items from a Google spreadsheet (using simple Random#rand in the first case, and Array#sample in the second). The dice seems biased to certain numbers, and the spreadsheet has the same items come up more than mundane statistics would otherwise suggest. (A 1/50 roll landing on the same item 2-3 times in a row, multiple times per day?) It's gotten to the point where my users don't want to use my bot for RPGs. I'll have to see if using SecureRandom#random_number produces any different results

clarry 12y ago

I would've appreciated if you'd annotated each snippet with the source so as to make it easier for us to find the program it came from. One interesting question to ask next would be, what do these programs do with their random numbers? And so, does the quality of the stream or the non-repeatability of it matter at all?

waterhouse 12y ago
Since he's mocking and snarking at each snippet, I think adding pointers to the sources would make it come off as an incitement to make fun of the authors, and rather more mean than he intended. An alternative would be to add direct citations but tone down the snark. I think Ted wanted to focus on the code examples themselves, and to make an overarching point about how "rand" is actually used in practice. That said, if you want to figure it out, he did say they were "selected examples" from this list of projects: http://marc.info/?l=openbsd-tech&m=141776286105814&w=2 http://marc.info/?l=openbsd-tech&m=141776286105814&w=2 Also, you may be able to google for exact text matches with the code. (You might find other projects that have the exact same problem--but that is likely good enough.)
- moron4hire 12y ago
  There was a particularly egregious example near the end that a simple Google search definitively found only one copy.

sarciszewski 12y ago

For cryptography, there's really no reason to use rand(), mt_rand(), or the other insecure variants. No excuse, I should say. Just use urandom. Or getentropy() if your OS supports it. If you're not using it for cryptographic purposes, then I don't see why it matters. :)

jsnell 12y ago
There are all kinds of apps that might not need crypto quality randomness, but do at least need the random number streams to be different between invocations of the program! A Monte Carlo simulation that always gets the same results isn't going to be too hot. A game that seeds the RNG with 16 bits of entropy will be fine for a single player, but not for a community. (Think of FreeCell or Minesweeper in Windows, though those might even have been just 15 bits).
- sarciszewski 12y ago
  > There are all kinds of apps that might not need crypto quality randomness, but do at least need the random number streams to be different between invocations of the program! If you need high quality randomness, you probably should use urandom. If no where else, when the program is first executed. And if you're on Windows: https://github.com/php/php-src/blob/e6ea376a91514c59d21f4b53ccbb8c06fa42447b/win32/winutil.c#L80-L123 https://github.com/php/php-src/blob/e6ea376a91514c59d21f4b53...
  - pbsd 12y ago
    On Windows, the easy way is to call `rand_s`: http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx
- conistonwater 12y ago
  > A Monte Carlo simulation that always gets the same results isn't going to be too hot. A Monte Carlo simulation absolutely needs to be able to produce the same numbers every time if you want to have a hope of debugging it. In a release version, yes, sure. But even there, people will still have concerns about replicating other people's results, so being careful with random seeds is important.

colmmacc 12y ago

My own favourite random() in the wild bug is one that I've come across many many times: /* Generate a random number 0...5 inclusive */ int r = random() % 6; The problem is that this results in a bias towards certain values, because the random() return space is probably not a whole multiple of the number you are modding. It's easier if you think what would happen if RAND_MAX were "10". Then the results 0,1,2,3,4 each have two opportunities of being selected for r, but "5" only has one. So 5 is half as likely as any other number. Terrible! Using float/double random()'s don't always help either, because floating point multiplication has non-uniform errors. Instead, what you really need is: int random_n(int top) { if (top <= 0) { return -1; } while(1) { int r = random(top); if (r < (RAND_MAX - (RAND_MAX % top))) { return r; } } return -1; } Although it's better to replace random() itself with something that uses real entropy.

conistonwater 12y ago
On my machine RAND_MAX is 2^31-1. So getting the probability wrong in the way you describe means a relative error of one in two billion. That's really quite small for non-critical applications.
- clarry 12y ago
  Doesn't matter what your RAND_MAX is if you're taking the result modulo anything that's not a power of two.
  - conistonwater 12y ago
    No, it does matter. If RAND_MAX is really large, the relative error in "incorrect" probabilities is really small. Unless you have a critical need for it to be precisely correct, the error is basically negligible.
    - christianmann 12y ago
      And if you have a need for it to be precisely correct, I have bad news for you about the word "random".

sjolsen 12y ago

This sort of code is one of the motivations behind improving the random number generation facilities available in C++. If you're using C++ or you're using C and have the option to link with C++, I strongly recommend looking at the random number library introduced in C++11 [1]. In addition to letting you specify a statistical distribution (including a proper uniform distribution for both integral and floating-point types), it lets you choose between various PRNG engines with various trade-offs. It also provides a way to source hardware entropy with which to seed an engine, and it's all pretty easy to use. *[1] en.cppreference.com/w/cpp/numeric

nepalisaathi 12y ago
Proper link en.cppreference.com/w/cpp/numeric
jacobparker 12y ago
Language lawyer note: std::random_device isn't guaranteed to be hardware-based, or anything in particular: http://en.cppreference.com/w/cpp/numeric/random/random_device http://en.cppreference.com/w/cpp/numeric/random/random_devic... (GNU libstdc++ will use rdrand if possible, otherwise it will read from /dev/urandom: https://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2B%2B-v3/src/c%2B%2B11/random.cc;hb=HEAD https://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2B...)
- sjolsen 12y ago
  You are correct; and of course, any hardware-level behaviour is likely to be implementation defined. I should note that MSVC [1] guarantees "non-deterministic and cryptographically secure" behaviour; and that libc++ [2] uses the "cryptographically secure" rand_s [3] on Windows, NaCl on other platforms where NaCl is available, and /dev/urandom where it isn't. [1] http://msdn.microsoft.com/en-us/library/bb982250.aspx http://msdn.microsoft.com/en-us/library/bb982250.aspx [2] https://github.com/llvm-mirror/libcxx/blob/master/src/random.cpp https://github.com/llvm-mirror/libcxx/blob/master/src/random... [3] http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx http://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx
12y ago

viraptor 12y ago

With all the comments author makes about nonstandard and crazy behaviour, he actually misses some practical solutions and makes fun of them. "The one operation that was not observed was substracting the pid from the time. More research into this subject is warranted." It's actually simple (even if still not effective on pid wraparound) - pid numbers grow, at a rate of at least 1 per program execution. Time grows at around 1 second per second. If you substituted pid from time, there's a good chance you would get the same seed by running the app twice in a row. So it's added instead, so that it always grows. And we pretend the wraparound happens very rarely. Broken behaviour? Sure. Practical solution that works for 99% cases where non-critical randomness is required? Definitely.

mijoharas 12y ago

My favourite bit is: "Take 16 bytes of random data. No, wait, make that 15 bytes. Then hash it to four bytes to really squeeze the entropy in. Then seed." Good article