Java 的随机数生成器。生成数字的复杂性
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7291911/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java's random number generator. Complexity of generating a number
提问by OckhamsRazor
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?
我知道 Java 使用线性同余生成器。我的问题是 - 生成随机数的复杂性是多少？您如何进行此类分析？
回答by DaveFar
The complexity of generating arandom number is O(1). Do you mean "what are its costs in terms of runtime and memory"?
所述生成的复杂一个随机数为O（1）。您的意思是“它在运行时和内存方面的成本是多少”？
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?).
您可以使用微基准测试来衡量它们，例如 junit-benchmark 或 Brent Boyer 的基准测试（请参阅什么是在 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.
此外，我认为 Java 的随机数生成器非常快，但在统计上很糟糕。而是使用外部库，例如http://www.cs.gmu.edu/~sean/research/ 上的 Mersenne Twister ，或者，如果运行时对您来说如此重要，则使用 Fast Mersenne Twister。
回答by Peter Lawrey
The time complexity of the random number generator is O(1). The time it takes does not increase as you have more random numbers.
随机数生成器的时间复杂度为 O(1)。随着随机数的增加，所需的时间不会增加。
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.
java.util.Random 的随机性可能是一个问题。它使用 2^48 的种子，因此它会在这么多值之后重复自己。这意味着 nextLong() 不会生成所有可能的值。
If this is an issue you can use SecureRandom which is slower but the point it repeats is much higher.
如果这是一个问题，您可以使用 SecureRandom，它速度较慢，但重复的次数要高得多。
回答by harold
According to the docs, java.util.Random.nextis implemented as follows:
根据文档，java.util.Random.next实现如下：
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.
这就是 Java 的随机数生成器，如前所述，它甚至不是随机数生成器，而是伪随机数生成器，而且在这方面不是很好。
回答by pageman
maybe you can try Texts in Computational Complexity: Pseudorandom Generators by Oded Goldreich
也许您可以尝试计算复杂性中的文本：Oded Goldreich 的 Pseudorandom Generators
"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."
"生成的复杂性：典型的选择是生成器必须在多项式时间内工作（输入的长度 - 种子）。其他选择也将讨论。我们注意到对生成器（或，或者，提出非常温和的要求，例如双指数运行时间上限），产生的“生成器”可以欺骗任何次指数大小的电路系列。”
