Java's random number generator. Complexity of

问题:

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?

回答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.

回答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.

回答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.

回答4:

maybe you can try Texts in Computational Complexity: Pseudorandom Generators by Oded Goldreich

"Complexity of Generation: The archetypical choice is that the generator has to work in polynomial-time (in length of its input - the seed). Other choices will be discussed as well. We note that placing no computational requirements on the generator (or, alternatively, putting very mild requirements such as a double-exponential running-time upper bound), yields "generators" that can fool any subexponential-size circuit family."