Take the 2-minute tour ×

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?

share|improve this question
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? –  quasiverse Sep 3 '11 at 8:04
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. –  GregS Sep 4 '11 at 11:45

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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

 synchronized protected int next(int bits) {
   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.

share|improve this answer
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). –  DaveFar Sep 3 '11 at 8:27
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 –  harold Sep 3 '11 at 8:31

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

share|improve this answer

Your Answer


