Better Random Number Generation: Mersenne Twister 19937

Posted: March 28th, 2010 under ActionScript 3.0.

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

So, Adobe will not release the methodology behind how their Math.random() function works:
“Returns 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.” – from Adobe live docs as of the writing of this article.

All 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 ‘random’ numbers is a frustration of many people (usually not game developers, but there are plenty of practical applications that require it, cryptography for example).

The other, more common problem, and the blight of every Flash dice game is that the Math.random() function tends to be ‘streaky’ or becomes ‘stuck’ on a number. This is due to the Math.random() 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 – Flash’s 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’s problem is that these kinds of events happen at a higher frequency than they would in a true uniform distribution.

Anyone that has written game engine code is familiar with the Mersenne Twister 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.

I’m 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.

The Mersenne Twister gets its name from the Mersenne primes – 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 – 1. There are only 47 known Mersenne Primes, somewhat fantastically, 2147483647, or 2^31 – 1, or the upper bound on a 32 bit integer is one as well. There is a one-to-one relationship between Mersenne Primes and ‘perfect numbers’ 2^(p-1) * (2^p – 1), which written in binary are all of the form p 1s followed by (p – 1) zeros. Perfect numbers are not entirely relevant but just one of the things I discovered about Mersenne Primes and binary numbers that blew my mind, if you need more mind candy check out the connections between Mersenne primes and digital roots, and the relationship between perfect and triangular numbers.

The prime for the Mersenne Twister is often written as 2^(nw – r) – 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.

//Mersenne Twister variables
public static var MT:Array;
public static var indexMT:int;

//—————————————————————————————
//***************************************************************************************

//—————————————————————
//these functions compose the algorithm for a Mersenne Twister
//see http://en.wikipedia.org/wiki/Mersenne_twister
//This is a MT19937 implementation
//named because it has a proven 2^19937 – 1 period (approx 4.3 * 10^6001)
//(w, m, n, r) = (32, 624, 397, 31)
//a = 0x9908B0DF
//u = 11
//(s, b) = (7, 0x9D2C5680)
//(t, c) = (15, 0xEFC60000)
//l = 18
//it generates numbers in the range 0 to 2^32 – 1
//—————————————————————-

//while MT is the ‘best’ random number generator, it is considerably slower
//then Flash’s Math.random()

public static function initializeRandGenerator(seed:uint):void{
    //the seed can be any positive integer
    MT = new Array();
    indexMT = 624;
    MT[0] = seed;
   
    var i:int;
    for(i = 1; i < 624; i++){
        MT[i] = uint(0xFFFFFFFF & (0x6C078965 * (MT[i-1] ^ (MT[i-1] >>> 30)) + i));
    }          
}

public static function quickRand():uint{
    if(indexMT == 624){
        indexMT = 0;
        generateRands();
    }
   
    var y:uint = MT[indexMT]
    y = y ^ (y >>> 11);
    y = y ^ ((y << 7) & 0x9D2C5680);
    y = y ^ ((y << 15) & 0xEFC60000);
    y = y ^ (y >>> 18);
    indexMT++;
    return y;
}

public static function generateRands():void{
    var i:int;
    var y:uint;        
    for(i = 0; i < 227; i++){              
        y = (0×80000000 & MT[i]) + (0x7FFFFFFF & (MT[i+1]));                   
        MT[i] = MT[i + 397] ^ (y >>> 1) ^ ((y & 0×1) * 0x9908B0DF);                
    }
    //special case for i + 397 > 624 to avoid a mod operator
    for(i = 227; i < 623; i++){            
        y = (0×80000000 & MT[i]) + (0x7FFFFFFF & (MT[i+1]));                   
        MT[i] = MT[i - 227] ^ (y >>> 1) ^ ((y & 0×1) * 0x9908B0DF);                
    }          
    //special case for last value, to avoid mod operator
    y = (0×80000000 & MT[623]) + (0x7FFFFFFF & (MT[0]));
    MT[623] = MT[396] ^ (y >>> 1) ^ ((y & 0×1) * 0x9908B0DF);  
   
}

//***************************************************************************************
//—————————————————————————————
 

*Special thanks to the Quick Highlighter team for the code embed CSS and HTML

So the only real question left is what do you pick for a seed value? If you always use the same number, the ‘random generator’ will always return the same sequence. Therefore, you need a random way to seed the generator – quite the paradox. You can use Flash’s random number generator to provide an initialization integer, personally I think it’s clever to derive a value from the date and time the application runs.

Thanks for reading, and remember, we are all in this together.

Bookmark this on Delicious

5 Comments »

  • Comment by Todd — March 28, 2010 @ 4:23 pm

    1

    That was interesting. I remember dealing with that issue at SemTech. How is the performance in Flash? Does it work as smoothly as the built-in math.random?


  • Comment by Tapir — May 23, 2010 @ 3:55 am

    2

    great implementation!

    Can I use it in my games for free?


  • Comment by Stephen Calender — May 23, 2010 @ 9:56 am

    3

    Mersenne Twister is freely available, if you check out the authors web site you can find the license:

    “Until 2001/4/6, MT had been distributed under GNU Public License, but after 2001/4/6, we decided to let MT be used for any purpose, including commercial use. 2002-versions mt19937ar.c, mt19937ar-cok.c are considered to be usable freely.”


  • Comment by anon — April 7, 2011 @ 8:57 am

    4

    Does this really work in actionscript, I was under the impression the integers were 32 bits only? There’s a few places where they are multiplied together, If I understand correctly action script will convert them to lossy Numbers in that case, and the least significant bits are lost, as well as some performance degradation due to number conversions.


  • Comment by Stephen Calender — May 30, 2011 @ 11:56 pm

    5

    If it didn’t work I wouldn’t have posted it.

    I don’t blame you for asking though, I have been burned in the past by online code samples (even samples on Adobe’s site) and 3rd party code before.

    If you are still doubtful. First look at the other implementations on Wikipedia. Copy one of theirs and compare results with the same seed, and generate a bunch of randoms numbers and check out the distribution in Excel or a similar program.


RSS feed for comments on this post. TrackBack URL

Leave a comment