CODEWITHSUNDEEP
javaalgorithmrandom
OckhamsRazor
OckhamsRazor

Reputation: 4906

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

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?

Upvotes: 7

Views: 16678

Answers (4)

user555045
user555045

Reputation: 64904

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.

Upvotes: 4

DaveFar
DaveFar

Reputation: 7447

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.

Upvotes: 10

pageman
pageman

Reputation: 3022

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

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533500

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.

Upvotes: 5

Related Questions