The Mersenne Twister Pseudo Random Number Generator

posted August 19, 2014 by Stephan Brumme

Introduction

The Mersenne Twister is often regarded as the fastest pseudo-random number generator which passes almost all statistical tests.

The original C code isn't exactly beautiful, therefore I decided to write my own C++ class.
And for the fun of it, I converted the code to Javascript and added two live demos, too (scroll down).

Live Demo

This demo will give you the first 10 random numbers generated by the Mersenne Twister.
My C++ implementation returns exactly the same values as the original code written by Makoto Matsumoto and Takuji Nishimura.

These numbers will be computed on the webserver whereas the Javascript code - which generates exactly the same numbers, too - obviously runs in your browser.
Modifying the seed value will change the sequence of random numbers. seed must be a 32 bit integer. If you leave it empty, 5489 will be used instead.

Seed:
C++:
Original:
Javascript:
(in hexadecimal)

I have written a live performance test of the Javascript Mersenne Twister: please scroll down on this page.

C++ code

The constructor accepts an optional seed value. The actual number generation is implemented as a functor.
Your program will look like this:

hide


     #include "mersenne.h"
     
     // create new Mersenne Twister
     MersenneTwister prng(123456);
     // generate two random 32-bit numbers
     int x = prng();
     int y = prng();

My implementation generates the same output as the original code when supplied with the same seed value.
I got rid of all the statics found in the original code which gives you the opportunity to have several independent Mersenne Twisters in your program at the same time.
Moreover, it reduced the risks of nasty concurrency effects in multi-threaded programs.

hide mersenne.h - header file


     // //////////////////////////////////////////////////////////
     // mersenne.h
     // Copyright (c) 2014 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #pragma once
     
     #include <stdint.h>
     
     /// Mersenne twister pseudo-random number generator
     /** algorithm invented by Makoto Matsumoto and Takuji Nishimura **/
     class MersenneTwister
     {
       /// state size
       enum   { SizeState = 624 };
       /// internal state
       uint32_t state[SizeState];
       /// offset of next state's word
       int      next;
     
     public:
       /// generate initial internal state
       MersenneTwister(uint32_t seed = 5489);
     
       /// return a random 32 bit number
       uint32_t operator()();
     
     private:
       /// create new state (based on old one)
       void twist();
     };

hide mersenne.cpp - implementation


     // //////////////////////////////////////////////////////////
     // mersenne.cpp
     // Copyright (c) 2014 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #include "mersenne.h"
     
     
     /// generate initial internal state
     MersenneTwister::MersenneTwister(uint32_t seed)
     : next(0)
     {
       state[0] = seed;
       for (int i = 1; i < SizeState; i++)
         state[i] = 1812433253UL * (state[i-1] ^ (state[i-1] >> 30)) + i;
     
       // let's twist'n'shout ...
       twist();
     }
     
     
     /// return a random 32 bit number
     uint32_t MersenneTwister::operator()()
     {
       // compute new state ?
       if (next >= SizeState)
         twist();
     
       // shuffle bits around
       uint32_t x = state[next++];
       x ^=  x >> 11;
       x ^= (x <<  7) & 0x9d2c5680;
       x ^= (x << 15) & 0xefc60000;
       x ^=  x >> 18;
       return x;
     }
     
     
     /// create new state (based on old one)
     void MersenneTwister::twist()
     {
       const int M = 397;
       const int FirstHalf = SizeState - M;
     
       // first 624-397=227 words
       int i;
       for (i = 0; i < FirstHalf; i++)
       {
         uint32_t bits = (state[i] & 0x80000000) | (state[i + 1] & 0x7fffffff);
         state[i] = state[i + M]         ^ (bits >> 1) ^ ((bits & 1) * 0x9908b0df);
       }
       // remaining words (except the very last one)
       for ( ; i < SizeState - 1; i++)
       {
         uint32_t bits = (state[i] & 0x80000000) | (state[i + 1] & 0x7fffffff);
         state[i] = state[i - FirstHalf] ^ (bits >> 1) ^ ((bits & 1) * 0x9908b0df);
       }
     
       // last word is computed pretty much the same way, but i + 1 must wrap around to 0
       uint32_t bits = (state[i] & 0x80000000) | (state[0] & 0x7fffffff);
       state[i] = state[M - 1] ^ (bits >> 1) ^ ((bits & 1) * 0x9908b0df);
     
       // word used for next random number
       next = 0;
     }

