从随机位生成非 2 幂范围内的随机数

Question

我有无限的随机位流。

我想生成一个0到999（含）之间的随机数。

是最好的算法：

• 拉10位
• 如果它们的值小于 1,000，请使用它，
• 否则再拉 10 位。

或者有更好的方法吗？也许有一种算法可以保证只消耗有限数量的比特？

Answer 1

在这种情况下，区分“无限”和“无界”非常重要。

在您的情况下，您将能够以概率 1 生成具有有限位数的随机数，但不能保证所需位数的上限为概率 1。

我们总结为“所需的位数是有限但无限的。”

但是，您可以保证相对较高的概率上限。

即使使用提取 10 位的简单策略，如果生成的数字高于 1000，则丢弃它，然后重新开始，您也只有概率 24/1024 = 0.2% 需要超过 10 位，概率 (24/1024)^2 = 需要超过 20 位的 0.05%，概率 (24/1024)^3 = 需要超过 30 位的 0.001%，概率 (24/1024)^4 = 需要超过 40 位的 0.00003%，等等

当您拒绝一个数字时，通过不丢弃额外的信息位，即记住您已经超过 999 的数量，您可以稍微提高效率。如果您超过 999，则意味着该数字介于 [1000, 1023] 之间。超过999的方式有24种，而且是均匀分布的。减去 1000，您将得到 [0, 23] 中的统一随机数，其价值约为 4.5 位随机性，您可以将其用于下一个生成的随机数。

这是该方法在 python 中的实现：

def gen_random(bitstream, n):
    x = next(bitstream)  # random number generated so far
    m = 2                # x is always uniform in range [0, m-1]
    while m < 100000 and x < 100000:
        print(f'x={x}, m={m}')
        x = x * 2 + next(bitstream)
        m *= 2
        if m >= n:
            if x < n:
                return x
            else:
                x = x - n
                m = m - n

from itertools import count
from random import getrandbits

bitstream = (getrandbits(1) for _ in count())
print('Uniform random number between 0 and 999: ', gen_random(bitstream, 1000))

注意：就实际执行速度而言，上述代码效率较低，因为它调用

getrandbits(1)

十次，而不是调用

getrandbits(10)

一次 - 但就从流中拉取的位数而言，它是最佳的。