java 不使用任何外部函数生成随机数

Generate Random numbers without using any external functions

提问by Usha

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?

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

回答by leemes

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 anyfunction 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.

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

Note that there is no algorithmwhich can generate differentvalues for differentruns with the same inputswithout access to some external sourceslike the system environment. Every well-seeded random number generator makes use of some external sources.

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

回答by Grijesh Chauhan

Here I am suggesting some sources with comment may be you find helpful:

在这里，我建议一些带有评论的来源可能对您有所帮助：

• System Time: Monotonic in a day poor random. Fast, Easy.
• Mouse Point: Random But not useful on standalone system.
• Raw Socket/ Local Network(Packet 's info-part ) : Good Random Technical and time consuming - Possible to model a attack mode to reduce randomness.
• Some input text with permutation: Fast, Common way and good too (in my opinion).
• Timing of the Interrupt due to keyboard, disk-drive and other events:Common way – error prone if not used carefully.
• Another approach is to feed an analog noise signal: example like temp.

• /procfile data: On Linux system. I feel you should use this.

  /proc/sys/kernel/random:This directory contains various parameters controlling the operation of the file /dev/random.

  The character special files /dev/randomand /dev/urandom(present since Linux 1.3.30) provide an interface to the kernel's random number generator.

  try this commads:

  $cat /dev/urandom   
  

  and

  $cat /dev/random
  

  You can write a file read function that read from this file.

  Read (also suggests): Is a rand from /dev/urandom secure for a login key?

• 系统时间：单调的一天不好随机。快速，简单。
• 鼠标点：随机但在独立系统上没有用。
• 原始套接字/本地网络（数据包的信息部分）：良好的随机技术和耗时 - 可以建模攻击模式以减少随机性。
• 一些带有排列的输入文本：快速，通用，也很好（在我看来）。
• 由于键盘、磁盘驱动器和其他事件引起的中断时间：常见方式 - 如果不小心使用，容易出错。
• 另一种方法是提供模拟噪声信号：例如 temp。

• /proc文件数据：在 Linux 系统上。我觉得你应该用这个。

  /proc/sys/kernel/random:该目录包含控制文件操作的各种参数/dev/random。

  字符特殊文件/dev/random和/dev/urandom（自 出现Linux 1.3.30）为内核的随机数生成器提供了一个接口。

  试试这个命令：

  $cat /dev/urandom   
  

  和

  $cat /dev/random
  

  您可以编写从该文件中读取的文件读取函数。

  阅读（也建议）：来自 /dev/urandom 的 rand 是否安全用于登录密钥？

`

`

回答by Krease

Does System.currentTimeMillis()count as external? You could always get this and calculate mod by some max value:

是否System.currentTimeMillis()算作外部？你总是可以得到这个并通过一些最大值计算 mod：

int rand = (int)(System.currentTimeMillis()%high)+low;

回答by Mark Hurd

You can get near randomness (actually chaotic and definitely not uniform*) from the logistic map x = 4x(1-x)starting with a "non-rational" xbetween 0and 1.

你可以得到接近随机性从逻辑图（实际上混乱，绝对不是制服*）x = 4x(1-x)开头的“非理性”x之间的0和1。

The "randomness" appears because ofthe rounding errors at the edge of the accuracy of the floating point representation.

“随机性”的出现是因为浮点表示精度边缘的舍入误差。

(*)You can undo the skewing once you know it is there.

(*) 一旦你知道它在那里，你就可以撤销它。

回答by Alireza Soori

You may use the address of a variable or combine the address of more variables to make a more complex one...

您可以使用一个变量的地址或组合更多变量的地址来制作一个更复杂的...

回答by user000001

You could get the current system time, but that would also require a function in most languages.

您可以获得当前系统时间，但这也需要大多数语言的函数。

回答by mikera

You can do it without external functions if you are allowed to use some external state (e.g. a long initialised with the current system time). This is enough for you to implement a simple psuedo-random number generator.

如果允许使用某些外部状态（例如使用当前系统时间进行长时间初始化），则无需外部函数即可完成此操作。这足以让您实现一个简单的伪随机数生成器。

In each call to your random function, you would use the state to create a new random value, and update the state, so that subsequent calls get different results.

在对随机函数的每次调用中，您将使用状态创建一个新的随机值，并更新状态，以便后续调用获得不同的结果。

You can do this with just regular Java arithmetic and/or bitwise operations, so no external functions are required.

您只需使用常规 Java 算术和/或按位运算即可完成此操作，因此不需要外部函数。

回答by Narayana nadiminti

public class randomNumberGenerator {

    int generateRandomNumber(int min, int max) {
        return (int) ((System.currentTimeMillis() % max) + min);
    }

    public static void main(String[] args) {
        randomNumberGenerator rn = new randomNumberGenerator();
        int cv = 0;
        int min = 1, max = 4;
        Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();

        int count = min;
        while (count <= max) {
            cv = rn.generateRandomNumber(min, max);
            if ((hmap.get(cv) == null) && cv >= min && cv <= max) {
                System.out.print(cv + ",");
                hmap.put(cv, 1);
                count++;
            }
        }

    }
}

回答by SureshS

Poisson Random Generator

泊松随机发生器

Lets say we start with an expected value 'v' of the random numbers. Then to say that a sequence of non negative integers satisfies a Poisson Distribution with expected value v means that over subsequences, the mean(average) of the value will appear 'v'. Poisson Distribution is part of statistics and the details can be found on wikipedia. But here the main advantage of using this function are: 1. Only integer values are generated. 2. The mean of those integers will be equal to the value we initially provided.

假设我们从随机数的期望值“v”开始。然后说非负整数序列满足具有期望值 v 的泊松分布意味着在子序列上，值的均值（平均值）将出现“v”。泊松分布是统计的一部分，详细信息可以在维基百科上找到。但是这里使用这个函数的主要优点是： 1. 只生成整数值。2. 这些整数的平均值将等于我们最初提供的值。

It is helpful in applications where fractional values don't make sense. Like number of planes arriving on an airport in 1min is 2.5(doesn't make sense) but it implies that in 2 mins 5 plans arrive.

它在小数值没有意义的应用程序中很有帮助。就像 1 分钟内到达机场的飞机数量是 2.5（没有意义），但这意味着在 2 分钟内有 5 个计划到达。

int poissonRandom(double expectedValue) {
  int n = 0; //counter of iteration
  double limit; 
  double x;  //pseudo random number
  limit = exp(-expectedValue);
  x = rand() / INT_MAX; 
  while (x > limit) {
    n++;
    x *= rand() / INT_MAX;
  }
  return n;
}

The line

线

rand() / INT_MAX

should generate a random number between 0 and 1. So we can use time of the system. Seconds / 60 will serve the purpose. Which function we should use is totally application dependent.

应该生成一个介于 0 和 1 之间的随机数。因此我们可以使用系统的时间。秒/60 将达到目的。我们应该使用哪个函数完全取决于应用程序。