Add your own alternative version
Stats
426.3K views 15.2K downloads 169 bookmarked
Posted
11 Apr 2008

Comments and Discussions



Hi John,
Excellent article though way out of my league as far as math is concerned.
The problem I am trying to solve is to generate a random positive integer y calling the GetRandom() function x number of times using VB.net. The problem I am running into is that since the computers are so fast these days, if my x is 25 (e.g), then it generates the same number 25 times.
I don't know if it makes sense to use your solution. Might be an overkill.
Do you or any of your readers have any suggestions besides using System.Threading.thread.pause(2) so I will (hopefully) have fresh seed? Or if not, any way to port your c# library into VB.NET so I can just use it directly without compiling yours into a dll?
Thanks for your help
Kuntal





You're only meant to seed the generator once, at the start. Then you can call the GetUint() function many times, and get a different value each time.
modified 18Jun12 0:10am.





I found this to generate pretty random numbers. It's nothing fancy and I'm not sure of the statistical distribution if produces, but it works well for me.
Denny
static double GenerateRandomNumber()
{
byte[] random_bytes = new byte[4];
new RNGCryptoServiceProvider().GetBytes(random_bytes);
int random_int = BitConverter.ToInt32(random_bytes, 0);
Random random = new Random(random_int);
return random.NextDouble();
}





While trying to figure out how to generate random number for a Poisson distribution, I came across your contribution. Thank you putting together the well written article+code+test harness. So rare these days!
BTW: I am still trying to figure out how to create Poisson RNs. Any suggestions (or code snippet) would be much appreciated. Cheers!






Thank you so much. This rates a 10!





Hi John:
The GetPoisson function works nicely for me (as I have small Lamda values). But the LargePoisson function won't compile as it is looking for the LogFactorial(n) function. For the moment I've implemented the "simple/inefficient version" (just to get it to compile), but as I was intrigued by your comment "A better approach would be to use a log gamma function if one is available", I looked around your lovely clean adfree site for the LogFactorial code but couldn't find it. My math is a tad rusty (have been out of school for four decades now!), so I don't know if I can write my own; if you could point me to the better code that would be marvelous.
Cheers!
VVX





I have standalone code[^] for several functions on my web site, but not for gamma and log gamma. The standalone code collection is for welldocumented little pieces of code you can easily copy and paste. Also, I want to write them from scratch so there are no license issues, not even open source licenses.
I haven't included gamma and log gamma because their implementations are more complicated. Some day I may add these functions.





Thanks. Look forward to seeing your gamma functions.






Thanks John. Will check it out soon. Cheers!





Nice and succinct. Better if in VB





First I very much appreciate mathematical articles. Second I would really appreciate some more explanation on why GetUint works. Not obvious is definitely an understatement. Can this be extended if one needed random numbers from 1 to n where n could be gargantuan. In particular I want to generate random rational numbers and I would like to have potentially thousands or more digits in the numerator and denominator. If you have any Ideas as to how to make a good random number generator for Rational Numbers  .Net 4.0 version , it would be greatly appreciated.
Ken





If you want to understand how random number generators work, you could start with Knuth's Seminumerical Algorithms, (TAOCP volume 2).
As far as generating large random numbers, assume for a minute we had a random number generator that produced numbers 0, 1, 2, ..., 9. You could generate a random number with k digits by computing an array a[] of random digits and computing a[0] + 10*a[1] + 100*a[2] + ... + 10^(k1)*a[k1].
Now instead of working in base 10, work in base 2^32 since GetUint produces numbers between 0 and 2^32  1. For example, you could generate a 128bit random number by generating four 32bit unsigned integers a, b, c, and d and returning a + b*2^32 + c*2^64 + d*2^96.






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





return (m_z << 16) + (m_w & 65535);
The above line is not portable if m_z may be greater than 65535. I would suggest ((m_z & 65535) << 16) + (m_w & 65535).
I also find myself somewhat dubious about the fact that the upper 16 bits and lower 16 bits of the result are independent. It would seem many applications would be likely to use only the upper or lower 16 bits. I'm not sure what form of blending would be best, but I would think some form of mixing would be helpful.
Incidentally, I wonder whether simple random number generators might be improved by simply xor'ing the output with a counter indicating how many times the generator has been invoked (perhaps one that counts by some large number, mod 2^31). Such a counter by itself would be a crummy generator, but if it's orthogonal to whatever other generator is being used, it shouldn't make things any worse and might make them better (if the other generator's period isn't a power of two, such a counter would extend the period of the generator quite nicely).






See also this newsgroup post from around the same time (Random numbers for C: Improvements. Posted: Jan 15, 1999 11:41 AM), in which Marsaglia explains the difference between the two algorithms:
> In my earlier work, done in Fortran, I had implemented
> two 16bit multiplywithcarry generators, say z and w,
> as 32bit integers, with the carry in the top 16 bits,
> the output in the bottom 16. They were combined by
> (z<<16)+w. (In Fortran, ishft(z,16)+w.) Such a
> combination seemed to pass all tests. In the above
> mentioned post, I used (z<<16)+(w&65525), and that
> does not pass all tests. So (z<<16)+w seems
> preferable; it is used below, providing a MWC that
> seems to pass all tests.






Thanks. I have submitted a revised version of the article and code incorporating the correction you suggest.





Hi John:
I like your article; it's well written and very practical.
Good Job! 5*
Thanks and regards,
Alex





Good article. I will use this the next time I need one.





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 MonteCarlo 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.airspacev.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.





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.328306435454494e010;
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





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






Good observation. This has been corrected as of 6 October 2008.





you can just do this :
<br />
Random ran = new Random();<br />
double d = ran.NextDouble();<br />
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 kerosenesoaked 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.





nothing wrong if you want to eat a McDonalds FiletOFish , but some want to know a bit more about what their eating , and others want to learn how to fish for themselves ...
I arrived here six years later , curious about generating controlled distributions and found cached gold waiting to be picked up .
thank you George and J.D. !





I'll stick with what's builtin.
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 inbuilt 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





That's fine for crypto work, but what about for statistical simulations (Monte Carlo etc), here you need very fast random number generation with good statistical properties. The inbuilt Random() function looks similar to rand() from c. I haven't made any serious use of random numbers in .NET, but it is possible that this simple generator could be useful.
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."





This PRNG is only usable for monte carlo simulations. And i think it is better than rand() for this purpose, because it passes the DIEHARD tests, the build in rand() function don't!
Where are the problems in crypthography?
1. It is only 32Bit wide  no problem for a brute force attack, at least you need 128Bit, 160Bit or 256Bit is better.
2. It is guessable. If you have a number, you can guess the previous number because the algorithm has not the strength of an cryptography hash function like SHA or even MD5. If the output must be salted and hashed to masquerade, it looses it statistical distribution because of the hash function. In this case you can use a salted hash function to produce a PRN sequence like this:
salt = something real random
number = 0; // Dosn't matter because of the salt!
number = CryptoHash( number xor salt )
number = CryptoHash( number xor salt )
(replace CryptoHash with your prefered hash function like SHA)
Due to the fact that cryptographical hash functions are slow and often don't produce a perfect statistical distribution, it is not very good to use them for monte carlo simulations.
modified 4Dec14 5:56am.






You are right: no computer algorithm will produce 'truly' random numbers.
So the goal is to create a sequence of numbers that appears to be random for whatever purpose we want to use it for.
In cryptography, random means unpredictable. Given some numbers from the sequence, it is impossible to guess the next number.
In simulations, random means that the sequence is not unusual. The DIEHARD tests[^] basically run a large number of simulations and call out very improbable results.







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

