java - 在不使用任何外部函数的情况下生成随机数

Question

这是我最近参加的一次采访中提出的问题。

据我所知，两个数字之间的随机数可以生成如下

public static int rand(int low, int high) {
    return low + (int)(Math.random() * (high - low + 1));
}

但是在这里我使用 Math.random() 来生成一个介于 0 和 1 之间的随机数，并使用它来帮助我在低位和高位之间生成一个随机数。有没有其他方法可以不使用外部函数直接做？

Answer 1

典型的伪随机数生成器根据之前的数计算新数，因此理论上它们是完全确定的。通过提供良好的种子(随机数生成算法的初始化)来保证唯一的随机性。只要随机数不是非常安全的关键(这将需要“真正的”随机数)，这种递归随机数生成器通常可以满足需求。

一旦提供了种子，就可以在没有任何“外部”函数的情况下表示递归生成。有几种算法可以解决这个问题。一个很好的例子是 Linear Congruential Generator .

伪代码实现可能如下所示:

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;
}

您仍然需要为这个生成器设置一些初始值。这可以通过执行以下操作之一来完成:

• 使用像当前时间这样的东西(在大多数非安全关键的情况下，比如游戏)
• 使用硬件噪声(有利于安全关键随机性)
• 使用一个常数(有利于调试，因为您总是得到相同的序列)
• 如果您不能使用 any 函数并且不想使用常量种子，并且如果您使用的语言允许这样做，您也可以使用一些未初始化的内存。例如，在 C 和 C++ 中，定义一个新变量，不要给它赋值，而是使用它的值来为生成器播种。但请注意，这远非“好种子”，而只是满足您要求的黑客。切勿在实际代码中使用它。

请注意，没有算法可以为不同运行生成不同值相同的输入没有访问一些外部资源，例如系统环境。每个种子良好的随机数生成器都会使用一些外部资源。