产生随机数,而无需使用任何外部功能 [英] Generate Random numbers without using any external functions
问题描述
这是在问我最近参加了面试中的一个问题。
This was questions asked in one of the interviews that I recently attended.
据我所知可以如下产生两个数字之间的随机数
As far as I know a random number between two numbers can be generated as follows
public static int rand(int low, int high) {
return low + (int)(Math.random() * (high - low + 1));
}
但在这里我使用的Math.random()产生0和1之间的随机数并用它来帮助我的高低产生。有没有其他方法可以让我直接做,而无需使用外部功能?
But here I am using Math.random() to generate a random number between 0 and 1 and using that to help me generate between low and high. Is there any other way I can directly do without using external functions?
推荐答案
典型的伪随机数生成器计算的基础上previous那些新号码,所以从理论上讲,他们是完全确定的。唯一的随机性是通过提供一个良好的种子(随机数生成算法的初始化)保证。只要随机数是不很安全的关键(这将需要真正的随机数),这样的递归随机数发生器常满足需要。
Typical pseudo-random number generators calculate new numbers based on previous ones, so in theory they are completely deterministic. The only randomness is guaranteed by providing a good seed (initialization of the random number generation algorithm). As long as the random numbers aren't very security critical (this would require "real" random numbers), such a recursive random number generator often satisfies the needs.
递归代可以pssed没有任何外部功能EX $ P $,一旦种子提供了依据。有一对夫妇的算法解决了这个问题。一个很好的例子就是线性同余发生器。
The recursive generation can be expressed without any "external" functions, once a seed was provided. There are a couple of algorithms solving this problem. A good example is the Linear Congruential Generator.
一个伪code实现可能如下所示:
A pseudo-code implementation might look like the following:
long a = 25214903917; // These Values for a and c are the actual values found
long c = 11; // in the implementation of java.util.Random(), see link
long previous = 0;
void rseed(long seed) {
previous = seed;
}
long rand() {
long r = a * previous + c;
// Note: typically, one chooses only a couple of bits of this value, see link
previous = r;
return r;
}
您还需要种子这种生成一些初始值。这可以通过执行下列操作之一来完成:
You still need to seed this generator with some initial value. This can be done by doing one of the following:
- 在使用类似的当前时间(好在大多数非安全关键情况下,如游戏)
- 在使用硬件噪声(有利于安全关键随机性)
- 使用常数(对于调试很好,因为你总是得到相同的序列)
- 如果您不能使用的任意的功能,不想用一个恒定的种子,如果你正在使用的语言,它允许,您还可以使用一些初始化的内存。在C和C ++为例,定义一个新的变量,不分配的东西它并使用它的价值种子发电机。但是,请注意,这远不是一个好苗子,只有黑客以满足您的要求。从来没有在真正的code使用。
- Using something like the current time (good in most non-security-critical cases like games)
- Using hardware noise (good for security-critical randomness)
- Using a constant number (good for debugging, since you get always the same sequence)
- If you can't use any function and don't want to use a constant seed, and if you are using a language which allows this, you could also use some uninitialized memory. In C and C++ for example, define a new variable, don't assign something to it and use its value to seed the generator. But note that this is far from being a "good seed" and only a hack to fulfill your requirements. Never use this in real code.
请注意,有否算法,它可以产生的不同的的值的不同的的运行与相同的输入的无访问某些外部源类似的制度环境。每一个良好的种子随机数生成器是利用一些外部资源。
Note that there is no algorithm which can generate different values for different runs with the same inputs without access to some external sources like the system environment. Every well-seeded random number generator makes use of some external sources.
这篇关于产生随机数,而无需使用任何外部功能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!