{"id":181,"date":"2010-03-28T14:48:00","date_gmt":"2010-03-28T19:48:00","guid":{"rendered":"http:\/\/www.stephencalenderblog.com\/?p=181"},"modified":"2016-04-16T11:26:21","modified_gmt":"2016-04-16T16:26:21","slug":"better-random-number-generation-mersenne-twister-19937","status":"publish","type":"post","link":"https:\/\/www.stephencalenderblog.com\/?p=181","title":{"rendered":"Better Random Number Generation: Mersenne Twister 19937"},"content":{"rendered":"

Math.random()<\/a> is the bane of many Flash game developers, and in this article I am going to help you work around it (free code).
\n<\/p>\n

So, Adobe will not release the methodology behind how their Math.random()<\/a> function works:
\n\u201cReturns a pseudo-random number n, where 0 <= n < 1. The number returned is calculated in an undisclosed manner, and pseudo-random because the calculation inevitably contains some element of non-randomness.\u201d \u2013 from Adobe live docs as of the writing of this article.\n\nAll random number generators are pseudo-random, because they are all algorithmic in nature. If you know the seed value and the algorithm, you can exactly predict the numbers the function will return. In fact, the inability to seed the generator and repeat a string of \u2018random\u2019 numbers is a frustration of many people (usually not game developers, but there are plenty of practical applications that require it, cryptography for example). \n\nThe other, more common problem, and the blight of every Flash dice game is that the Math.random()<\/a> function tends to be \u2018streaky\u2019 or becomes \u2018stuck\u2019 on a number. This is due to the Math.random()<\/a> function deviating from a uniform distribution. Statistically, and in as plain a language I can manage, you need to meet two criteria to qualify as a uniform distribution. First, nearly even dispersal across the range. In the case of a 6 sided die, if it was fair, and you rolled it 60 times, you would expect to see 1 through 6 represented equally \u2013 Flash\u2019s random number generator passes this test, but so would a die that roles 10 1s, then 10 2s, then 10 3s… The second criteria deals with the probability of specific events happening, in the case of our 6 sided die example, rolling the same number 2 times in a row is 1\/6 * 1\/6 * 6 = 1\/6, there is a 1\/36 chance to roll any double, there are 6 pair of doubles (1s, 2s, etc.). Odds of hitting any 3 streak is 1\/36. Flash\u2019s problem is that these kinds of events happen at a higher frequency than they would in a true uniform distribution.<\/p>\n

Anyone that has written game engine code is familiar with the Mersenne Twister<\/a> routine, the Playstation 3 even made it its native random number generator. While it has its critics, it has become widely adopted as the best (not to be read as fastest) number generator out there. It has seen such wide adoption in games because it is the most cost effective, the best quality numbers for its speed.<\/p>\n

I\u2019m a math nerd, and I really enjoy the beauty of the number theory which I elaborate on here; but no one will judge you if you skip to the bottom and just steal the code. Just remember to seed algorithm and that it returns a random unsigned integer i where 0 <= i < 0xFFFFFFFF = 4294967296. \n\nThe Mersenne Twister<\/a> gets its name from the Mersenne primes<\/a> \u2013 all primes that are of the form: 2 to a power minus 1. Often abbreviated as MT19937, the number part of the name comes from the length of the period: 2^19937 \u2013 1. There are only 47 known Mersenne Primes<\/a>, somewhat fantastically, 2147483647, or 2^31 \u2013 1, or the upper bound on a 32 bit integer is one as well. There is a one-to-one relationship between Mersenne Primes<\/a> and \u2018perfect numbers<\/a>\u2019 2^(p-1) * (2^p \u2013 1), which written in binary are all of the form p 1s followed by (p \u2013 1) zeros. Perfect numbers<\/a> are not entirely relevant but just one of the things I discovered about Mersenne Primes<\/a> and binary numbers that blew my mind, if you need more mind candy check out the connections between Mersenne primes<\/a> and digital roots<\/a>, and the relationship between perfect<\/a> and triangular numbers<\/a>. <\/p>\n

The prime for the Mersenne Twister<\/a> is often written as 2^(nw – r) \u2013 1 to clarify coefficients used in the algorithm. The values for n, w, and r are 32, 624, and 31 respectively for MT19937. Then we do a bunch of linear algebra to form a twist transformation (where the twister part of the name is derived) followed by a tempering transform to ensure as uniform of a distribution as possible. <\/p>\n