Java generating “random” numbers that don't re

Question

Basically I want to generate random numbers that won't ever repeat for a very long period (I don't want to use a sequence) like for example the LCG that java uses:

 synchronized protected int next(int bits) {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return (int)(seed >>> (48 - bits));
 }

As I understand the seed in this case will only repeat after 2^48 calls to next is this correct?

so it is my understand that if I did a method like:

 synchronized protected long next() {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return seed;
 }

The seed value is guaranteed not to repeat before 2^48 calls?

Answer 1

Not for that LCG, since you are modding out by 2^48 each time you call it (and thus the period/state is at most 2^48 in length). If you want a better random number generator, you could try the Mersenne twister:

http://en.wikipedia.org/wiki/Mersenne_twister

The standard MT19937 has a period of 2^19937-1 (!!!) That should be more than you will ever need.

Answer 2

You can use Collection.shuffle() for that might be Performance issue..

ArrayList<Integer> number = new ArrayList<Integer>();
        for (int i = 0; i < array.size(); ++i) 
            number.add(i);
        Collections.shuffle(number);

Answer 3

For reference, the parameters for the linear congruential generator implemented in java.util.Random are as follows:

a = 25214903917 = 7 x 443 x 739 x 11003
c = 11
m = 2⁴⁸
a – 1 = 25214903916

The period length is at most m if and only if all of the following are true:

1. ✔ c and m and are relatively prime

2. ✔ a – 1 is divisible by all prime factors of m

3. ✔ a – 1 is a multiple of 4 if m is a multiple of 4

Yes, the period is 2⁴⁸. The problem is "that the low order bits go through very short cycles." The strong correlation between the low order bits of successive values significantly limits what you can do with them.

Answer 4

You could use SecureRandom as a drop in replacement from random. It doesn't repeat as quickly as Random does.