 |
 | not 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 ?
|
|
|
|
|
|
|
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
|
|
|
|
|
| Excellent 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
|
|
|
|
|
| Good article
Donsw | 8:33 27 Jan '09 |
|
|
Good article. I will use this the next time I need one.
|
|
|
|
|
| Quality 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
|
|
|
|
|
|
|
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.
|
|
|
|
|
| Output-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
Gü
|
|
|
|
|
|
|
Good catch! You are correct. The code should have computed (u+1)/(2 + 2^32) rather than u/(1 + 2^32).
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
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
|
|
|
|
|
| I'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. 
kostas KEL
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
Thanks !
kostas KEL
|
|
|
|
|
| when both seeds are 0
Pink Li | 1:56 10 Jun '08 |
|
|
|
|
|
Good observation. This has been corrected as of 6 October 2008.
|
|
|
|
|
| why 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 ?
|
|
|
|
|
|
|
For the fun maybe? Beside that, it's probably better to turn to System.Security.Cryptography for production code.
|
|
|
|
|
|
|
just showed how easy it is to get a random number 
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
Random in c# is SUCK!
if my program run 100 in 1 millisec. the random value would just the same.
|
|
|
|
|
| I'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.
|
|
|
|
|
|
|
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."
|
|
|
|
|
|
|
I use System.Security.Cryptography.RNGCryptoServiceProvider
|
|
|
|
|
