Add your own alternative version
Stats
367.8K views 13.7K downloads 163 bookmarked
Posted
11 Apr 2008

Comments and Discussions



Glad to hear about Marsaglia's generator.





exactly what I am looking for! Thanks






I use this in my C# projects and now writing Java for Android. Blasted Java doesn't support unsigned types and this uses unsigned ints.
This seems simpler than other implementations of Marsaglia so I'd really like a port of this to Java (long/int). A bit over my head to be certain it's done right.
Any help from the author? Thanks...





Hello,
I'm generating in sequential form a random sequence of numbers and i'm timing the operation; I'm generating with Parallel.For, Invoke and Task.Factory.StartNew but the sequential is faster than the other ... Can the marsaglia algorithm be parallelized?
The generation of the sequence can be faster in parallel form?
Could someone suggest a method of generation ?
Thank you in advance,
Daniel
ParallelOptions options = new ParallelOptions();
options.MaxDegreeOfParallelism = 3;
counter.Reset();
counter.Start();
Parallel.For(0, n,options,i => vect[i] = GetUint());
counter.Stop();
Console.WriteLine("Generarea a durat pentru Parallel.For: {0}", counter.Elapsed);
counter.Reset();
counter.Start();
for (int i = 0; i < n; i++)
{
Parallel.Invoke(options,()=>
{
vect[i] = GetUint();
}
);
}
counter.Stop();
Console.WriteLine("Generarea a durat pentru Invoke: {0}", counter.Elapsed);
counter.Reset();
counter.Start();
for (int i = 0; i < n; i++)
Task.Factory.StartNew(() => { vect[i] = GetUint(); });
counter.Stop();
Console.WriteLine("Generarea a durat pentru Task.Factory.StartNew: {0}", counter.Elapsed);





Hello,
I am using Parallel.For , Invoke and Task.Factory.StartNew to generate the numbers in parallel but all three methods are less efficient than the sequential for. Do you think i am doing something wrong? all three methods do the same operation vect[i] = GetUint();
Is marsaglia parallelizable? And where ?
Thank you in advance!
Daniel
PS: I can post the code on demand.





Is there a way to somehow reset the RNG? Such that the following is possible.
SimpleRNG.SetSeed(seed);
double i = SimpleRNG.GetUniform();
SimpleRNG.reset();
SimpleRNG.SetSeed(seed);
double j = SimpleRNG.GetUniform();
Assert(i == j);





Solved the issue by changing SimpleRNG to nonstatic implementation.






Great one!
Using the MWC for a while now and loving it  your article is great in explaining it and provides some excellent source code with the different distributions. Have my 5!





http://www.bobwheeler.com/statistics/Password/MarsagliaPost.txt
Above post has the code:
#define znew ((z=36969*(z&65535)+(z>>16))<<16)
#define wnew ((w=18000*(w&65535)+(w>>16))&65535)
#define MWC (znew+wnew)
and 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;
}
You are missing the &65535 andoperation? Is this on purpose or by mistake?
Additional links: Wikipages has the two versions, suggesting that probably the version without &65535 is the right one.
modified 13Aug12 16:22pm.





I've noticed this too, the correct code would be this:
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));





But in this archive Marsaglia himself states:
"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."
http://mathforum.org/kb/message.jspa?messageID=1524861[^]





Sorry, my mistake, the second ")" changes everything. This comment is completely wrong:
Member 8551910 wrote: +(w>>16))&65535) That seems kind of dumb. (w>>16) shifts the leftmost 16 bits of a 32 bit number into the rightmost 16 bits. "And"ing that with 65535 is "and"ing it with 16 ones in the rightmost 16 bits, so it remains unchanged. The bug looks to me to be in your referenced link.
modified 29Jun14 5:36am.






I converted SimpleRNG to VB. The first time through GetUint() I get an Overflow exception from this statement:
m_z = 36969 * (m_z & 65535) + (m_z >> 16)
When I step through the code in C# it works just fine.
The environment is VS2008 and .NET 3.5
Any ideas?





There is a significant and functional difference between And and & which the converter I used doesn't seem to handle very well.
I don't seem to have checked the output very well, either.
Sorry to have bothered you.





