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?

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

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

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

Comments

[flight]

This is a bit general and also a bit ill defined. "The complexity of generating a random number." Doesn't that sound a bit dodgy to you?

[President James K. Polk]

It takes one JVM integer multiply, one JVM add, and one JVM divide per number generated. The analysis was performed by combining directed neuronal activation together with reading the code.

[DaveFar]

Hm, are there any real random number generators in Java? I guess you would have to use some hardware and physical phenomenon (and believe in god playing dice).

[harold]

Not that I know of.. but I expect that there is at least one java library floating around that uses the entropy from HKLM\SOFTWARE\Microsoft\Cryptography\RNG\Seed on windows or /dev/random elsewhere