4

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

现在我正在尝试实现一个签名看起来像的方法：

int getRandomInteger(int min, int max)

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

方法#1 是幼稚的。获取(max - min) / 256字节数并将它们相加。它可以工作，但它会从我拥有的慢速随机数生成器源中获取大量字节。例如，如果我想获得一百万到零之间的随机整数，它将获取近 4000 个字节......这是不可接受的。

方法 #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 代码或伪代码。

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

4

4 回答 4

2

不幸的是，您的方法 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。

这里介绍的其他一些解决方案存在问题，但很抱歉，我现在没有时间发表评论。如果有兴趣，可能会在几天内。

于 2012-11-10T16:59:09.513 回答
1 
range 1 to r
256^a >= r

first find 'a' 

get 'a' number of bytes into array A[]

num=0
for i=0 to len(A)-1
    num+=(A[i]^(8*i))
next

random number = num mod range
于 2012-11-10T16:41:56.420 回答
1

您的随机源每次调用为您提供 8 个随机位。对于 [min,max] 范围内的整数，您需要 ceil(log2(max-min+1)) 位。

假设您可以使用某些函数从源中获取随机字节：

bool RandomBuf(BYTE* pBuf , size_t nLen); // fill buffer with nLen random bytes

现在您可以使用以下函数在给定范围内生成随机值：

// --------------------------------------------------------------------------
// produce a uniformly-distributed integral value in range [nMin, nMax]
// T is char/BYTE/short/WORD/int/UINT/LONGLONG/ULONGLONG
template <class T> T RandU(T nMin, T nMax)
{
    static_assert(std::numeric_limits<T>::is_integer, "RandU: integral type expected");

    if (nMin>nMax)
        std::swap(nMin, nMax);

    if (0 == (T)(nMax-nMin+1)) // all range of type T
    {
        T nR;
        return RandomBuf((BYTE*)&nR, sizeof(T)) ? *(T*)&nR : nMin;
    }

    ULONGLONG nRange    = (ULONGLONG)nMax-(ULONGLONG)nMin+1        ; // number of discrete values
    UINT      nRangeBits= (UINT)ceil(log((double)nRange) / log(2.)); // bits for storing nRange discrete values
    ULONGLONG nR                                                   ;

    do
    {
        if (!RandomBuf((BYTE*)&nR, sizeof(nR)))
            return nMin;

        nR= nR>>((sizeof(nR)<<3) - nRangeBits); // keep nRangeBits random bits
    }
    while (nR >= nRange);                       // ensure value in range [0..nRange-1]

    return nMin + (T)nR;                        // [nMin..nMax]
}

由于您总是得到 8 位的倍数，因此您可以在调用之间节省额外的位（例如，您可能只需要 16 位中的 9 位）。它需要一些位操作，并且由您决定是否值得付出努力。

如果您使用“半位”，您可以节省更多：假设您要生成范围 [1..5] 内的数字。每个随机值都需要 log2(5)=2.32 位。使用 32 个随机位，您实际上可以在此范围内生成 floor(32/2.32)= 13 个随机值，尽管这需要一些额外的努力。

于 2012-11-10T16:42:30.490 回答
1

3 个字节（一起）为您提供 0..16777215 范围内的随机整数。您可以使用该值的 20 位来获取范围 0..1048575 并丢弃大于 1000000 的值

于 2012-11-10T16:39:18.907 回答