<!--------------------------------------------------------------------------->
<!-- 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: Article Title Goes Here
Author: Author Name
Email: author@email.com
Environment: VC++ 5.0-6.0, NT 4.0, Win95/98
Keywords: Control, Dialog, MFC
Level: Intermediate"
Description: An article on something-or-other
Section Miscellaneous
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>
<img src="zigurat.png" width=500 height=280>
<h2>Introduction</h3>
<h3>Random Variable Generator</h3>
<p>This article present a fast generator for Random Variable, namely normal and exponential distributions.
The algorithm is due to George Marsaglia and Wai Wan Tsang in [1]. Here's the abstract of their paper:</p>
<p><em>We provide a new version of our ziggurat method for generating a random variable from a given
decreasing density. It is faster and simpler than the original, and will produce, for example, normal
or exponential variates at the rate of <b>15 million per second with a C version on a 400MHz PC</b>. It
uses two tables, integers ki and reals wi. Some 99% of the time, the required x is produced by:
Generate a random 32-bit integer j and let i be the index formed from the rightmost 8 bits of j. If
j < ki return x = j . wi.
</em></p>
<p>They did 99,9% of the work, I just encapsulated their C code in a class wrapper.</p>
<h3>Histogram</h3>
<p>In order to illustrate the generator, I've coded a Histogram class, <code>CHistogram</code>.</p>
<h2>A little bit of mathematical background</h2>
<p>The normal distribution holds an honored role in probability and statistics, mostly because of the central limit theorem,
one of the fundamental theorems that forms a bridge between the two subjects.</p>
<p>The normal distribution is also called the <em>Gaussian distribution</em>, in honor of Carl Friedrich Gauss,
who was among the first to use the distribution.</p>
<p>There are plenty tutorials and demo applets on normal distributions on the web so I won't go into mathematical details here.
A very nice web site on this topic can be found at
<a href="http://www.math.uah.edu/stat/index.html">Virtual Laboratories in Probability and Statistics</a></p>
<p>The algorithm used to compute the mean, variance and other statistical stuff are taken from the numerical recipies (see [2]).</p>
<h2>Using the generator</h2>
<p>The <code>CRandomGenerator</code> provides two types of randow variables: normal and exponential. These
are computed by 2 static functions, RNOR and REXP:</p>
<ul>
<li>normal variable:
<pre>
float var = CRandomGenerator::RNOR();
</pre>
<li>exponential variable:
<pre>
float var = CRandomGenerator::REXP();
</pre>
</ul>
<h2>Initializing the generator</h2>
<p>Like any random generator, it has to be initiliazed with a "seed". Classicaly, one uses the current time to
seed the generator. This is done implicitely in the default constructor of <code>CRandomGenerator</code>, so
what you have to do is to build <b>one and only one</b> <code>CRandomGenerator</code> object in your application
thread before using the generator. Doing that in your <code>CWinApp::InitInstance</code> function is a good idea.</p>
<pre>
CWinApp::InitInstance
{
...
// build a CRandomGenerator to seed the generator
CRandomGenerator randn;
}
</pre>
<h2>Using the histogram</h2>
<code>CHistogram</code> is a templated histogram class. The histogram is characterized by
<ul>
<li>a region, defined by a minimum and maximum spectrum value (see <code>Get/SetMinSpectrum</code>,
<code>Get/SetMaxSpectrum</code>)</li>
<li>a step size (see <code>GetStep</code>)</li>
</ul>
<img src="histogram.png" with=255 height=116>
<h3>Computing the histogram</h3>
You can feed the histogram with data by different manners:
<ul>
<li> Feeding a vector of data,
<pre>
vector< float > vData;
... // computing the data
// Creating an histogram with 101 regions
CHistogram< float > histo(101);
// Computing the histogram, min and max values are automaticaly computed...
histo.Compute( vData , true /* compute min, max */);
</pre>
</li>
<li>Updating with a vector of data,
<pre>
vector< float > vData;
...
// updating the histogram
histo.Update( vData );
</pre>
</li>
<li> Updating with a single data entry,
<pre>
float fData;
...
// updating the histogram
histo.Update( fData );
</pre>
</li>
</ul>
<h3>Retreiving results</h3>
<p>You can access the histogram results by using <code>GetHistogram</code>.
You can also get a normalized histogram by calling <code>GetNormalizedHistogram</code>.</p>
<p>The coordinates of the regions can be accessed by using <code>GetLeftContainers</code> and
<code>GetCenterContainers</code>.</p>
<p>The code to generate the plots looks like this:</p>
<pre>
vector < double > vDistribution ( histo.GetNormalizedHistogram() );
vector < double > vLeftPositions ( histo.GetLeftContainers() );
CPGLLine2D* pLine;
...
pLine->SetDatas(vLeftPositions, vDistributions);
</pre>
<h2>Demo application</h2>
<p>The demo application shows the normal and exponential distribution. It uses the Plot Graphic Library
for visualization. There is another article on the PGL <a href="http://www.codeproject.com/miscctrl/pgllib.asp">here</a>.</p>
<p><b>You will need the GDI+ binaries to make the demo application work ! (gdiplus.dll)</b></p>
<p>The source code is documented using Doxygen syntax.</p>
<h2>References</h2>
<ul>
<li>
<a href="http://www.jstatsoft.org/v05/i08/ziggurat.pdf">
[1] The Ziggurat Method for Generating Random Variables, George Marsaglia and Wai Wan Tsang,
Journal of Statistical Software, Vol 05, Issue 08.</a></li>
<li>
<a href="http://www.library.cornell.edu/nr/bookcpdf/c14-1.pdf">
[2] The Numerical recipies in C, Chapter 14.</a>
</li>
</ul>
<!------------------------------- That's it! --------------------------->
</body>
</html>
Submit an article or tip