3

这不是#11766794“在一个范围内生成无偏随机整数的最佳算法是什么？”</a>。它的最高投票答案和接受的答案都与浮点外推法有关，这甚至不会产生完全一致的整数。这个问题是在询问如何在给定可用的统一浮点值的情况下快速获得统一随机整数的良好近似值rand()；我在给定真正的随机位生成器（确定性或其他方式；问题同样适用于任何一种方式）的情况下，在完全统一的随机整数算法的上下文中提出这个问题。

具体来说，我问的是仅就使用的随机比特的效率而言的理论最优性：给定一个随机比特流，在生成完美统一的过程中消耗最少比特的算法是什么给定范围内的随机整数？

例如，CPython 3.9.0random.randbelow至少有一个微不足道的低效率——当调用任何 2 的幂（包括微不足道的范围）时，它会浪费一个随机位：

def randbelow(n):
    "Return a random int in the range [0,n).  Returns 0 if n==0."
    if not n:
        return 0
    k = n.bit_length()  # don't use (n-1) here because n can be 1
    r = getrandbits(k)  # 0 <= r < 2**k
    while r >= n:
        r = getrandbits(k)
    return r

虽然这很容易通过将“ not n”替换为“ n <= 1”和“ n.bit_length()”替换为“”来修补(n-1).bit_length()，但一点分析表明它还有更多不足之处：

假设一个在范围内生成一个整数[0, 4097)：所有调用的一半getrandbits(13)将超过该值：如果第一个位和第二个位为高，无论如何它将消耗 11 个更多位，并在看起来没有时丢弃它们没必要。所以看起来这个算法显然不是最优的。

今晚我能在一个小时内得到的最好的算法是以下算法：

def randbelow(n):
    if n <= 1:
        return 0
    k = (n - 1).bit_length() # this is POPCNT for bignums
    while True:
        r = 0
        for i in reversed(range(k)):
            r |= getrandbits(1) << i
            if r >= n:
                break
        else:
            return r

但是，我不是数学家，仅仅因为我修复了我可以立即看到的低效率问题，并不能让我相信我只是在一个下午立即偶然发现了最有效的统一整数选择算法。

例如，比特是从量子或大气 RNG 服务购买的；或作为多方协议的一部分，其中每个单独的比特生成都需要多次往返；或者在没有任何硬件 RNG 支持的嵌入式设备上……无论如何，我只问一个直接的问题：从真正的随机比特流中生成（完美）均匀随机整数的算法对于随机数而言是最有效的位消耗？（或者，如果不确定，目前最好的候选人是什么？）

（我在这些示例中使用了 Python，因为这是我本赛季主要研究的内容，但问题绝不是特定于任何语言的，除非算法本身必须推广到 2 64以上的数字。）

4

1 回答 1

2

下面的 Python 以精确算术实现算术编码。这在计算上变得非常昂贵，但在期望中实现了熵 + O(1) 位，这基本上是最优的。

from fractions import Fraction
from math import floor, log2
import random


meter = 0


def metered_random_bits():
    global meter
    while True:
        yield bool(random.randrange(2))
        meter += 1


class ArithmeticDecoder:
    def __init__(self, bits):
        self._low = Fraction(0)
        self._width = Fraction(1)
        self._bits = bits

    def randrange(self, n):
        self._low *= n
        self._width *= n
        while True:
            f = floor(self._low)
            if self._low + self._width <= f + 1:
                self._low -= f
                return f
            self._width /= 2
            if next(self._bits):
                self._low += self._width


import collections

if __name__ == "__main__":
    k = 3000
    n = 7
    decoder = ArithmeticDecoder(metered_random_bits())
    print(collections.Counter(decoder.randrange(n) for i in range(k)))
    print("used", meter, "bits")
    print("entropy", k * log2(n), "bits")
于 2022-02-06T14:15:39.980 回答