12
\$\begingroup\$

Recently I got used to modern languages which include a stock good random generator, which usually is the Mersenne Twister; now that I got back to C++ I have to decide what to use.

I searched for Mersenne Twister implementations and I noticed there are so many: is there one which is more used and widespread, or am I supposed to pick one assuming they are all equally good?

\$\endgroup\$
  • 1
    \$\begingroup\$ I like your separation of C++ and modern languages. \$\endgroup\$ – jcora Mar 17 '12 at 23:14
  • 2
    \$\begingroup\$ Maybe saying "higher level" was more appropriate. \$\endgroup\$ – o0'. Mar 17 '12 at 23:27
  • \$\begingroup\$ I think this question belongs on stackoverflow \$\endgroup\$ – TravisG Mar 18 '12 at 8:48
  • 5
    \$\begingroup\$ On SO I'd give a different answer because I wouldn't know it was for a game engine as opposed to, say, Monte Carlo simulations for medical therapies, in which case not having 624 dimensions of randomness can be deadly. \$\endgroup\$ – user744 Mar 18 '12 at 8:58
19
\$\begingroup\$

C++11 includes a Mersenne Twister generator by default as part of its new <random> interface. For example, to generate integers uniformly between [-10, 10] using MT:

std::mt19937 eng; // This is the Mersenne Twister
std:::uniform_int_distribution<int> dist(-10, 10)
for (int i = 0; i < 10; ++i)
    std::cout << dist(eng) << std::endl;

Most of this is also available in any compiler offering TR1 though the names are slightly different; std::tr1::mt19937 and std::tr1::uniform_int<int>.

I usually caution people away from using Mersenne Twister. It's an okay algorithm but a lot of its popularity is just marketing. 624 dimensions of randomness is more than most people need, and MT carries relatively heavy state requirements and when it does a full table recalc it can blow cache. I am personally partial to xorshift which gives excellent periods and reasonable distributions for anything a game needs, with tiny memory and CPU requirements.

I've written a (mostly?) C++11-compliant xorshift generator - xorshift.hpp, xorshift.cpp - and placed it in the public domain. You can plug this into any C++11 randomization function, as above:

xorshift eng;
std:::uniform_int_distribution<int> dist(-10, 10)
for (int i = 0; i < 10; ++i)
    std::cout << dist(eng) << std::endl;
\$\endgroup\$
  • 5
    \$\begingroup\$ Yeah, that's the kind of answer I was looking for, that's why I posted here on gamedev : ) \$\endgroup\$ – o0'. Mar 18 '12 at 10:34
  • 1
    \$\begingroup\$ Just wanted to note that nothing in the files you linked indicate that they are in the public domain. The way copyright law works, there really needs to be a clear note about that, as the law assumes "all rights reserve" by default. It's actually even safer to just use something like the MIT or BSD 2-clause license, since some jurisdictions basically don't acknowledge "this is in the public domain" as legally binding. If you're interested in seeing people use your code, it might be worth taking care of that. \$\endgroup\$ – Sean Middleditch Mar 18 '12 at 23:19
  • 1
    \$\begingroup\$ @seanmiddleditch: I am being clear about it right here. If you want it under a MIT-style license, I'll follow SQLite's lead and give that to you for only $1000. \$\endgroup\$ – user744 Mar 19 '12 at 9:35
  • \$\begingroup\$ The lack if a header in the code declaring anything (which SQLite does, iirc) is the main problem. If you don't care, that's cool. Was just giving you a friendly suggestion. \$\endgroup\$ – Sean Middleditch Mar 19 '12 at 20:40
1
\$\begingroup\$

Another RNG I've used before for gamedev purposes is Bob Jenkins' "small" RNG, described here.

(He also has a cryptographic-strength RNG called ISAAC, but it's bigger and slower, and games don't need that level of strength.)

\$\endgroup\$
  • 1
    \$\begingroup\$ That looks more expensive than xorshift (4 xors and 3 shifts vs. 4 adds, 6 shifts, 2 ors, and a xor), has a worse period, and runs the risk of very short cycles with certain initializations. It looks fast but not fastest; okay period but nowhere near optimal; same basic distribution qualities as xorshift; I don't see any reason to use it. \$\endgroup\$ – user744 Mar 18 '12 at 20:11
  • \$\begingroup\$ Fair enough. I don't know enough about RNG analysis to dig into the distribution and cycle properties. \$\endgroup\$ – Nathan Reed Mar 18 '12 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.