?? mersennetwisterclass.html
字號:
<!--------------------------------------------------------------------------->
<!-- INTRODUCTION
The Code Project article submission template (HTML version)
Using this template will help us post your article sooner. To use, just
follow the 3 easy steps below:
1. Fill in the article description details
2. Add links to your images and downloads
3. Include the main article text
That's all there is to it! All formatting will be done by our submission
scripts and style sheets.
-->
<!--------------------------------------------------------------------------->
<!-- IGNORE THIS SECTION -->
<html>
<head>
<title>The Code Project</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<Style>
BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
H2 { font-size: 13pt; }
H3 { font-size: 12pt; }
H4 { font-size: 10pt; color: black; }
PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
</style>
<link rel="stylesheet" type=text/css href="http://www.codeproject.com/styles/global.css">
</head>
<body bgcolor="#FFFFFF" color=#000000>
<!--------------------------------------------------------------------------->
<!------------------------------- STEP 1 --------------------------->
<!-- Fill in the details (CodeProject will reformat this section for you) -->
<pre>
Title: The Mersenne Twister in C++
Author: Dave Loeser
Email: dave@elysianonline.com
Environment: VC++ 6.0, WinNT, W2K, WXP
Keywords: PRNG, Random, Mersenne Twister, Mersenne, Twister
Level: Intermediate
Description: A C++ class that wraps up the Mersenne Twister (PRNG).
Section C++ / MFC
SubSection General
</pre>
<hr width=100% noshade>
<!------------------------------- STEP 2 --------------------------->
<!-- Include download and sample image information. -->
<ul class=download>
<li><a href="Article_demo.zip">Download demo project - XXX Kb </a></li>
<li><a href="Article_src.zip">Download source - XXX Kb</a></li>
</ul>
<p><img src="Article.gif" alt="Sample Image" width=100 height=100></p>
<!------------------------------- STEP 3 --------------------------->
<!-- Add the article text. Please use simple formatting (<h2>, <p> etc) -->
<h2>Introduction</h2>
<p>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:
<UL>
<LI>It is designed with consideration on the flaws of various existing generators.</LI>
<LI>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.)</LI>
<LI>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.)</LI>
<LI>Efficient use of the memory. <!--(The implemented C-code mt19937.c consumes only 624 words of working area.)--></LI>
</UL>
<h3>Credit where it's due</h3>
I present a C++ class (<code>CRandomMT</code>) 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.
</p>
<p>
<h2>CRandomMT</h2>
<h3>Inspiration</h3>
In 2000 I was working on a random dungeon generator for a Roguelike and I asked the folks on
<A HREF="news://rec.games.roguelike.development">rec.games.roguelike.development</A> 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 <i>wrap</i> the code. I mean, that is what us C++ guys do... right?
</p>
<p>
<h3>Perspiration</h3>
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.
</p><p>
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: <br><b><number of dice>d<size of die></b>
so, to roll 2 six sided dice you would write <b>2d6</b>. 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: <br> <b>d<size of die><number of dice></b> I could easily create methods
that described the intentions of the code by creating methods such as <code>CRandomMT::D6(int _DiceCount)</code>
and <code>CRandomMT::D25(int _DiceCount)</code>. Ironically, these were merely wrappers around the method:
<code>CRandomMT::RollDice(int _DieSize, int _DiceCount)</code>.
</p>
<p>
<h3>Completion</h3>
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?
</p>
<!--
<pre>
//
// Any source code blocks look like this
//
</pre>
<p>More article text...</p>
-->
<h2>Class Description</h2>
<p>
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.</p>
<p>
<code>CRandomMT::CRandomMT()</code><br>
This is the default CTOR.</p>
<p>
<code>CRandomMT::CRandomMT(ULONG seed)</code><br>
A constructor that you provide the seed value.</p>
<p>
<code>CRandomMT::~CRandomMT()</code><br>
The DTOR.</p>
<p>
<code>CRandomMT::SeedMT()</code><br>
Used to seed or re-seed the random number generator.</p>
<p>
<code>ULONG CRandomMT::RandomMT()</code><br>
Returns a unsigned long random number.</p>
<p>
<code>int CRandomMT::RandomRange(int hi, int lo)</code><br>
Returns an int random number falling in the range specified.</p>
<p>
<code>int RollDice(int face, int number_of_dice)</code><br>
Returns an int random number for the number of dice specified and the face of the die.</p>
<p>
<code>int CRandomMT::D<i>#</i>(int die_count)</code><br>
Returns a simulated roll of the number of dice specified for the die (determined by #). These
are just wrappers around <code>RollDice()</code></p>
<p>
<code>int CRandomMT::HeadsOrTails()</code><br>
Returns 0 or 1, used to simulate a coin flip.</p>
<h2>Example Usage</h2>
<pre>
#include "Random.h"
.
.
.
CRandomMT MTrand(GetTickCount());
int rand_3d6 = MTrand.D6(3); // roll 3 six sided die
.
.
.
</pre>
<h2>About the demo application</h2>
<p>
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 <code>CProgressCtrl</code> and a couple static controls
for the textual display.
</p>
<div align=center>
<B>NuMega TrueTime Statistics</B> *<br>
CRandomMT::RandomMT() not inlined
<TABLE BORDER=1 WIDTH=580>
<TR><TH>Function</TH><TH>% in function</TH><TH>Called</TH><TH>Avgerage</TH><TR>
<TR><TD>rand()</TD><TD>23.88</TD><TD>100,000</TD><TD>0.73</TD></TR>
<TR><TD>FlipRand()</TD><TD>13.76</TD><TD>1</TD><TD>41,864.76</TD></TR>
<TR><TD>CRandomMT::RandomMT()</TD><TD>19.83</TD><TD>100,000</TD><TD>0.60</TD></TR>
<TR><TD>FlipMersenne()</TD><TD>13.60</TD><TD>1</TD><TD>41,378.81</TD></TR>
</TABLE>
</div>
<br>
<div align=center>
<B>NuMega TrueTime Statistics</B> *<br>
CRandomMT::RandomMT() inlined
<TABLE BORDER=1 WIDTH=580>
<TR><TH>Function</TH><TH>% in function</TH><TH>Called</TH><TH>Avgerage</TH><TR>
<TR><TD>rand()</TD><TD>31.76</TD><TD>100,000</TD><TD>0.72</TD></TR>
<TR><TD>FlipRand()</TD><TD>18.22</TD><TD>1</TD><TD>41,507.23</TD></TR>
<TR><TD>CRandomMT::RandomMT()</TD><TD COLSPAN=3>INLINED</TD></TR>
<TR><TD>FlipMersenne()</TD><TD>10.88</TD><TD>1</TD><TD>26,168.42</TD></TR>
</TABLE>
</div>
<UL><B>*</B>
<LI><b>% in function</b>: Time spent on this line and the functions it called as a percentage of the time spent in the entire function.</LI>
<LI><b>Called</b>: Number of times the function was called.</LI>
<LI><b>Average</b>: Average execution time of the function during the session.</LI>
</UL>
<h3>Faster?</h3>
<p>
In the speed category it is clear that the MT algorithm is much faster.
The difference is that <code>FlipMersenne()</code> in the inlined version averaged 26,168.42 -vs- the
41,507.23 of <code>FlipRand()</code> 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.
<p>
<h3>Equidistribution?</h3>
<p>
The probability of a coin flip being heads or tails is expressed using the the mathmatical formula
<tt>1/n</tt>. 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 <code>rand()</code> provided very good results based on a
50/50 assumption.
</p>
<p>
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:
</p>
<div ALIGN=center>
<B>Mersenne Twister</B>
<TABLE BORDER=1 WIDTH=580>
<TR><TD><B>FLIP(s)</B></TD><TD>1</TD><TD>2</TD><TD>3</TD><TD>4</TD><TD>5</TD><TD>6</TD><TD>7</TD><TD>8</TD><TD>9</TD><TD>10</TD><TD><B>AVG %</B></TD></TR>
<TR><TD><B>HEADS</B></TD><TD>50006</TD><TD>49910</TD><TD>49883</TD><TD>49673</TD><TD>49962</TD><TD>50073</TD><TD>49965</TD><TD>49768</TD><TD>50105</TD><TD>50116</TD><TD><B>49.946</B></TD></TR>
<TR><TD><B>TAILS</B></TD><TD>49994</TD><TD>50090</TD><TD>50117</TD><TD>50327</TD><TD>50038</TD><TD>49927</TD><TD>50035</TD><TD>50232</TD><TD>49895</TD><TD>49884</TD><TD><B>50.054</B></TD></TR>
</TABLE>
</div>
<div ALIGN=center>
<B>rand()</B>
<TABLE BORDER=1 WIDTH=580>
<TR><TD><B>FLIP(s)</B></TD><TD>1</TD><TD>2</TD><TD>3</TD><TD>4</TD><TD>5</TD><TD>6</TD><TD>7</TD><TD>8</TD><TD>9</TD><TD>10</TD><TD><B>AVG %</B></TD></TR>
<TR><TD><B>HEADS</B></TD><TD>49998</TD><TD>50091</TD><TD>49907</TD><TD>50106</TD><TD>50144</TD><TD>50097</TD><TD>49919</TD><TD>49888</TD><TD>50073</TD><TD>49847</TD><TD><B>50.007</B></TD></TR>
<TR><TD><B>TAILS</B></TD><TD>50002</TD><TD>49909</TD><TD>50093</TD><TD>49894</TD><TD>49856</TD><TD>49903</TD><TD>50081</TD><TD>50112</TD><TD>49927</TD><TD>50153</TD><TD><B>49.993</B></TD></TR>
</TABLE>
</div>
<p>
The above results for <code>rand()</code>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.
</p>
<h2>Conclussion</h2>
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).
<h2>Thanks</h2>
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.
<h2>References</h2>
<UL>
<LI>[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.</LI>
<LI><A HREF="http://www.math.keio.ac.jp/~matumoto/emt.html">[2] Mersenne Twister: A random number generator</A>, www.math.keio.ac.jp/~matumoto/emt.html</LI>
<h2>Links</h2>
<LI><A HREF="http://www.compuware.com">Compuware Corporation</A> The makers of TrueTime
</UL>
</UL>
<!------------------------------- That's it! --------------------------->
</body>
</html>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -