生成随机数而不使用任何外部功能 [英] Generate Random numbers without using any external functions

问题描述

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

（int low，int high）{
return low +（int）（Math.random（））$（$）

 *（高 - 低+ 1））; 
} 
  

但是在这里我使用Math.random（）生成一个随机数0和1，并使用它来帮助我在低和高之间生成。

解决方案

典型的伪随机数生成器根据以前的，所以在理论上它们是完全确定的。通过提供良好的种子（随机数生成算法的初始化）来保证唯一的随机性。只要随机数不是非常安全的关键（这将需要真正的随机数），这样的递归随机数发生器通常满足需求。

一旦种子被提供，递归世代可以被表达而没有任何外部功能。有几个算法解决这个问题。一个很好的例子是线性同余发生器。

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

  long a = 25214903917; //这些a和c的值是实际的值
 long c = 11; //在java.util.Random（）的实现中，请参阅link 
 long previous = 0; 
 
 void rseed（long seed）{
 previous = seed; 
} 
 
 long rand（）{
 long r = a * previous + c; 
 //注意：通常，只选择这个值的几个位，请参阅link 
 previous = r; 
 return r; 
} 
  

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

• 使用类似于当前时间的东西（在大多数非安全关键的情况下


• 使用硬件噪声（有利于安全关键的随机性）


• 使用常数（好的调试，因为你总是一样序列）


• 如果您不能使用任何函数，并且不想使用常量种子，如果您使用的语言允许，你也可以使用一些未初始化的内存。例如，在C和C ++中，定义一个新的变量，不要给它分配一些东西，并使用它的值来种子生成器。但请注意，这远远不是一个好的种子，只是一个黑客来满足你的要求。

请注意，无算法可以生成不同的 每个种子良好的随机数生成器都使用一些外部来源。

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

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:

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