Java's random number generator. Complexity of generating a number

Question

I am aware that Java uses a Linear congruential generator. My question is- what is the complexity of generating a random number? How do you perform such analyses?

Answer 1

The complexity of generating a random number is O(1). Do you mean "what are its costs in terms of runtime and memory"?

You can measure them with a micro-benchmark, e.g. junit-benchmark or Brent Boyer's Benchmark (see a larg list of such tools at What is the best macro-benchmarking tool / framework to measure a single-threaded complex algorithm in Java?).

Furthermore, I think Javas random number generators are quite fast, but statistically bad. Rather use external libraries, e.g. the Mersenne Twister at http://www.cs.gmu.edu/~sean/research/, or, if runtime is so important for you, the Fast Mersenne Twister.

Answer 2

The time complexity of the random number generator is O(1). The time it takes does not increase as you have more random numbers.

The randomness of java.util.Random could be an issue. It uses a seed of 2^48 so it will repeat itself after this many values. This means nextLong() does not generate every possible value.

If this is an issue you can use SecureRandom which is slower but the point it repeats is much higher.

Answer 3

According to the docs, java.util.Random.next is implemented as follows:

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

There is nothing in there that takes a variable amount of time, but that's in a big part due to the fact that it's dealing only with fixed-length numbers.

So that's Java's random number generator, which isn't even a random number generator but a pseudo random number generator and not a very good one at that, as noted.