Silverlight 4 Coin-Flip Decision Maker based on Mersenne Twister

Have you ever had difficulty making a decision? The classic "Flip a Coin" method is time-tested (it's always right, too). This article shows how the Mersenne Twister algorithm can be used in a Silverlight app.

The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto and Takuji Nishimura that is based on a matrix linear recurrence over a finite binary field F2. It provides for fast generation of very high-quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms.

Its name derives from the fact that period length is chosen to be a Mersenne prime. There are at least two common variants of the algorithm, differing only in the size of the Mersenne primes used. The newer and more commonly used one is the Mersenne Twister MT19937, with 32-bit word length. There is also a variant with 64-bit word length, MT19937-64, which generates a different sequence.

For many applications the Mersenne twister is quickly becoming the pseudorandom number generator of choice; for example, it is the default in R, Mathematica, Maple, MATLAB, Gretl and the two popular scripting languages Python and Ruby. Since the algorithm is portable, freely available, and quickly generates high quality pseudorandom numbers, it is rarely a bad choice.

The pseudocode below illustrates the technique:

// Create a length 624 array to store the state of the generator
int[0..623] MT
int index = 0

// Initialize the generator from a seed
function initializeGenerator(int seed) {
     MT[0] := seed
     for i from 1 to 623 { // loop over each other element
         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
     }
}

// Extract a tempered pseudorandom number based on the index-th value,
// calling generateNumbers() every 624 numbers
function extractNumber() {
     if index == 0 {
         generateNumbers()
     }
    
     int y := MT[index]
     y := y xor (right shift by 11 bits(y))
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
     y := y xor (right shift by 18 bits(y))
    
     index := (index + 1) mod 624
     return y
}

// Generate an array of 624 untempered numbers
function generateNumbers() {
     for i from 0 to 623 {
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])
         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
         if (y mod 2) == 1 { // y is odd
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
         }
     }
}

For this example I used Mersenne Twister code from  CodeProject by  Dave Loeser, which remains faithful to the original MT19937 algorithm.



There are, however even better random number generators than the Mersenne Twister. For a great page containing resources including downloadable C# code, go here.

You can download the Visual Studio 2010 Silverlight 4 solution here.


By Peter Bromberg   Popularity  (2089 Views)