CODEWITHSUNDEEP
javarandom
WildBill
WildBill

Reputation: 9291

Explanation of random number generator in java

Reading the wikiepedia page on Fisher-Yates shuffling the last paragraph is:

Finally, it is to be noted that even with perfect random number generation, flaws can be introduced into an implementation by improper usage of the generator. For example, suppose a Java implementation creates a new generator for each call to the shuffler, without passing constructor arguments. The generator will then be default-seeded by the language's time-of-day (System.currentTimeMillis() in the case of Java). So if two callers call the shuffler within a time-span less than the granularity of the clock (one millisecond in the case of Java), the generators they create will be identical, and (for arrays of the same length) the same permutation will be generated. This is almost certain to happen if the shuffler is called many times in rapid succession, leading to an extremely non-uniform distribution in such cases; it can also apply to independent calls from different threads. A more robust Java implementation would use a single static instance of the generator defined outside the shuffler function.

I understand everything but the last sentence in this paragraph. What does the author mean when he says:

A more robust Java implementation would use a single static instance of the generator defined outside the shuffler function.?

Upvotes: 3

Views: 4876

Answers (4)

finnw
finnw

Reputation: 48629

Part of that article is wrong:

For example, suppose a Java implementation creates a new generator for each call to the shuffler, without passing constructor arguments. The generator will then be default-seeded by the language's time-of-day (System.currentTimeMillis() in the case of Java). So if two callers call the shuffler within a time-span less than the granularity of the clock (one millisecond in the case of Java), the generators they create will be identical, and (for arrays of the same length) the same permutation will be generated.

This is not actually true. Although it is poor practice to create a new generator for each call, the Random class contains code specifically to defend against this:

 public Random() {
     this(++seedUniquifier + System.nanoTime());
 }
 private static volatile long seedUniquifier = 8682522807148012L;

Firstly the resolution is one nanosecond, not one millisecond. Creating the generator and using it once will usually take longer than a nanosecond. And secondly even when it does not, the seedUniquifier value will be different on each call.

So while it is still a bad idea to generate a new Random on each call, it is somewhat less harmful than that article suggests.

Upvotes: 4

matcauthon
matcauthon

Reputation: 2261

It means you have a single static function like this:

class RandomUtil {

    public static final Random rand = new Random();     

}

You then take this rand generator RandomUtil.rand.nextInt() to generate all your random numbers. You only use this one instance and ensure that the problems mentioned in the wiki do not occur.

Upvotes: 12

MaVRoSCy
MaVRoSCy

Reputation: 17839

To make this implementation robust and not possibly generating predictable random numbers, the generator class should be defined in a static method outside of the shuffler class. Thus no two or more objects of the generator will be created at any given time. And therefore minimizing the possibility to generate same random numbers.

Upvotes: 0

Nishant
Nishant

Reputation: 55866

Two random number generator using the same seed and same permutations are likely to give less randomness than using one generator to generate different random numbers.

Lets say you have created two default random number generators at the same instant. They use time stamp (in millis) as seed. And, will have same permutations. Now, you try to get first random from the two different generators, it's likely they will be the same.

To avoid having this situation create a public static final Random variable and use it everywhere.

Upvotes: 2

Related Questions