7
$\begingroup$

I recently stumbled across an article on pseudorandom numbers in Java which mention potential weaknesses in the default algorithm, called linear congruential generator (LCG), and gives some alternatives. Among those I find Xorshift generators interesting. So I put on my researcher's hat and dove in to find more information.

It turns out that it's extremely simple to implement, and very fast at runtime, which sounds great. The question is whether or not the method is a significant improvement than the default LCG algorithm. To figure that out I read through the original paper where Marsaglia introduces the method, as well as a rather tough critique/analysis by Panneton and L'ecuyer. I cannot claim that I followed the math the whole way, so I am not sure as to whether the method is a step up from LCG or not, which brings me to my first question:

Question 1: Is Xorshift a step up from LCG based default RNG that java utilizes?

Panneton and L'ecuyer raise the point of parameter choice, and also point out that only 3-bitshifts may not be enough. I have recently dug up a bit on hash functions (here's a relevant question I asked on StackOverflow). I wonder if one could improve the 3-bitshift method by something like this?

long lhash = prime * (hash1 ^ hash2); then using (int)((lhash >> 32) ^ lhash)

As per @whuber's comment, it's tricky business to change nuts and bolts of a RNG so this might be tricky, but I would appreciate any ideas/leads on how to amend weaknesses in Xorshift RNG. Question 2: What can be done to improve the "overall performance" of Xorshift algorithm? (note that I do not mean computational performance here)

As a final note, what I want to do is to generate pseudorandom Gussians, to simulate $e^{rand}$ type numbers, where rand is a Gaussian with $N(0,\sigma)$. I am not too keen on adding a dependency just for this reason, and I also think using SecureRandom is pretty much overkill at this point.

$\endgroup$
  • 3
    $\begingroup$ Unless you truly do understand the math and are willing to undertake extensive tests of your modification, it is a poor idea to change any aspect of a pseudorandom number generator. Too much can subtly go wrong. $\endgroup$ – whuber Oct 18 '12 at 18:46
  • $\begingroup$ Any ideas on how one can go about testing such a modification? Oh and btw, any comments on the overall performance of the method? $\endgroup$ – posdef Oct 19 '12 at 11:55
  • 1
    $\begingroup$ Check out George Marsaglia's Diehard tests. $\endgroup$ – whuber Oct 19 '12 at 13:37
  • $\begingroup$ @whuber I have read the wikipedia page as well as a number of other sources. I couldn't really find more detailed information on the tests; there are many vague statements like "a certain mean" or "a certain distribution". Would you happen to know more on the tests by any chance? $\endgroup$ – posdef Oct 29 '12 at 15:03
  • 1
    $\begingroup$ Yes: I used an earlier version of Diehard a long time ago to test pseudo RNGs in Excel and ArcView (GIS software). My account of that investigation--along with a link to Diehard that (amazingly) still works--appears at quantdec.com/arcview.htm. $\endgroup$ – whuber Oct 29 '12 at 17:01
6
$\begingroup$

At http://prng.di.unimi.it/ you can find a shootout of several random number generators tested using TestU01, the modern test suite for pseudorandom number generators that replaced diehard and dieharder.

The Java LCG generator is unusable. You should avoid it like the plague. A xorshift generator is better, but still displays several statistical artifacts. Marsaglia suggested in his original paper to multiply the result of a xorshift generator by a constant to improve the statistical quality, and the result is a xorshift* generator. These are some of the fastest top-quality generators available, in particular if the period is reasonably large.

Using SecureRandom for generating a large number of random bits is extremely dangerous. After a few hundred thousands calls (or less) your application will stop (on Linux, at least) waiting for /dev/random to provide more truly random bits. It is a nightmare to debug if you don't know--the application will just hang and use 0% CPU for apparently no reason.

$\endgroup$
  • $\begingroup$ Interesting... I am going to read the paper associated with the testing and xorshift* generators. One quick question; how come the paper is not published in a journal? I'd think that a fast and efficient PRNG would be very relevant to many people out there $\endgroup$ – posdef Jan 28 '14 at 10:52
  • $\begingroup$ It was submitted two weeks ago. It takes time. :-) $\endgroup$ – seba Jan 28 '14 at 14:40
  • $\begingroup$ ah, ok... :) In our field one would not be able to post something like that publicly before it gets accepted somewhere. I was surprised to see something like that go "unpublished".. $\endgroup$ – posdef Jan 28 '14 at 18:30
  • $\begingroup$ Btw, I am a bit unsure about the $M_t$ multiplicative factor, which I asked about in a separate question: stats.stackexchange.com/questions/83849/…. Would be really nice if you could take a look at it at some point. $\endgroup$ – posdef Jan 30 '14 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.