Add your own alternative version
Stats
397.4K views 14.5K downloads 166 bookmarked
Posted
11 Apr 2008

Comments and Discussions




I think there is a bug in GetUniform method which is not caught by the tests. What happens if u = 2^32? The return statement return (u + 1) * 2.328306435454494e10; increments u by one, making u+1 == 0, thus the method return 0, I suppose (haven't tested it, though). A simple fix would be: return (u + 1.0) * 2.328306435454494e10; so that the increment operation is using doubles, not ints.





Yes, 1.0 would be better than 1. Thanks for reading carefully and finding that. As it stands, the code will return 0 when u = 2^32  1. Of course that's a rare event, but I should change the code.
Update (8 January 2011): The article and the source code have been modified to reflect this change.
modified on Saturday, January 8, 2011 10:02 AM





Excellent article, but I was wondering why all the methods are static. IMHO, this cause problems if you have a multithreaded application and you want to have more than one, yet reproducible, pseudorandom series.
Problem 1: If you have static methods and variables, you need locking or some other synchronization method. Nonstatic version allows RNG instance for each thread so they are safe to use without synchronization.
Problem 2: Even if you used synchronization with static methods, the pseudo random number series are not deterministic and reproducible because the RNG is used in nondeterministic times from different threads. There are several applications where you want to reproduce exactly the same pseudo random number for a given seed.





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.








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.