Git users: scroll down to the repository link

Download mersenne.h

Latest release: August 18, 2014, size: 743 bytes, 32 lines

CRC32: a028bca2
MD5: a0d1de2c02eaa91722b7591c4ca8eb9b
SHA1: 9e00279dc85bad24eb63379f87cfe20211e9e3ea
SHA256:79f195d0f0a1d154995a9fc0c94f8e3ebf17f37169127e28822facbaa17c82db

Download mersenne.cpp

Latest release: August 18, 2014, size: 1682 bytes, 66 lines

CRC32: 2f6d248c
MD5: 0e6b3353d5bae5e7b80f6534d880ec26
SHA1: 89c1fd6081d6cdc53854a76a8adb7e778374ffea
SHA256:8150b7eb8cfe24ed87926fbfa5a0ddc8ee1540cb4a44596a93e8b77206ba3507

Stay up-to-date:git clone https://create.stephan-brumme.com/mersenne-twister/git

GitHub mirror:https://github.com/stbrumme/mersenne-twister

If you encounter any bugs/problems or have ideas for improving future versions, please write me an email: create@stephan-brumme.com

There are a few C/C++ implementations available on the internet which might be slightly faster on certain SIMD architectures.
I am not aware of any library written in plain C/C++ that is significantly faster than the code shown above.

License

This code is licensed under the zlib License:

This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software. Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions: 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 3. This notice may not be removed or altered from any source distribution.zlib License

Javascript

The WebKit browser engine used the Mersenne Twister for Math.random() (but switched to the faster XorShift algorithm recently). However, inside Javascript code there is no way to control the generation of random numbers, for example by defining a seed value - which can be incredibly helpful during testing/debugging because then you can reproduce the same random numbers.

There are only a handful Javascript versions of the Mersenne Twister algorithms and most of them are pretty slow.
My Javascript port computes exactly the same numbers as the C++ version (when using the same seed value).
Firefox 31 (Windows) can spit out about 44 million random numbers per second on a three-year-old Intel Core i7 @ 3.4 GHz.
Internet Explorer 11 achieves about 23 million numbers per second on the same computer.
Obviously my Samsung S2 phone (three years old as well) is even slower and can generate only 3.8 million numbers per second (Firefox 31, too).

Live test:

Please note that my Mersenne Twister generates 32 bit signed integers whereas the output of Math.random() are floating-point numbers between 0 and 1.

And a simple bit distribution heatmap (move your mouse, double-click the heatmap to reset):

bits 0 - 7
bits 8 - 15
bits 16 - 23
bits 24 - 31

Current random number (hexadecimal):
Total of

Usage is pretty straightforward:

hide


     // load class
     <script src="http://create.stephan-brumme.com/mersenne-twister/mersenne.js">
     </script>
     
     <script>
       // create new Mersenne Twister
       var prng = new MersenneTwister((new Date).getTime());
       // generate two random 32-bit numbers
       var x = prng.random();
       var y = prng.random();
     </script>

I converted the code from C++ to Javascript by hand instead of using tools like Emscripten.
The most tricky part was coping with bit shifts and the limitation of Javascript's integer system.
Therefore you will find strangely looking symbols like the triple-right-shift >>> and explicit integer conversion using the And-Zero idiom (e.g. state[i] |= 0;). Git users: scroll down to the repository link

Download mersenne.js

Latest release: August 19, 2014, size: 2102 bytes, 75 lines

CRC32: 9c22dfda
MD5: 641108e6441ec79179742d916f38ad7f
SHA1: 4f1ad50a16675b5092899774ce0dbc25df9ae98e
SHA256:44bc7c23ad2115de39a3fb62e60b25c40c92beb7497c9b0cc91872616ea9a372

