Click here to Skip to main content
Email Password   helpLost your password?
SimpleRNG console test program screen shot

Introduction

Random number generation is tricky business. Good random number generation algorithms are tricky to invent. Code implementing the algorithms is tricky to test. And code using random number generators is tricky to test. This article will describe SimpleRNG, a very simple random number generator. The generator uses a well-tested algorithm and is quite efficient. Because it is so simple, it is easy to drop into projects and easy to debug into.

SimpleRNG can be used to generate random unsigned integers and double values distributed uniformly, exponentially, or normally.

Why Not Just Use the .NET Random Number Generator?

For many applications, it hardly matters what random number generator you use, and the one included in the .NET runtime would be the most convenient. However, sometimes it helps to have your own random number generator. Here are some examples.

  1. When debugging, it's convenient to have full access to the random number generator. You may want to examine the internal state of the generator, and it helps if that state is small. Also, it may be helpful to change the generator temporarily, making the output predictable to help debug code that uses the generator.
  2. Sometimes it is necessary to compare the output of programs written in different languages. For example, at my work we often take prototype code that was written in R and rewrite it in C++ to make it more efficient. If both programs use their own library's random number generator, the outputs are not directly comparable. But if both programs use the same algorithm, such as the one used here, the results might be directly comparable. (The results still might not match due to other differences.)
  3. The statistical quality of the built-in generator might not be adequate for some tasks. Also, the attributes of the generator could change without notice when you apply a service pack.

Background

George Marsaglia is one of the leading experts in random number generation. He's come up with some simple algorithms that nevertheless produce high quality output. The generator presented here, SimpleRNG, uses Marsaglia's MWC (multiply with carry) algorithm. The algorithm is mysterious but very succinct. The algorithm passes Marsaglia's DIEHARD battery of tests, the acid test suite for random number generators.

The heart of SimpleRNG is three lines of code. Here is the method that generates uniformly distributed unsigned integers.

private static uint GetUint()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + (m_w & 65535);
}

Here m_w and m_z are unsigned integers, the only member variables of the class. It's not at all obvious why this code should produce quality random numbers, but it does.

The unsigned integer is then turned into a double in the open interval (0, 1). ("Open" means that the end points are not included; the method will not return 0 or 1, only numbers in between.)

public static double GetUniform()
{
    // 0 <= u <= 2^32
    uint u = GetUint();
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (u + 1) * 2.328306435454494e-10;
}

Using the Code

The SimpleRNG class has two seeds. These have default values, or they can be specified by calling SetSeed() with one or two arguments. These arguments must be non-zero; if an argument is zero, it is replaced by the default value. Some may prefer to throw an exception in this case rather than silently fix the problem. There is also an option to set the seed values from the system clock using SetSeedFromSystemTime(). Once the class is initialized, there is only one public method to call, GetUniform().

Points of Interest

The code to test SimpleRNG is more complicated than SimpleRNG itself. The test code included as a demo uses a statistical test, the Kolmogorov-Smirnov test, to confirm that the output of the generator has the expected statistical properties. If this test were applied repeatedly with ideal random input, the test would fail on average once in every thousand applications. This is highly unusual in software testing: the test should fail occasionally! That's statistics for you. Don't be alarmed if the test fails. Try again with another seed and it will most likely pass. The test is good enough to catch most coding errors since a bug would likely result in the test failing far more often.

Further Reading

For more information on random number generation, particularly on subtle things that can go wrong, see the CodeProject article Pitfalls in Random Number Generation. If you are using C++, see Random number generation using C++ TR1.

History

You must Sign In to use this message board.
 
 
Per page   
 FirstPrevNext
Generalnot the same as Marsaglia's MWC; warning about lower 16 bits.
lsemprini
23:49 14 Feb '10  
Hi,

Very nice and useful article.

The RNG in your code:

private static uint GetUint()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w;
}

is not quite the same as the RNG that Marsaglia proposed:

#define znew ((z=36969*(z&65535)+(z>>16))<<16)
#define wnew ((w=18000*(w&65535)+(w>>16))&65535)
#define MWC (znew+wnew)

