Random Fail

One of my common software interview questions involves the creation of a game board. Part of the problem includes the generation of random numbers. If the candidate is writing in C/C++, the typical code I see looks something like this:

srand(seed); // one time seeding of generator
// later on ...
r = (rand() % 6) + 1; // throw the dice

Plenty of people have discussed the drawbacks of rand(), but the interview problem is not focused on the random number generation itself, so I consider the code above reasonable. Recently I had a candidate use JavaScript as their language of choice. The candidate wrote:

r = Math.Floor((Math.Random() * 5) + 1); // [1...6] ?

I’m not a JavaScript expert, but I noticed a couple things right away. First, there appears to be no way to seed the generator, so it’s not reproducible. Second, Math.Random() returns a float in the range [0.0 to 1.0). In other words, the code above will never return the number 6 because Random() never generates a 1.0! Even if Random() returned values in the range [0.0 to 1.0] there would still be a big problem. Random() is a uniform generator, so it only returns precisely 1.0 on very rare occasions. Hence the distribution of numbers will look something like this, which is clearly not random:

Takeaway: getting random numbers correct is a non-trivial problem. A lot of information available on the Internet about generating random numbers is plan wrong. Beware. Test your generators to ensure that they are both random and uniform. If I was writing C++ code today that needed to throw a d6, it would look like this:

#include <random>
std::mt19937 mt(seed); // generation engine
std::uniform_int_distribution<int> ud(1,6); // distribution engine
// later on ...
r = ud(mt); // [1...6], uniformly distributed

For a hilarious 30 min excursion into the pitfalls of C/C++ rand(), see Stephan’s talk: rand Considered Harmful. You’ll never use rand() again.

Advertisements