math - 如何有效地将几个字节转换为一个范围之间的整数？

Question

我正在写一些从非常慢的远程随机数生成源读取字节(只是一个 List<int> )的东西。为此和我的个人要求，我想检索 来自源的尽可能少的字节 .

现在我正在尝试实现一个签名如下所示的方法:

int getRandomInteger(int min, int max)

我有两个理论如何从我的随机源中获取字节，并将它们转换为整数。

方法#1 是幼稚的。获取 (max - min) / 256字节数并将它们相加。它可以工作，但它将从我拥有的慢速随机数生成器源中获取大量字节。例如，如果我想获得一个介于 100 万和 0 之间的随机整数，它将获取近 4000 个字节……这是 Not Acceptable 。

方法#2 对我来说听起来很理想，但我无法想出算法。它是这样的:

让我们以 min: 0, max: 1000 为例。

计算 ceil(rangeSize / 256)在这种情况下是 ceil(1000 / 256) = 4 .现在从源中获取一 (1) 个字节。

将这个字节从 0-255 范围缩放到 0-3 范围(或 1-4)，并让它决定我们使用哪个组。例如。如果字节为 250，我们将选择第 4 组(代表最后 250 个数字，即我们范围内的 750-1000)。

现在获取另一个字节并从 0-255 缩放到 0-250，然后让它确定我们拥有的组中的位置。因此，如果第二个字节是例如120，那么我们最终的整数是 750 + 120 = 870 .

在那种情况下，我们总共只需要获取 2 个字节。然而，如果我们的范围是 0-1000000，我们需要几个“组”，这要复杂得多。

我该如何实现这样的事情？我对 Java/C#/JavaScript 代码或伪代码没问题。

我还想保持结果不会丢失熵/随机性。所以，我有点担心缩放整数。

Answer 1

不幸的是，您的方法 #1 已损坏。例如，如果 min 为 0，max 为 510，您将添加 2 个字节。只有一种方法可以获得 0 结果:两个字节都为零。出现这种情况的几率是 (1/256)^2。然而，有很多方法可以获得其他值，比如 100 = 100+0、99+1、98+2……所以 100 的机会要大得多:101(1/256)^2。

做你想做的或多或少的标准方法是:

Let R = max - min + 1   -- the number of possible random output values
Let N = 2^k >= mR, m>=1  -- a power of 2 at least as big as some multiple of R that you choose.
loop
   b = a random integer in 0..N-1 formed from k random bits
while b >= mR -- reject b values that would bias the output
return min + floor(b/m)

这称为拒绝方法。它会丢弃随机选择的会使输出产生偏差的二进制数。如 min-max+1恰好是 2 的幂，那么您将有零拒绝。

如果您有 m=1和 min-max+1只是比 2 的大幂多一点，那么拒绝率将接近一半。在这种情况下，您肯定想要更大的 m .

一般来说，较大的 m 值会导致较少的拒绝，但当然它们每个数字需要更多的位。有一个概率最优算法来选择 m .

此处介绍的其他一些解决方案存在问题，但很抱歉，我现在没有时间发表评论。如果有兴趣，也许几天后。