java - 如何获得用于生成随机数的范围？

Question

我使用 Java 中的种子生成随机数。知道最终输出是235，种子数是532，我怎样才能在java中获得intBound数呢？ 例如

int randomNumber
int seed=532;
int intBound=800;
Random rand = Random(seed); 
randomNumber=rand.nextInt(intBound);

System.out.println("The generated Random number using the above seed and int bound is:- "+randomNumber);
//Results is: The generated Random number using the above seed and int bound is: 235

问题的简化数学版本是:只知道数学公式的两个值，如何产生第三个值？例如 1+2=3 这也意味着如果我们只知道 2 个值和所使用的公式，我们可以轻松地通过知道用于获取结果的公式来获得第三个值。

Answer 1

这是不可能的。许多上限可以产生相同的输出。例如，quick test在 Ideone 上显示了 1000000 以下的 9 个可能的边界，这些边界将使用种子 532 产生 235 的输出(800 不是其中之一):237、369、711、3239、9717、29151、50549、151647 和 454941。

import java.util.*;

class Test
{
    public static void main (String[] args) throws java.lang.Exception
    {
        List<Integer> bounds = new ArrayList<Integer>();
        for (int i = 1; i < 1000000; i++) {
            Random rng = new Random(532);
            if (rng.nextInt(i) == 235) {
                bounds.add(i);
            }
        }
        System.out.println(bounds);
    }
}

<小时/>

您能做的最好的事情就是确定可能的界限。 nextInt(int) 的实现是 required相当于

 public int nextInt(int bound) {
   if (bound <= 0)
     throw new IllegalArgumentException("bound must be positive");

   if ((bound & -bound) == bound)  // i.e., bound is a power of 2
     return (int)((bound * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % bound;
   } while (bits - val + (bound-1) < 0);
   return val;
 }

该算法给出特定输出的方式可以分为三种可能性:

• bound 是 2 的幂
• bound 不是 2 的幂，循环在第一次迭代时终止
• bound 不是 2 的幂，并且循环将继续经过第一次迭代

二次方绑定(bind)的情况很简单 - 只需尝试适合int的每个二次方绑定(bind)即可。其中只有31个。您可以对此进行优化，但没有多大意义。

第一次迭代非二次幂的情况可以通过计算 next(31) 的值来处理(这可以通过播种 Random 实例并调用 next(31))，并查看 bound 的哪些值会给出正确的 val 值并终止做一会儿。

要给出正确的 val 值，bound 必须是大于 val 的 bits - val 因子>。 (有时 bits - val 将为 0，任何大于 val 的整数都会通过。)要终止 do-while，bits - val + (bound- 1) 不得溢出。因此，属于这种情况的可能界限是特定范围内的 bits - val 因子，而不是 2 的幂。

至于最后一个案例，我不想经历它，所以这将“留给读者作为练习”。 (这是最困难的情况，当您不知道 val 时，很难弄清楚 bound 的哪些值会导致溢出，这会花费比我更多的时间有。)