Java random number generator. The complexity of generating numbers

Question

I know that Java uses a linear congruent generator. My question is: what is the difficulty of generating a random number? How do you do these tests?

Answer 1

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

You can measure them with a micro benchmark, for example. junit-benchmark or Benentmark Brent Boyer (see a large list of such tools in What is the best tool / framework for macro benchmarking for measuring a single-threaded complex algorithm in Java? ).

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

Answer 2

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

The randomness of java.util.Random can be a problem. He uses a seed of 2 ^ 48 to repeat after these many meanings. This means that nextLong () does not generate all possible values.

If this is a problem, you can use SecureRandom, which is slower, but the point it repeats is much higher.

Answer 3

According to 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 that takes variable time, but is largely due to the fact that it deals only with fixed-length numbers.

So, the Java random number generator, which is not even a random number generator, but a pseudo random number generator, is not very good, as noted.

Answer 4

perhaps you can try Texts in computational complexity: pseudo-random generators Oded Goldreich

“ Generation complexity: The archetypal choice is that the generator should work in polynomial time (seeds are the length of its input). Other options will also be discussed. Note that the placement does not have any computational requirements for the generator (or, alternatively, presenting very soft requirements, such as double exponential current upper bound), gives "generators" that can fool any family of sub-exponential sizes. "