Just did a quick port to C++  have a little project in mind, and this might be just the thing, thanks.
I know I should google it, just wondering if the KS test result here looks reasonable  I was scratching my head a bit on the inits of K_plus and K_minus and their output:
Testing the random number distributionusing the KolmogorovSmirnov (KS) test.
K+ statistic: 0.405208
K statistic: 0.596502
Acceptable interval: [ 0.00591058, 2.03115 ]
K+ max at 391 0.379186
K max at 539 0.557863
KS test passed
Testing gamma
Expected mean: 20 computed mean: 20.0289
Expected variance: 40 computed variance: 39.8337
Testing normal
Expected mean: 2 computed mean: 1.9709
Expected variance: 25 computed variance: 24.9908
Testing Student t
Expected mean: 0 computed mean: 0.000852398
Expected variance: 1.5 computed variance: 1.49278
Testing Weibull
Expected mean: 2.65868 computed mean: 2.66205
Expected variance: 1.93142 computed variance: 1.93547
Testing Beta
Expected mean: 0.777778 computed mean: 0.777622
Expected variance: 0.017284 computed variance: 0.0172395
Happy to pass along what I have  thanks again, nice stuff (er, though a tad over my head )
Cheers
Tim





The KS test looks mysterious, but as long as the K and K+ values are inside the "acceptable interval," there's no reason to be suspicious. They may occasionally fall outside the interval, but unless that keeps happening with several seeds then you're probably OK. In this case 0.405208 and 0.596502 fit inside, larger than 0.00591058 and smaller than 2.03115.





Thanks  just did a test with numReps = 10000000  surprisingly quick, KS test reported in well under a minute on a P4 at 2.8Ghz (dual core I think, though not sure how much that helps), and that's most probably the std::list push_back operations taking up the time [edit: and the sort]. (I used a bit of STL in the test harness, leaving the SimpleRNG class to the basic C runtime for the math ops etc.)
Still might be a bit of tweaking for the exception code  not formatting the params yet.
The little project involves some bitmap manipulation, so speed is good.
Thanks again,
Tim





You should explain about bad seeds for this generator.
The most basic one is: if you initialise either w or z component of the generator with 0, it will be stuck on 0 (making that component of the generator useless).
But also if you initialise the w component with 0x464FFFFF, 0x8C9FFFFE, or 0xD2EFFFFD, it will get "stuck" forever on a same value output. Similarly for a value of 0x9068FFFF for the z component.





Bravo for the comment!
Just because you can do it in 3 lines of code, and result looks ok to eye, doesn't mean the algorithm is good...
I would never use SimpleRNG in any securitybased code as its next values are possibly predictable and even the bad seeds can destroy the main purpose: generating random values.
For any other case, I really don't see why I would use any "lightweight random generator".





Hi, just a note to say that it seems the single parameter constructor: Public Shared Sub SetSeed(u As UInteger) is proving to result in the more "usefully random" results for me when using the GetUniform() function.
When calling the seed constructor with dual parameters, it seems the second value has only a very small affect on the variation of the result.
SetSeed(1, 1); GetUniform = 0.564106363773296;
SetSeed(2, 1); GetUniform = 0.56411055472488;
SetSeed(3, 1); GetUniform = 0.564114745676464;
SetSeed(4, 1); GetUniform = 0.564118936628048;
SetSeed(5, 1); GetUniform = 0.564123127579632;
SetSeed(1, 2); GetUniform = 0.12820853682784;
SetSeed(2, 2); GetUniform = 0.128212727779423;
SetSeed(3, 2); GetUniform = 0.128216918731007;
SetSeed(4, 2); GetUniform = 0.128221109682591;
SetSeed(5, 2); GetUniform = 0.128225300634175;
SetSeed(1, 3); GetUniform = 0.692310709416722;
SetSeed(2, 3); GetUniform = 0.692314900368305;
SetSeed(3, 3); GetUniform = 0.692319091319889;
SetSeed(4, 3); GetUniform = 0.692323282271473;
SetSeed(5, 3); GetUniform = 0.692327473223057;
I was thinking that any unique combination of parameters would result in a significantly random output. Am I misunderstanding the intention of the second param?
Thanks in advance for help





If you run these sequences further, not just generating one sample, I believe you'll see them diverge.





Hello, thanks for the article and code; my apologies, I am new to pseudo random number generators and Mathematics is a weak point of mine, but I have a question:
I would like to know up front the point the sequence repeats, I believe this is called the period, so that I can "wrap" around some dynamically generated game content.
Is this even possible to determine?







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.

