How good is java.util.Random?

Tags: java random
By : Dove
Source: Stackoverflow.com
Question!

Two Questions:

Will I get different sequences of numbers for every seed I put into it?

Are there some "dead" seeds? (Ones that produce zeros or repeat very quickly.)

By the way, which, if any, other PRNGs should I use?

Solution: Since, I'm going to be using the PRNG to make a game, I don't need it to be cryptographically secure. I'm going with the Mersenne Twister, both for it's speed and huge period.

By : Dove


Answers

To some extent, random number generators are horses for courses. The Random class implements an LCG with reasonably chosen parameters. But it still exhibits the following features:

If these things don't matter to you, then Random has the redeeming feature of being provided as part of the JDK. It's good enough for things like casual games (but not ones where money is involved). There are no weak seeds as such.

Another alternative which is the XORShift generator, which can be implemented in Java as follows:

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

For some very cheap operations, this has a period of 2^64-1 (zero is not permitted), and is simple enough to be inlined when you're generating values repeatedly. Various shift values are possible: see George Marsaglia's paper on XORShift Generators for more details. You can consider bits in the numbers generated as being equally random. One main weakness is that occasionally it will get into a "rut" where not many bits are set in the number, and then it takes a few generations to get out of this rut.

Other possibilities are:

  • combine different generators (e.g. feed the output from an XORShift generator into an LCG, then add the result to the output of an XORShift generator with different parameters): this generally allows the weaknesses of the different methods to be "smoothed out", and can give a longer period if the periods of the combined generators are carefully chosen
  • add a "lag" (to give a longer period): essentially, where a generator would normally transform the last number generated, store a "history buffer" and transform, say, the (n-1023)th.

I would say avoid generators that use a stupid amount of memory to give you a period longer than you really need (some have a period greater than the number of atoms in the universe-- you really don't usually need that). And note that "long period" doesn't necessarily mean "high quality generator" (though 2^48 is still a little bit low!).



See the answer in my blog post:

http://code-o-matic.blogspot.com/2010/12/how-long-is-period-of-random-numbers.html

Random has a maximal period for its state (a long, i.e. 2^64 period). This can be directly generalized to 2^k - invest as many state bits as you want, and you get the maximal period. 2Mersenne Twister has actually a very short period, comparatively (see the comments in said blog post).

--Oops. Random restricts itself to 48bits, instead of using the full 64 bits of a long, so correspondingly, its period is 2^48 after all, not 2^64.



If RNG quality really matters to you, I'd recommend using your own RNG. Maybe java.util.Random is just great, in this version, on your operating system, etc. It probably is. But that could change. It's happened before that a library writer made things worse in a later version.

It's very simple to write your own, and then you know exactly what's going on. It won't change on upgrade, etc. Here's a generator you could port to Java in 10 minutes. And if you start writing in some new language a week from now, you can port it again.

If you don't implement your own, you can grab code for a well-known RNG from a reputable source and use it in your projects. Then nobody will change your generator out from under you.

(I'm not advocating that people come up with their own algorithms, only their own implementation. Most people, myself included, have no business developing their own algorithm. It's easy to write a bad generator that you think is wonderful. That's why people need to ask questions like this one, wondering how good the library generator is. The algorithm in the generator I referenced has been through the ringer of much peer review.)



This video can help you solving your question :)
By: admin