不使用任何外部函数生成随机数 [英] 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?

推荐答案

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

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.

一旦提供了种子，就可以在没有任何外部"函数的情况下表达递归生成.有几种算法可以解决这个问题.一个很好的例子是线性同余生成器.

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.

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

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++ 中，定义一个新变量，不要为其赋值，而是使用它的值为生成器提供种子.但请注意，这远不是好种子"，而只是满足您要求的技巧.切勿在实际代码中使用它.

• 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屋！