4

我记得在面向数学的网站上的一篇文章中阅读了一种有效使用随机位的方法，但我似乎无法在 Google 中找到正确的关键字来找到它，而且它不在我的浏览器历史记录中。

所问问题的要点是在域 [ domainStart, domainEnd) 中获取随机数序列，并有效地使用随机数序列的位均匀地投影到范围 [ rangeStart, rangeEnd) 中。域和范围都是整数（更准确地说，long是 s 而不是 Z）。这样做的算法是什么？

在实现方面，我有一个带有这个签名的函数：

long doRead(InputStream in, long rangeStart, long rangeEnd);

in基于我需要使用的 CSPRNG（由硬件 RNG 提供，通过 SecureRandom 调节）；返回值必须在rangeStart和之间rangeEnd，但明显的实现是浪费：

long doRead(InputStream in, long rangeStart, long rangeEnd) {
    long retVal = 0;
    long range = rangeEnd - rangeStart;

    // Fill until we get to range
    for (int i = 0; (1 << (8 * i)) < range; i++) {
        int in = 0;
        do {
            in = in.read();
        // but be sure we don't exceed range
        } while(retVal + (in << (8 * i)) >= range);
        retVal += in << (8 * i);
     }

    return retVal + rangeStart;
}

我相信这实际上是相同的想法(rand() * (max - min)) + min，只是我们丢弃了推动我们前进的部分max。我们没有使用可能会错误地将结果偏向较低值的模运算符，而是丢弃这些位并重试。由于击中 CSPRNG 可能会触发重新播种（这可能会阻止 InputStream），我想避免浪费随机位。 Henry 指出该代码偏向于 0 和 257；班塔尔在一个例子中演示了它。

第一次编辑：亨利提醒我求和调用了中心极限定理。我已经修复了上面的代码来解决这个问题。

第二次编辑：机械蜗牛建议我查看 Random.nextInt() 的源代码。看了一会，才发现这个问题和基数转换问题差不多。请参阅下面的答案。

4

2 回答 2

2

您的算法会产生有偏差的结果。让我们假设rangeStart=0和rangeEnd=257。如果第一个字节大于0，那将是结果。如果是0，则结果将是0或256有50/50概率。因此0和256被选择的可能性比任何其他数字低两倍。

我做了一个简单的测试来确认这一点：

p(0)=0.001945
p(1)=0.003827
p(2)=0.003818
...
p(254)=0.003941
p(255)=0.003817
p(256)=0.001955

我认为你需要做同样的事情java.util.Random.nextInt并丢弃整个数字，而不是最后一个字节。

于 2013-09-22T08:25:51.433 回答
0

在阅读了 Random.nextInt() 的源代码后，我意识到这个问题类似于基础转换问题。

与一次转换单个符号相比，通过累加器“缓冲区”一次转换输入符号块会更有效，该缓冲区大到足以表示域和范围内的至少一个符号。新代码如下所示：

public int[] fromStream(InputStream input, int length, int rangeLow, int rangeHigh) throws IOException {
    int[] outputBuffer = new int[length];
    // buffer is initially 0, so there is only 1 possible state it can be in
    int numStates = 1;
    long buffer = 0;
    int alphaLength = rangeLow - rangeHigh;
    // Fill outputBuffer from 0 to length
    for (int i = 0; i < length; i++) {
        // Until buffer has sufficient data filled in from input to emit one symbol in the output alphabet, fill buffer.
        fill:
        while(numStates < alphaLength) {
            // Shift buffer by 8 (*256) to mix in new data (of 8 bits)
            buffer = buffer << 8 | input.read();
            // Multiply by 256, as that's the number of states that we have possibly introduced
            numStates = numStates << 8;
        }
        // spits out least significant symbol in alphaLength
        outputBuffer[i] = (int) (rangeLow + (buffer % alphaLength));
        // We have consumed the least significant portion of the input.
        buffer = buffer / alphaLength;
        // Track the number of states we've introduced into buffer
        numStates = numStates / alphaLength;
    }
    return outputBuffer;
}

然而，在基数之间转换数字和这个问题之间存在根本区别。为了在基数之间进行转换，我认为需要有足够的关于数字的信息来执行计算 - 目标基数的连续除法会产生用于构造目标字母表中数字的余数。在这个问题中，我真的不需要知道所有这些信息，只要我不偏向数据，这意味着我可以做我在标记为“填充”的循环中所做的事情。

于 2013-09-29T00:15:58.050 回答