如何根据随机位生成一定范围内的整数

Question

我有一些随机比特源，希望将其转换为不同大小的整数，大致与常用骰子（1-4、1-6等）的大小相对应。

我正在编写的代码是PHP，因此最好用这种语言回答。但是，通用算法回答也完全可以。

我希望得到的答案比简单地使用我的随机数据块来种子PHP的random()函数更加复杂。

- Winfield Trail

---

你是否有无限数量的随机位可供使用？ - Oliver Charlesworth

为什么使用随机数据作为种子不可接受？ - Oliver Charlesworth

我猜测从某个东西开始（即使是伪代码），然后询问它是否有效，可能会是一种更有效的方法。 :) - Jared Farrish

@Oli，按顺序：是的，就大多数情况而言，我拥有几乎无限的随机性，足以永久持续。其次，因为我了解PHP RNG的种子会产生一个数字，该数字由我的高质量随机性与系统时间和其他确定性因素混合制成的垃圾随机性相杂糅。 - Winfield Trail

如果你的初始种子是真正随机的，那么从RNG产生的序列将是真正随机的。（基本上，如果 y = f(x) 且 x 是随机的，则 y 也必须是随机的。）然而，这并不意味着未来的值不能从过去的值中预测出来... - Oliver Charlesworth

Answer 1

如果您有任意数量的比特可用，您可以选择使用拒绝方法，例如Java的Random.nextInt(int)。以下是从那里获取的伪代码：

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

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

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

next() 是一个函数，返回指定数量的随机位组成的 int。您可以将其替换为您的随机位来源。

- Oliver Charlesworth

---

嗯，这有可能可行。如果需要的话，我甚至可以将被拒绝的位放到随机性“堆栈”的后面以节省空间。 - Winfield Trail

尽管这似乎是常见的算法，但它不会给出完全随机的数字。当n接近最大整数时，误差会增加。 - soid

@soid：您所说的“确切随机”是什么意思，为什么您认为误差会增加？ - Oliver Charlesworth

@soid：这就是为什么它在执行拒绝操作的 while 循环中。 这可以确保均匀分布。 - Oliver Charlesworth

@soid：最坏情况是n=2^30+1，这将导致拒绝率为0.5。 - Oliver Charlesworth