How good is java.util.Random?

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.

Answer 1

This is described in the documentation. Linear congruential generators are theoretically well-understood and a lot of material on them is available in literature and on the internet. Linear congruential generator with same parameters always outputs the same periodic sequence, and the only thing that seed decides is where the sequence begins. So the answer to your first question is "yes, if you generate enough random numbers."

Answer 2

As zvrba said, that JavaDoc explains the normal implementation. The Wikipedia page on pseudo-random number generators has a fair amount of information and mentions the Mersenne twister, which is not deemed cryptographically secure, but is very fast and has various implementations in Java. (The last link has two implementations - there are others available, I believe.)

If you need cryptographically secure generation, read the Wikipedia page - there are various options available.

Answer 3

As RNGs go, Sun's implementation is definitely not state-of-theart, but's good enough for most purposes. If you need random numbers for cryptography purposes, there's java.security.SecureRandom, if you just want something faster and better than java.util.random, it's easy to find Java implementations of the Mersenne Twister on the net.

Answer 4

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.)

Answer 5

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:

• fairly short period (2^48)
• bits are not equally random (see my article on randomness of bit positions)
• will only generate a small fraction of combinations of values (the famous problem of "falling in the planes")

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 it simple enough to be inlined when you're generating repeatd values. 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 equally random. The 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!).

Answer 6

A tad off topic but when you look at the Java Doc for the class and it says "The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)", you know it has to be good.