Stay up-to-date:git clone https://create.stephan-brumme.com/mersenne-twister/git

GitHub mirror:https://github.com/stbrumme/mersenne-twister

If you encounter any bugs/problems or have ideas for improving future versions, please write me an email: create@stephan-brumme.com

hide mersenne.js - Javascript version


     // //////////////////////////////////////////////////////////
     // mersenne.js
     // Copyright (c) 2014 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     
     var MersenneTwister = function(seed)
     {
       "use strict";
     
       var state = new Array(624);
       var next;
     
       // if no seed is given, use default value 5489
       if (seed == undefined)
         seed = 5489;
     
       // private function: create new state (based on old one)
       var twist = function()
       {
         // first 624-397=227 words
         for (var i = 0; i < 227; i++)
         {
           var bits = (state[i] & 0x80000000) | (state[i + 1] & 0x7fffffff);
           state[i] = state[i + 397] ^ (bits >>> 1) ^ ((bits & 1) * 0x9908b0df);
         }
         // remaining words (except the very last one)
         for (var i = 227 ; i < 623; i++)
         {
           var bits = (state[i] & 0x80000000) | (state[i + 1] & 0x7fffffff);
           state[i] = state[i - 227] ^ (bits >>> 1) ^ ((bits & 1) * 0x9908b0df);
         }
     
         // last word is computed pretty much the same way, but i + 1 must wrap around to 0
         var bits = (state[623] & 0x80000000) | (state[0] & 0x7fffffff);
         state[623] = state[396] ^ (bits >>> 1) ^ ((bits & 1) * 0x9908b0df);
     
         // word used for next random number
         next = 0;
       }
     
       // fill initial state
       state[0] = seed;
       for (var i = 1; i < 624; i++)
       {
         var s = state[i - 1] ^ (state[i - 1] >>> 30);
         // avoid multiplication overflow: split 32 bits into 2x 16 bits and process them individually
         state[i]  = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) +
                         (s & 0x0000ffff)         * 1812433253)        + i;
         // convert to 32 bit unsigned int
         state[i] |= 0;
       }
     
       // twist'n'shout
       twist();
     
     
       // public function: return a random 32 bit number
       this.random = function()
       {
         // compute new state ?
         if (next >= 624)
           twist();
     
         // shuffle bits around
         var x = state[next++];
         x ^=  x >>> 11;
         x ^= (x  <<  7) & 0x9d2c5680;
         x ^= (x  << 15) & 0xefc60000;
         x ^=  x >>> 18;
     
         return x;
       }
     };

The live demo shows the random numbers as hexadecimal values:

hide integer-to-hexadecimal conversion


     // load class
     <script src="http://create.stephan-brumme.com/mersenne-twister/mersenne.js">
     </script>
     
     <script>
       // create new Mersenne Twister
       var prng = new MersenneTwister((new Date).getTime());
       // generate two random 32-bit numbers
       var x = prng.random();
       var y = prng.random();
     </script>

Live demo's inner loop must take care of proper Javascript type conversion otherwise full optimization doesn't kick in.
A simple for-loop can be two times slower:

hide inner loop


     // prevents Javascript engine from eliminating the whole loop
     var dummy = 0;
     
     // make sure it's an integer
     var i = numValues | 0;
     // and go !
     while (i-- > 0)
       dummy ^= prng.random();
     
     // much slower: for (var i = 0; i < numValues; i++)


June 30, 2021: Length-Limited Prefix Codes April 13, 2020: smalLZ4 - optimal LZ4 compression June 17, 2019: toojpeg - a JPEG encoder in a single C++ file ... and 30 more !	RSS	www.stephan-brumme.com bits.stephan-brumme.com photos.stephan-brumme.com minime.stephan-brumme.com
© 2011-2024 Stephan Brumme products and company names mentioned may be trademarks of their respective owners. see my disclaimer. dude, this is the end ... of this page.