Click here to Skip to main content
14,545,108 members

A Mersenne Twister Class

Rate this:
4.86 (16 votes)
Please Sign up or sign in to vote.
4.86 (16 votes)
18 Feb 2003
A pseudorandom number generator.

Sample Image - MersenneTwisterClass.jpg

Introduction

The Mersenne Twister(MT) is a pseudorandom number generator (PRNG) developed by Makoto Matsumoto and Takuji Nishimura[1][2] during 1996-1997. MT has the following merits:

  • It is designed with consideration on the flaws of various existing generators.
  • Far longer period and far higher order of equidistribution than any other implemented generators. (It has been proven that the period is 2^19937-1, and 623-dimensional equidistribution property is assured.)
  • Fast generation. (Although it depends on the system, it is reported that MT is sometimes faster than the standard ANSI-C library in a system with pipeline and cache memory.)
  • Efficient use of the memory.

Credit where it's due

I present a C++ class (CRandomMT) that encapsulates the work of the creators. I do not take credit for their work, I am merely presenting an object oriented (OO) version of their code that you can simply drop into your game or application.

CRandomMT

Inspiration

In 2000 I was working on a random dungeon generator for a Roguelike and I asked the folks on rec.games.roguelike.development what they used for PRNG. One response (or maybe two) suggested that I give the MT a try. After reading about its merits (see above) I decided to download it and drop it in my Roguelike. I was surprised that I could not find an object oriented (OO) version of the algorithm and immediately sat down to wrap the code. I mean, that is what us C++ guys do... right?

Perspiration

Wrapping the code up wasn't all that difficult and there really wasn't any perspiration, which made me wonder even more why the algorithm had not been encapsulated into a C++ class and made publicly available. Nevertheless, I went about the business of pulling this function here and that one there and this one should be private, you know the drill, until I had a completely encapsulated version ready for use.

Roguelikes tend to need a good deal of random numbers so, my next task was to add a few methods that would make my Roguelike easier to code and the intentions of the code easy to read. The standard nomenclature for representing dice rolls is:
<number of dice>d<size of die> so, to roll 2 six sided dice you would write 2d6. Thinking about this for a bit I determined that the standard nomenclature would be difficult to translate into methods for my class but if I reverse the nomenclature to read:
d<size of die><number of dice> I could easily create methods that described the intentions of the code by creating methods such as CRandomMT::D6(int _DiceCount) and CRandomMT::D25(int _DiceCount). Ironically, these were merely wrappers around the method: CRandomMT::RollDice(int _DieSize, int _DiceCount).

Completion

Ahhh, completion... that really is the hardest part. I did complete the class that I present to you and I even completed this article. But, I failed to complete the Roguelike. Like everything that I have burned to CD, I suppose that I will get around to completing that work someday. I mean, that is what us C++ guys do... right?

Class Description

I should first point out that many of the methods are unneccessary for general use and that they are all inline. Because this was a game and I was going to need a ton of random numbers I opted for speed over size.

CRandomMT::CRandomMT()
This is the default CTOR.

CRandomMT::CRandomMT(ULONG seed)
A constructor that you provide the seed value.

CRandomMT::~CRandomMT()
The DTOR.

CRandomMT::SeedMT()
Used to seed or re-seed the random number generator.

ULONG CRandomMT::RandomMT()
Returns a unsigned long random number.

int CRandomMT::RandomRange(int hi, int lo)
Returns an int random number falling in the range specified.

int RollDice(int face, int number_of_dice)
Returns an int random number for the number of dice specified and the face of the die.

