无需任何外部函数即可生成随机数

Question

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

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

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

但是在这里，我使用Math.random（）生成一个介于0和1之间的随机数，并使用它来帮助我生成一个介于低数和高数之间的数。我还有其他方法可以直接使用，而无需使用外部函数吗？

Answer 1

典型的伪随机数生成器基于先前的数字来计算新数字，因此从理论上讲，它们是完全确定的。通过提供良好的种子（随机数生成算法的初始化）来保证唯一的随机性。只要随机数不是非常严格的安全性（这将需要“真实”随机数），这样的递归随机数生成器通常就可以满足需求。

一旦提供了种子，就可以在没有任何“外部”功能的情况下表达递归生成。有两种算法可以解决此问题。线性同余生成器就是一个很好的例子。

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

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

您仍然需要使用一些初始值为该生成器添加种子。这可以通过执行以下任一操作来完成：

• 使用当前时间（在大多数非安全性至关重要的情况下，例如游戏中使用）
• 使用硬件噪声（对安全性至关重要的随机性有好处）
• 使用常数（用于调试，因为您始终获得相同的序列）
• 如果您不能使用 任何 函数并且不想使用常量种子，并且使用的语言允许这样做，那么您还可以使用一些未初始化的内存。例如，在C和C ++中，定义一个新变量，不要为其分配任何内容，而应使用其值作为生成器的种子。但是请注意，这远非成为“好种子”，而仅仅是满足您要求的技巧。切勿在真实代码中使用此代码。

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