How Good Is Java.Util.Random

How good is java.util.Random?

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

Is Java's java.util.Random reliable?

Random's no-arg constructor is already based on the current time (through its cpu nanoTime and not the UTC date) so just creating it will get you a different seed every time. the seeded Random(long) version is (in my experience) mostly used when you want predictable output (some procedural generation routines for computer games, for example, allow the player to specify a random seed)

if youre very worried about how random your random numbers are, you might want to look at SecureRandom, which is recommended over plain Random for encryption and such. there's a nice explanation of how to use it here and a VERY good explanation of the difference between the two here

Is java.util.Random really that random? How can I generate 52! (factorial) possible sequences?

Selecting a random permutation requires simultaneously more and less randomness than what your question implies. Let me explain.

The bad news: need more randomness.

The fundamental flaw in your approach is that it's trying to choose between ~2²²⁶ possibilities using 64 bits of entropy (the random seed). To fairly choose between ~2²²⁶ possibilities you're going to have to find a way to generate 226 bits of entropy instead of 64.

There are several ways to generate random bits: dedicated hardware, CPU instructions, OS interfaces, online services. There is already an implicit assumption in your question that you can somehow generate 64 bits, so just do whatever you were going to do, only four times, and donate the excess bits to charity. :)

The good news: need less randomness.

Once you have those 226 random bits, the rest can be done deterministically and so the properties of java.util.Random can be made irrelevant. Here is how.

Let's say we generate all 52! permutations (bear with me) and sort them lexicographically.

To choose one of the permutations all we need is a single random integer between 0 and 52!-1. That integer is our 226 bits of entropy. We'll use it as an index into our sorted list of permutations. If the random index is uniformly distributed, not only are you guaranteed that all permutations can be chosen, they will be chosen equiprobably (which is a stronger guarantee than what the question is asking).

Now, you don't actually need to generate all those permutations. You can produce one directly, given its randomly chosen position in our hypothetical sorted list. This can be done in O(n²) time using the Lehmer^[1] code (also see numbering permutations and factoriadic number system). The n here is the size of your deck, i.e. 52.

There is a C implementation in this StackOverflow answer. There are several integer variables there that would overflow for n=52, but luckily in Java you can use java.math.BigInteger. The rest of the computations can be transcribed almost as-is:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] Not to be confused with Lehrer. :)

how does java.util.random work?

Good Question! Random Generator is not a random generator afterall! The only difference between your generation and what Random does it you return a long, while Random casts it to int.

The following change will fix it:

public static void main(String args[]){
     long multiplier = 0x5DEECE66DL;

    long addend = 0xBL;

     long mask = (1L << 48) - 1;

    long seed = 128856;
    Random random = new Random(seed);
    long n1 = random.nextInt();
    long n2 = random.nextInt();
    long n3 = random.nextInt();

    System.out.println("Results: " + n1 +" "+ n2 +" "+ n3);

    System.out.println("seed: " + seed);
    long seed0 = (seed ^ multiplier) & mask;
    System.out.println("seed0: " + seed0);

    long seed1 = ((seed0 * multiplier + addend) & mask);
    System.out.println("seed1: " + seed1);
    int v1 = (int)(seed1 >>> 16);
    System.out.println("v1: " + v1);

    long seed2 = ((seed1 * multiplier + addend) & mask);
    System.out.println("seed2: " + seed2);
    int v2 = (int)(seed2 >>> 16);
    System.out.println("v2: " + v2);
}

how random is Math.random() in java across different jvms or different machines

Math.random() is based on java.util.Random, which is based on a linear congruential generator. That means its randomness is not perfect, but good enough for most tasks, and it sounds like it should be sufficient for your task.

However, it sounds like you're using the double return value of Math.random() to choose between a fixed number of choices, which may further degrade the quality of the randomness. It would be better to use java.util.Random.nextInt() - just be sure to reuse the same Random object.

Sometimes, it doesn't appear so random by looking at a snapshot on a resource pool to see which pieces it's getting at that instant

Our brains are really good at spotting patterns in perfect randomness, so that means almost nothing.

Difference between java.util.Random and java.security.SecureRandom

The standard Oracle JDK 7 implementation uses what's called a Linear Congruential Generator to produce random values in java.util.Random.

Taken from java.util.Random source code (JDK 7u2), from a comment on the method protected int next(int bits), which is the one that generates the random values:

This is a linear congruential pseudorandom number generator, as
defined by D. H. Lehmer and described by Donald E. Knuth in
The Art of Computer Programming, Volume 3:
Seminumerical Algorithms, section 3.2.1.

Predictability of Linear Congruential Generators

Hugo Krawczyk wrote a pretty good paper about how these LCGs can be predicted ("How to predict congruential generators"). If you're lucky and interested, you may still find a free, downloadable version of it on the web. And there's plenty more research that clearly shows that you should never use an LCG for security-critical purposes. This also means that your random numbers are predictable right now, something you don't want for session IDs and the like.

How to break a Linear Congruential Generator

The assumption that an attacker would have to wait for the LCG to repeat after a full cycle is wrong. Even with an optimal cycle (the modulus m in its recurrence relation) it is very easy to predict future values in much less time than a full cycle. After all, it's just a bunch of modular equations that need to be solved, which becomes easy as soon as you have observed enough output values of the LCG.

The security doesn't improve with a "better" seed. It simply doesn't matter if you seed with a random value generated by SecureRandom or even produce the value by rolling a die several times.

An attacker will simply compute the seed from the output values observed. This takes significantly less time than 2^48 in the case of java.util.Random. Disbelievers may try out this experiment, where it is shown that you can predict future Random outputs observing only two(!) output values in time roughly 2^16. It takes not even a second on a modern computer to predict the output of your random numbers right now.

Conclusion

Replace your current code. Use SecureRandom exclusively. Then at least you will have a little guarantee that the result will be hard to predict. If you want the properties of a cryptographically secure PRNG (in your case, that's what you want), then you have to go with SecureRandom only. Being clever about changing the way it was supposed to be used will almost always result in something less secure...

Fast real valued random generator in java

If you need something fast and have access to Java8, I can recommend the java.utils SplittableRandom. It is faster (~twice as fast) and has better statistical distribution.

If you need a even faster or better algorithm I can recommend one of these specialized XorShift variants:

• XorShift128PlusRandom (faster & better)
• XorShift1024StarPhiRandom (similar speed, even longer period)

Information on these algorithms and their quality can be found in this big PRNG comparison.

I made an independent Performance comparison you can find the detailed results and the code here: github.com/tobijdc/PRNG-Performance

Futhermore Apache Commons RNG has a performance test of all their implemented algoritms

TLDR

Never use java.util.Random, use java.util.SplittableRandom.
If you need faster or better PRNG use a XorShift variant.

How Java random generator works?

They're pseudorandom numbers, meaning that for general intents and purposes, they're random enough. However they are deterministic and entirely dependent on the seed. The following code will print out the same 10 numbers twice.

Random rnd = new Random(1234);
for(int i = 0;i < 10; i++)
    System.out.println(rnd.nextInt(100));

rnd = new Random(1234);
for(int i = 0;i < 10; i++)
    System.out.println(rnd.nextInt(100));

If you can choose the seed, you can precalculate the numbers first, then reset the generator with the same seed and you'll know in advance what numbers come out.

---

Related Topics