because Marsaglia's code includes &65535 at the end of the definition of wnew.

So your GetUint() code will mix 16 bits of z and w in the upper 16 bits of the return value, whereas Marsaglia's code strictly appends two 16 bit values without overlapping them.

This may have a positive, negative, or no effect on the quality of the numbers for a given purpose, but anyway we should be clear that it's not the same code that Marsaglia was evaluating. However you have some amount of evaluation you did independently on your code.

One point about both pieces of code is that the lower 16 bits returned depend only on w.

So if we use either piece of code, we have to be careful not to assume that w can be predictable (for example, if an attacker can predict w but not z, we would be wrong to assume that the algorithm would still "protect" us in some way by covering up the predictability of w: the lower 16 bits returned from each call would be completely predictable).

For the same reason, a piece of code that wanted 8 random bits should probably choose them from the top 16 bits returned.

I wonder if it might be "better" in some way to return

(w ^ ( ((z&65535)<<16) | (z>>16) ) ) [assumes z is unsigned so no sign extension]

so that no matter which subset of bits you chose, they would include contributions from z and w ?
GeneralRe: not the same as Marsaglia's MWC; warning about lower 16 bits. [modified]
John D. Cook
10:29 19 Feb '10  
You are correct. Thank you for reading so carefully. I've submitted a revised version of the article and code to match Marsaglia.

Update: The current version of the article now reflects the update.
modified on Monday, February 22, 2010 1:53 PM

GeneralExcellent article!
DrABELL
13:49 16 Sep '09  
Hi John:
I like your article; it's well written and very practical.
Good Job! 5*

Thanks and regards,

Alex
GeneralGood article
Donsw
8:33 27 Jan '09  
Good article. I will use this the next time I need one.
GeneralQuality of PRNG is context dependent
Learndy
22:00 13 Oct '08  
I like small simple code very much! Especially for such artistic purpose like this. And even greater that the author gives a test suite.

However, there are several kinds of uses for pseudo random numbers. For instance Monte-Carlo simulation, noise generation, and cryptography.

Generally I would also expect an autocorrelatoin test. You take a series of generated values and autocorrelate them. You should get a peak at offset zero and more or less constant low level result at all other offsets. In this case you can use it for simulation.

To produce white noise you also have to show that the spectrum meets your requirements.

If you look at LFSR generators they pass the autocorrelation test, produce white noise and are great PRNGs frequently used for simulation and autio or even spread spectrum noise generation. However, in crypto applications they are most crackable! They have still been in use by Russians in the eightees and have been read using Sinclair ZX81 computers running a 4 MHz 8 bit CPU. Maybe they should have been read...

Anyway. I like the article and will digg into it more deeply. But be warned that quality tests for PRNGs should be application specific.

Learndy

--
Airspace V - international hangar flying!
http://www.airspace-v.com/ggadgets for tools & toys

GeneralRe: Quality of PRNG is context dependent
John D. Cook
7:49 14 Oct '08  
Thanks for your note. I agree that generators need to be tested for autocorrelation etc. The test I provided is more of a demo than a thorough test. I don't want to imply that the test included with the project is enough. I'm leaning on George Marsaglia having tested his algorithm with his DIEHARD suite of tests.

The test I included would probably catch an error in my implementation of Marsaglia's algorithm, but not a flaw in his algorithm itself.
GeneralOutput-interval
Günther M. FOIDL
3:14 4 Oct '08  
Hi,

you wrote that the interval
0 <= u <= 2^32
gets transformed to
(0, 1)
. The transformation is done by multiplying with
1 / (2^32 + 1)
.
Although
u
can be 0 the output interval should be
[0, 1)
- so 0 included while 1 is excluded.

Kind regards

GeneralRe: Output-interval
John D. Cook
4:01 4 Oct '08  
Good catch! You are correct. The code should have computed (u+1)/(2 + 2^32) rather than u/(1 + 2^32).
GeneralRe: Output-interval
Günther M. FOIDL
8:36 4 Oct '08  
Thus the code line returning the result in the GetUnitform method has to be changed to
return (u + 1) * 2.328306435454494e-010;

