什么是最有效的 rng 均匀随机整数算法？[复制]-解网

问：

如何在不浪费位的情况下从随机位流中生成 [0，n] 范围内的随机整数？（5 个答案）

去年关闭。

这不是#11766794“在一定范围内生成无偏随机整数的最佳算法是什么？”的重复。它的“最高票数”答案和“已接受”答案都与浮点外推有关，浮点外推甚至不会产生完全均匀的整数。这个问题是在给定一个可用的均匀浮点值的情况下快速获得均匀随机整数的良好近似的方法之后提出的;我是在一个完全均匀的随机整数算法的背景下提出这个问题的，该算法给定一个真正的随机位生成器（确定性或其他;无论哪种方式，这个问题都同样适用）。rand()

具体来说，我问的是仅从使用的随机位的效率的角度来看理论最优性：给定一个随机位流，在给定范围内生成完全均匀的随机整数的过程中，从中消耗最少位数的算法是什么？

例如，CPython 3.9.0 的 random.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 nn <= 1n.bit_length()(n-1).bit_length()

假设一个人在范围内生成一个整数：所有调用的一半将超过该值：如果第一个位和第二个位是高位，它无论如何都会消耗 11 位，并在看似不需要时丢弃它们。因此，这种算法似乎显然是非最优的。[0, 4097)getrandbits(13)

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

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⁶⁴ 以上的数字。

算法 Random BigInteger Optimal

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")

什么是最有效的 rng 均匀随机整数算法？[复制]

What is the most rng-efficient uniform random integer algorithm? [duplicate]

评论

评论