int CRandomMT::D#(int die_count)
Returns a simulated roll of the number of dice specified for the die (determined by #). These are just wrappers around RollDice()

int CRandomMT::HeadsOrTails()
Returns 0 or 1, used to simulate a coin flip.

Example Usage

#include "Random.h"	
	.
	.
	.
	CRandomMT MTrand(GetTickCount());
	int rand_3d6 = MTrand.D6(3);		// roll 3 six sided die
	.
	.
	.

About the demo application

The demo application is a fairly lame example but does demonstrate the equidistribution provided from the MT algorithm as well as the speed increase. Although I didn't percieve better distribution from the algorithm, the speed increase is significant witht the random routine being placed inline. Here we simulate flipping 100,000 coins and then visualy display the results with a CProgressCtrl and a couple static controls for the textual display.

NuMega TrueTime Statistics *
CRandomMT::RandomMT() not inlined
Function% in functionCalledAvgerage
rand()23.88100,0000.73
FlipRand()13.76141,864.76
CRandomMT::RandomMT()19.83100,0000.60
FlipMersenne()13.60141,378.81

NuMega TrueTime Statistics *
CRandomMT::RandomMT() inlined
Function% in functionCalledAvgerage
rand()31.76100,0000.72
FlipRand()18.22141,507.23
CRandomMT::RandomMT()INLINED
FlipMersenne()10.88126,168.42
    *
  • % in function: Time spent on this line and the functions it called as a percentage of the time spent in the entire function.
  • Called: Number of times the function was called.
  • Average: Average execution time of the function during the session.

Faster?

In the speed category it is clear that the MT algorithm is much faster. The difference is that FlipMersenne() in the inlined version averaged 26,168.42 -vs- the 41,507.23 of FlipRand() that is around a 45% increase in speed. This can be important in a game that needs to serve up tons of random numbers. Even the smaller increase in speed found in the non-inlined version results in big processor savings for applications that need to generate billions of random numbers.

Equidistribution?

The probability of a coin flip being heads or tails is expressed using the the mathmatical formula 1/n. Where n is the number of times the coin is tossed. In the demo application, we simulated flipping the coin 100,000 times. To my surprise rand() provided very good results based on a 50/50 assumption.

I started the application and brought up Excel, next I simulated flipping 100,000 coins 10 times and then I averaged the results from each of those iterations. Here are the results:

Mersenne Twister
FLIP(s)12345678910AVG %
HEADS5000649910498834967349962500734996549768501055011649.946
TAILS4999450090501175032750038499275003550232498954988450.054
rand()
FLIP(s)12345678910AVG %
HEADS4999850091499075010650144500974991949888500734984750.007
TAILS5000249909500934989449856499035008150112499275015349.993

The above results for rand()appear to come closer to the desired 50/50 distribution of a coin flip than that of MT. When one adds even a small error percentage to this statistical sample, it becomes clear that this test is more a wash than anything else. This leaves us with only speed as the determining factor in the decision to use the MT algorithim.

Conclussion

The pursuit of the perfect PRNG is an ongoing effort that eludes computer scientist and mathematicians alike. The Mersenne Twister is generally considered to be fast, small and provides equal distribution. I like the fact that I can generate 1,000,000,000 random numbers in about 0.45 seconds on a PIII 900mhz machine (with an urolled loop).

Thanks

Thanks go out to Makoto Matsumoto and Takuji Nishimura for creating the algorithm. I'd also like to thank my friend and business partner Derek Licciardi for his input and expertise in statistical analysis.

Links

References

  • [1] "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator", M. Matsumoto and T. Nishimura, ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3--30.
  • [2] Mersenne Twister: A random number generator, www.math.keio.ac.jp/~matumoto/emt.html

History

  • 19 Feb 2003 - updated source download

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Dave Loeser
Web Developer
United States United States
Dave has been programming for the past 20+ years first on a variety of platforms and operating systems using various languages. As a hobbyist Dave cut his teeth on the Commodore Pet and the 64 coding in basic and then moving to 6502 ASM. Dave moved to the Amiga using 68000 ASM and then C. His knowledge of the C language offered the stepping stone for him to make his hobby his profession taking a position coding C on an AIX Unix platform. Since then he has worked on many flavors of Unix, QNX, Windows (3.11 – present), and has been coding games for his Pocket PC in his spare time.

Dave lives in Indiana with his two teenage daughters and two cats.

Comments and Discussions

 
GeneralMy vote of 4 Pin
eddie.breeveld7-Feb-11 0:40
Membereddie.breeveld7-Feb-11 0:40 
GeneralEliminating distributional bias [modified] Pin
Max Topley8-May-07 10:54
MemberMax Topley8-May-07 10:54 
GeneralCoding (Games, Applications) For The Pocket PC/Palm OS Pin
BlitzPackage10-Oct-06 6:54
MemberBlitzPackage10-Oct-06 6:54 
GeneralSame Initialization Pin
RahulOP10-Jan-06 19:34
MemberRahulOP10-Jan-06 19:34 
GeneralRe: Same Initialization Pin
grebulon14-Jan-06 23:13
Membergrebulon14-Jan-06 23:13 
GeneralOne optimization Pin
Filip Strugar14-Jun-05 8:06
MemberFilip Strugar14-Jun-05 8:06 
General1 million dollars... Pin
Dave Loeser27-Sep-03 21:23
MemberDave Loeser27-Sep-03 21:23 
QuestionCan it be extended for Float / Double Pin
Richard French27-Feb-03 4:35
MemberRichard French27-Feb-03 4:35 
AnswerRe: Can it be extended for Float / Double Pin
Dave Loeser27-Feb-03 4:49
MemberDave Loeser27-Feb-03 4:49 
GeneralRe: Can it be extended for Float / Double Pin
Trevor Misfeldt1-Apr-03 10:25
MemberTrevor Misfeldt1-Apr-03 10:25 
GeneralRe: Can it be extended for Float / Double Pin
WoR25-Oct-05 4:58
MemberWoR25-Oct-05 4:58 
AnswerRe: Can it be extended for Float / Double Pin
Dave Loeser1-Oct-03 9:39
MemberDave Loeser1-Oct-03 9:39 
QuestionFaster? Pin
Anonymous20-Feb-03 12:04
MemberAnonymous20-Feb-03 12:04 
AnswerRe: Faster? Pin
Dave Loeser4-Jun-03 10:34
MemberDave Loeser4-Jun-03 10:34 
GeneralRe: Faster? Pin
David Crow21-Oct-04 7:45
MemberDavid Crow21-Oct-04 7:45 
AnswerRe: Faster? Pin
edesilva1-Nov-04 5:08
Memberedesilva1-Nov-04 5:08 
I recently stumbled across this site while doing some research on PRNG's and CPU Timers...

I had already implemented the timer from the following article into a timing class as part of my toolkit.

How to get timings as fine-grained as one nanosecond or better By Mark VanTassel
http://www.codeproject.com/datetime/NanoSecondTimer.asp

I also now have a modified version of the CRandomMT class which is setup to compile as either inline functions or non inline functions depending on an appropriate #define being set.

My version is also setup behind the scenes for 32 bit operations - eg instead of returning int all appropriate functions return ULONG and use ULONG where appropriate for internal variables (non loop variables).

Interestingly enough I did a run of timing tests on the inline and non inline functions...

basically the test covered 3 different styles of functions

get32bit() returns a single unsigned 32 bit number and is just a wrapper that returns (RandomMax(0xFFFFFFFF)).

D6(x) the classes original inline (and I added an identical non inline version) D6(int) routine.

FastD6(x) my modified D6(int) routine

As D6() is basically a wrapper around the RollDice Routine I wrote a modified version called FastDiceRoll and a wrapper to it called FastD6().

This does not actually loop the dice rolls, instead it sets the call to RandomRange so that RandomRange will return a value between number_of_dice and (face * number_of_dice) hence it is quite fast for more than 1 dice but not really the same as simulating each dice roll in a statistical sense.
<br />
inline int CRandomMT::FastRollDice(int face, int number_of_dice)<br />
{ return (((int)RandomRange(number_of_dice, (face * number_of_dice)))); }


I ran the test executable 10 times for each build then averaged the results.

In one build the library only uses inline functions and the other build the library uses no inline functions.

Each build test comprised of 100,000,000 calls to each of the functions being tested.

I will summarize the averages of each build test here...

Inline Functions Build Test Summary
get32bit() 34.00352406 average CPU Cycles per call

D6(1) 17.38749114 average CPU Cycles per call

FastD6(1) 16.77318784 average CPU Cycles per call

D6(10) 181.48215873 average CPU Cycles per call (expected around this as it is processing the loop 10 times)

FastD6(10) 16.74351271 average CPU Cycles per call


Non Inline Functions Build Test Summary
get32bit() 80.23092784 average CPU Cycles per call

D6(1) 102.848867 average CPU Cycles per call

FastD6(1) 93.01914954 average CPU Cycles per call

D6(10) 879.7773479 average CPU Cycles per call

FastD6(10) 96.72102957 average CPU Cycles per call


Both versions of the library were built as Release builds with Optimised for Speed turned on.
The compiler I used is Visual C++ 6.0 SP5 with Processor Pack Installed.

The inline version of the library I built was around 2Kb and the non inline version was around 14Kb

Also note that the timer routine is not defined as inline.

Based on these CPU Cycle timings, on a 900 Mhz machine, in 1 second you should be able to create approx 50,000,000 single D6(1) calls using the inline functions and 9,000,000 D6(1) calls using non inline functions.
GeneralNegative return values... Pin
mgearman13-Nov-02 11:02
Membermgearman13-Nov-02 11:02 
GeneralRe: Negative return values... Pin
Dave Loeser3-Dec-02 4:06
MemberDave Loeser3-Dec-02 4:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 21 Oct 2002

Stats

126K views
1.6K downloads
53 bookmarked