Note: the number slightly differs from the "old" number because (2^32 + 1) is just a little bit smaller than (2^32 + 2) -> the 2^32 part dominates.
GeneralRe: Output-interval [modified]
John D. Cook
9:41 4 Oct '08  
I've revised the code and the article. The new version was posted 6 Oct 2008.

modified on Monday, October 6, 2008 3:23 PM

GeneralI'd like some more!
KEL3
14:55 24 Aug '08  
Hello Mr. Cook.

I like your article !
Do you have any knowledge on designing RNG algorithms ?
I mean all the math theory etc...
If you do I would like to see some theory, in this or in another article.
Perhaps this site isn't the best place to write articles for math but I think some programmers interested in math may find this usefull.

Thanks. Smile

kostas KEL

GeneralRe: I'd like some more!
John D. Cook
17:27 24 Aug '08  
For an introduction to the mathematical theory, you might want to start with volume 2 of Donald Knuth's Art of Computer Programming, Seminumerical Algorithms. Also, you may be interested in another CodeProject article I wrote, "[^]Pitfalls in Random Number Generation
GeneralRe: I'd like some more!
KEL3
6:36 25 Aug '08  
Thanks ! Smile

kostas KEL

Generalwhen both seeds are 0
Pink Li
1:56 10 Jun '08  
the output is 0.
GeneralRe: when both seeds are 0
John D. Cook
10:25 6 Oct '08  
Good observation. This has been corrected as of 6 October 2008.
Generalwhy bother??
yassir hannoun
15:03 11 Apr '08  
you can just do this :
Random ran = new Random();
double d = ran.NextDouble();

and u will get a double between 0 and 1 then u can do what ever u want with it so why spnd time trying to create one ?
GeneralRe: why bother??
axelriet
16:17 11 Apr '08  
For the fun maybe? Beside that, it's probably better to turn to System.Security.Cryptography for production code.
GeneralRe: why bother??
yassir hannoun
16:28 11 Apr '08  
just showed how easy it is to get a random number Big Grin
GeneralRe: why bother?? [modified]
John D. Cook
17:02 11 Apr '08  
One reason for a custom generator is transparency. If you're trying to reproduce a problem and stepping through the code with a debugger, everything is right there in your code under your control.

Sometimes it's helpful to compare results of code written in different environments. If they all use their own library's RNG, the results aren't comparable. But, for example, you could use this code from unmanaged C++ and from C# and produce identical sequences if you start from identical seeds.

modified on Friday, April 11, 2008 10:08 PM

GeneralRe: why bother??
bfis108137
14:17 18 Jan '09  
If you want 1 random number fine but if you need hundreds or thousand that will be truly random then it's a problem. I am trying to write a statistics app and I can't seem to get random numbers.
GeneralRe: why bother??
John Simmons / outlaw programmer
4:53 1 May '08  
For one reason, the bug that was recently discovered in the random number generator used by Vista and everything that came before.

"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001

GeneralRe: why bother??
reborn_zhang
1:02 9 Dec '09  
Random in c# is SUCK!

if my program run 100 in 1 millisec. the random value would just the same.
GeneralI'll stick with what's built-in
PIEBALDconsult
14:18 11 Apr '08  
I'll stick with what's built-in.

This is one of many areas where I know Microsoft can do better than I can.
GeneralRe: I'll stick with what's built-in
cp9876
15:09 11 Apr '08  
PIEBALDconsult wrote:
This is one of many areas where I know Microsoft can do better than I can

This may be true, but others can do significantly better. You probably don't need really random numbers, but if you do, the in-built functions like rand() are not up to the task.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

GeneralRe: I'll stick with what's built-in
PIEBALDconsult
15:30 11 Apr '08  
I use System.Security.Cryptography.RNGCryptoServiceProvider


Last Updated 20 Feb 2010 | Advertise | Privacy | Terms of Use | Copyright © CodeProject, 1999-2010