来自有限位 TRNG 的均匀分布无偏 4 位简约范围映射
uniformly distributed unbiased 4bit parsimonious range mapping from a bit limited TRNG
我正在尝试为 C 应用程序的 TRNG 输出文件实现一个范围映射器，其范围最大为 4 位。由于鸽巢偏差问题，我决定使用丢弃算法。
我对简约算法的想法是这样的：
-- 从文件中读取 16 个字节并存储为索引的 128 位无符号整数位桶以作为位掩码 select一次编辑 n 位。
-- 尽可能预先确定每个输入所需的ranges/buckets并存储在数组中。
-- 对于 bitbucket select 中的每个 n 位，来自数组的输入如果存在则不会丢弃它。如果 2 位找不到输入，请尝试 3 位，如果找不到输入，请尝试使用 4 位。起初，当有很多输入时，不丢弃应该很容易，但是随着输入的选择越来越少，丢弃将变得更加普遍。我不完全确定是从更少的位开始并逐步提高还是相反。
这个 bit sipping range mapper 的缺点似乎是我需要假设大约两倍于有偏差缩放方法所需的随机输入数据。例如，来自 4 位随机输出的 9 桶输入将丢失大约 43% 的时间。
现有implementations/algorithms：
This 似乎是一个更复杂、更有效的简约范围映射方法的例子，但我发现他的解释完全难以理解。任何人都可以用英语向我解释一下或推荐一本书或一所大学 class 我可能会给我一个理解它的背景吗？
还有 arc4random 似乎是运行时优化的无偏模丢弃实现。就像我发现的几乎所有无偏范围映射器实现一样，这似乎并不特别关心它使用了多少数据。然而，这并不意味着它的数据效率必然较低，因为它具有较少遗漏的优势。
arc4random的基本思想貌似是只要鸽子数（max_randvalue_output）能被孔数（rangeupperbound）整除模函数本身就是一个优雅的 和无偏 范围映射器。然而，模数似乎只在你不喝水时才有意义，即当随机源的输出超过 ceil(log2(buckets)) 位时。
'wasted' 随机位的数量和丢弃的百分比之间似乎存在折衷。未命中的百分比与范围映射器输入中的多余位数成反比。似乎应该有一种数学方法来比较 bit sipping range mapper 的数据效率和 miss 更少的 bit hungry 版本，但我不知道。
所以我的计划是只写两个实现：一种可能有点像也可能不像数学论坛示例（我不明白）的简约类型的范围映射器和一个不变的字节输入模数范围mapper 接受来自 TRNG 的字节输入，并使用从最大乘数顶部丢弃的模去偏方法将 (x)n 只鸽子与 n 个孔相匹配，这类似于 arc4random。完成后，我计划 post 他们进行代码审查。
我基本上是在寻求有关这些问题的帮助或建议，这些问题可能会帮助我编写一个更简洁但仍然不偏不倚的范围映射器，尤其是在我的简约算法方面。运行时效率不是优先事项。
有一种更简单的方法可以从随机比特流中生成一定范围内的随机数，这种方法不仅效率最高，而且准确。它被称为 J. Lumbroso 的 "Fast Dice Roller" 方法：
"Optimal Discrete Uniform Generation from Coin Flips, and Applications", 2013.
另见 。
我看了一下@Peter.O指向的"Fast Dice Roller"（FDR），确实很简单（而且避免了除法）。但是每次生成一个随机数时，这都会吃掉一些位并丢弃它不使用的那部分位。
"batching"/"pooling" 技术似乎比 FDR 做得更好，因为未使用的部分比特被（至少部分）保留了。
但有趣的是，您引用的 DrMath 与 FDR 基本相同，但并不是每个随机值都从头开始 returns。
所以 FDR 到 return 0..n-1 是：
random(n):
m = 1 ; r = 0
while 1:
# Have r random and evenly distributed in 0..m-1
# Need m >= n -- can double m and double r adding random bit until
# we get that. r remains evenly distributed in 0..m-1
while m < n: r = 2*r + next_bit() ; m = m*2
# Now have r < m and n <= m < n*2
if r < n: return r # Hurrah !
# Have overshot, so reduce m and r to m MOD n and r MOD m
m -= n ; r -= n ;
DrMath 的事情是：
# Initialisation once before first call of random(m)
ms = 1 ; rs = 0
N = ... # N >= maximum n and N*2 does not overflow
# The function -- using the "static"/"global" ms, rs and N
random(n):
m = ms ; r = rs
while 1:
# Same as FDR -- except work up to N not n
while m < N: r = 2*r + next_bit() ; m = m*2 ;
# Now have r < m and m >= N
# Set nq = largest multiple of n <= m
# In FDR, at this point q = 1 and nq = n
q = m DIV n ;
nq = n * q
if r < nq: # all set if r < nq
# in FDR ms = 1, rs = 0
ms = q # keep stuff not used this time
rs = r DIV n # ditto
return r MOD n # hurrah !
# Overshot, so reduce MOD n*q -- remembering, for FDR q == 1
m = m - nq
r = r - nq
如前所述，这与 FDR 基本相同，但会跟踪未使用的随机性。
测试时我发现：
FDR: for 100000 values range=3 used 266804 bits cost=1.6833
DrMath: for 100000 values range=3 used 158526 bits cost=1.0002
其中 cost 是 bits-used / (100000 * log2(3))，注意 log2(3) = (1.58496)。 （因此 cost 是使用的位数除以希望使用的位数）。
还有：
FDR: for 100000 values range=17: 576579 bits cost=1.4106
DrMath: for 100000 values range=17: 408774 bits cost=1.0001
并且：
FDR: for 100000 values ranges=5..60: 578397 bits cost=1.2102
DrMath: for 100000 values ranges=5..60: 477953 bits cost=1.0001
其中构造了 100000 个值，并为每个值选择了一个范围 5..60（含）。
在我看来，DrMath 有它！尽管对于更大的范围，它的优势较小。
请注意...DrMath 对每个随机值使用至少 2 个除法 returned，这让我在时间方面变得更聪明 运行。但是您确实说过您对 运行-时间效率不感兴趣。
它是如何工作的？
因此，我们希望随机值序列 r 均匀分布在 0..n-1 范围内。不方便的是，我们只有一个随机源，它为我们提供了均匀分布在 0..m-1 中的随机值。通常 m 将是 2 的幂——让我们假设 n < m（如果 n == m 问题是微不足道的，如果 n > m 问题是不可能的）。对于任何 r 我们可以取 r MOD n 来给出所需范围内的随机值。如果我们只在 r < n 时使用 r 那么（平凡地）我们就有了我们想要的均匀分布。如果我们在 r < (n * q) 和 (n * q) < m 时只使用 r，我们也有一个均匀分布。我们在这里 "rejecting" r 这是 "too big"。我们拒绝的 r 越少越好。所以我们应该选择 q 使得 (n * q) <= m < (n * (q-1)) -- 所以 n * q 是 n 小于或等于 m 的最大倍数。这反过来告诉我们 n "much less" 比 m 更受欢迎。
当我们 "reject" 一个给定的 r 时，我们可以把它全部扔掉，但事实证明这并不是完全必要的。此外，m 不一定是 2 的幂。但我们稍后会谈到。
这是一些工作 Python:
M = 1
R = 0
N = (2**63) # N >= maximum range
REJECT_COUNT = 0
def random_drmath(n):
global M, R, REJECT_COUNT
# (1) load m and r "pool"
m = M
r = R
while 1:
# (2) want N <= m < N*2
# have 0 <= r < m, and that remains true.
# also r uniformly distributed in 0..m-1, and that remains true
while m < N:
r = 2*r + next_bit()
m = m*2
# (3) need r < nq where nq = largest multiple of n <= m
q = m // n
nq = n * q
if r < nq:
# (4) update the m and r "pool" and return 0..n-1
M = q
R = r // n
return r % n # hurrah !
# (5) reject: so reduce both m and r by MOD n*q
m = m - nq
r = r - nq
REJECT_COUNT += 1
必须有 N >= 最大范围，最好大得多。 2**31 或 2**63 是显而易见的选择。
在第一次调用 random_drmath() 时，步骤 (2) 会将随机位读取到 "fill the pool"。对于 N = 2**63，将以 m = 2**63 和 r 结束，具有 63 个随机位。显然 r 是随机均匀分布在 0..m-1 中的。 [到目前为止，还不错。]
现在（以及对 random_drmath() 的所有进一步调用）我们希望从 r 中统一提取一个随机值 0..n-1，如上所述。所以 -- 步骤 (3) -- 构造 nq，它是 n 小于或等于 m 的 最大 倍数。如果 r >= nq 我们不能使用它，因为 nq..m-1 中的值少于 n -- 这是通常的 "reject" 标准。
因此，r < nq 可以 return 一个值——步骤 (4)。这里的技巧是将 m 和 r 视为数字 "base-n"。 r 的 ls "digit" 被提取（r % n）和 returned。然后m和r右移一位"digit"（q = m // n和r // n），存入"pool"。我认为很明显，此时 r 和 m 仍然是 r < m 和 r 随机均匀分布在 0..m-1 中。但是 m 不再是 2 的幂——不过没关系。
但是，如果 r >= nq 必须同时减少 r 和 m -- 步骤 (5) -- 然后重试。简单地说，可以设置 m = 1 ; r = 0 并重新开始。但我们所做的是从 m 和 r 中减去 nq，这样 r 均匀分布在 0..m-1 中。这最后一步感觉很神奇，但我们知道 r 在 nq..m-1 中并且每个可能的值都有相等的概率，所以 r-nq 在范围 0..m-nq-1 中并且每个可能的值还是概率相等！ [记住while循环最前面的'invariant'就是r是随机均匀分布在0..m-1中的。]
对于小 n，拒绝步骤将丢弃大部分 r，但对于小 n（与 N 相比），我们希望不要经常拒绝。相反，对于大 n（与 N 相比），我们可能会期望更频繁地拒绝，但这至少保留了一些我们到目前为止已经吃掉的随机位。我觉得可能有一种方法可以保留更多的 r...但是还没有想到一种简单的方法...如果读取一个随机位的成本很高，它可能是值得尝试找到一个不简单的方法！
FWIW：设置 N = 128 我得到：
FDR: for 100000 values ranges=3.. 15: 389026 bits cost=1.2881
DrMath: for 100000 values ranges=3.. 15: 315815 bits cost=1.0457
FDR: for 100000 values ranges 3.. 31: 476428 bits cost=1.2371
DrMath: for 100000 values ranges 3.. 31: 410195 bits cost=1.0651
FDR: for 100000 values ranges 3.. 63: 568687 bits cost=1.2003
DrMath: for 100000 values ranges 3.. 63: 517674 bits cost=1.0927
FDR: for 100000 values ranges 3..127: 664333 bits cost=1.1727
DrMath: for 100000 values ranges 3..127: 639269 bits cost=1.1284
随着 n 接近 N，单位价值成本上升。
我正在尝试为 C 应用程序的 TRNG 输出文件实现一个范围映射器，其范围最大为 4 位。由于鸽巢偏差问题，我决定使用丢弃算法。
我对简约算法的想法是这样的：
-- 从文件中读取 16 个字节并存储为索引的 128 位无符号整数位桶以作为位掩码 select一次编辑 n 位。
-- 尽可能预先确定每个输入所需的ranges/buckets并存储在数组中。
-- 对于 bitbucket select 中的每个 n 位，来自数组的输入如果存在则不会丢弃它。如果 2 位找不到输入，请尝试 3 位，如果找不到输入，请尝试使用 4 位。起初，当有很多输入时，不丢弃应该很容易，但是随着输入的选择越来越少，丢弃将变得更加普遍。我不完全确定是从更少的位开始并逐步提高还是相反。
这个 bit sipping range mapper 的缺点似乎是我需要假设大约两倍于有偏差缩放方法所需的随机输入数据。例如，来自 4 位随机输出的 9 桶输入将丢失大约 43% 的时间。
现有implementations/algorithms： This 似乎是一个更复杂、更有效的简约范围映射方法的例子，但我发现他的解释完全难以理解。任何人都可以用英语向我解释一下或推荐一本书或一所大学 class 我可能会给我一个理解它的背景吗？
还有 arc4random 似乎是运行时优化的无偏模丢弃实现。就像我发现的几乎所有无偏范围映射器实现一样，这似乎并不特别关心它使用了多少数据。然而，这并不意味着它的数据效率必然较低，因为它具有较少遗漏的优势。
arc4random的基本思想貌似是只要鸽子数（max_randvalue_output）能被孔数（rangeupperbound）整除模函数本身就是一个优雅的 和无偏 范围映射器。然而，模数似乎只在你不喝水时才有意义，即当随机源的输出超过 ceil(log2(buckets)) 位时。
'wasted' 随机位的数量和丢弃的百分比之间似乎存在折衷。未命中的百分比与范围映射器输入中的多余位数成反比。似乎应该有一种数学方法来比较 bit sipping range mapper 的数据效率和 miss 更少的 bit hungry 版本，但我不知道。
所以我的计划是只写两个实现：一种可能有点像也可能不像数学论坛示例（我不明白）的简约类型的范围映射器和一个不变的字节输入模数范围mapper 接受来自 TRNG 的字节输入，并使用从最大乘数顶部丢弃的模去偏方法将 (x)n 只鸽子与 n 个孔相匹配，这类似于 arc4random。完成后，我计划 post 他们进行代码审查。
我基本上是在寻求有关这些问题的帮助或建议，这些问题可能会帮助我编写一个更简洁但仍然不偏不倚的范围映射器，尤其是在我的简约算法方面。运行时效率不是优先事项。
有一种更简单的方法可以从随机比特流中生成一定范围内的随机数，这种方法不仅效率最高，而且准确。它被称为 J. Lumbroso 的 "Fast Dice Roller" 方法：
"Optimal Discrete Uniform Generation from Coin Flips, and Applications", 2013.
另见
我看了一下@Peter.O指向的"Fast Dice Roller"（FDR），确实很简单（而且避免了除法）。但是每次生成一个随机数时，这都会吃掉一些位并丢弃它不使用的那部分位。
"batching"/"pooling" 技术似乎比 FDR 做得更好，因为未使用的部分比特被（至少部分）保留了。
但有趣的是，您引用的 DrMath 与 FDR 基本相同，但并不是每个随机值都从头开始 returns。
所以 FDR 到 return 0..n-1 是：
random(n):
m = 1 ; r = 0
while 1:
# Have r random and evenly distributed in 0..m-1
# Need m >= n -- can double m and double r adding random bit until
# we get that. r remains evenly distributed in 0..m-1
while m < n: r = 2*r + next_bit() ; m = m*2
# Now have r < m and n <= m < n*2
if r < n: return r # Hurrah !
# Have overshot, so reduce m and r to m MOD n and r MOD m
m -= n ; r -= n ;
DrMath 的事情是：
# Initialisation once before first call of random(m)
ms = 1 ; rs = 0
N = ... # N >= maximum n and N*2 does not overflow
# The function -- using the "static"/"global" ms, rs and N
random(n):
m = ms ; r = rs
while 1:
# Same as FDR -- except work up to N not n
while m < N: r = 2*r + next_bit() ; m = m*2 ;
# Now have r < m and m >= N
# Set nq = largest multiple of n <= m
# In FDR, at this point q = 1 and nq = n
q = m DIV n ;
nq = n * q
if r < nq: # all set if r < nq
# in FDR ms = 1, rs = 0
ms = q # keep stuff not used this time
rs = r DIV n # ditto
return r MOD n # hurrah !
# Overshot, so reduce MOD n*q -- remembering, for FDR q == 1
m = m - nq
r = r - nq
如前所述，这与 FDR 基本相同，但会跟踪未使用的随机性。
测试时我发现：
FDR: for 100000 values range=3 used 266804 bits cost=1.6833
DrMath: for 100000 values range=3 used 158526 bits cost=1.0002
其中 cost 是 bits-used / (100000 * log2(3))，注意 log2(3) = (1.58496)。 （因此 cost 是使用的位数除以希望使用的位数）。
还有：
FDR: for 100000 values range=17: 576579 bits cost=1.4106
DrMath: for 100000 values range=17: 408774 bits cost=1.0001
并且：
FDR: for 100000 values ranges=5..60: 578397 bits cost=1.2102
DrMath: for 100000 values ranges=5..60: 477953 bits cost=1.0001
其中构造了 100000 个值，并为每个值选择了一个范围 5..60（含）。
在我看来，DrMath 有它！尽管对于更大的范围，它的优势较小。
请注意...DrMath 对每个随机值使用至少 2 个除法 returned，这让我在时间方面变得更聪明 运行。但是您确实说过您对 运行-时间效率不感兴趣。
它是如何工作的？
因此，我们希望随机值序列 r 均匀分布在 0..n-1 范围内。不方便的是，我们只有一个随机源，它为我们提供了均匀分布在 0..m-1 中的随机值。通常 m 将是 2 的幂——让我们假设 n < m（如果 n == m 问题是微不足道的，如果 n > m 问题是不可能的）。对于任何 r 我们可以取 r MOD n 来给出所需范围内的随机值。如果我们只在 r < n 时使用 r 那么（平凡地）我们就有了我们想要的均匀分布。如果我们在 r < (n * q) 和 (n * q) < m 时只使用 r，我们也有一个均匀分布。我们在这里 "rejecting" r 这是 "too big"。我们拒绝的 r 越少越好。所以我们应该选择 q 使得 (n * q) <= m < (n * (q-1)) -- 所以 n * q 是 n 小于或等于 m 的最大倍数。这反过来告诉我们 n "much less" 比 m 更受欢迎。
当我们 "reject" 一个给定的 r 时，我们可以把它全部扔掉，但事实证明这并不是完全必要的。此外，m 不一定是 2 的幂。但我们稍后会谈到。
这是一些工作 Python:
M = 1
R = 0
N = (2**63) # N >= maximum range
REJECT_COUNT = 0
def random_drmath(n):
global M, R, REJECT_COUNT
# (1) load m and r "pool"
m = M
r = R
while 1:
# (2) want N <= m < N*2
# have 0 <= r < m, and that remains true.
# also r uniformly distributed in 0..m-1, and that remains true
while m < N:
r = 2*r + next_bit()
m = m*2
# (3) need r < nq where nq = largest multiple of n <= m
q = m // n
nq = n * q
if r < nq:
# (4) update the m and r "pool" and return 0..n-1
M = q
R = r // n
return r % n # hurrah !
# (5) reject: so reduce both m and r by MOD n*q
m = m - nq
r = r - nq
REJECT_COUNT += 1
必须有 N >= 最大范围，最好大得多。 2**31 或 2**63 是显而易见的选择。
在第一次调用 random_drmath() 时，步骤 (2) 会将随机位读取到 "fill the pool"。对于 N = 2**63，将以 m = 2**63 和 r 结束，具有 63 个随机位。显然 r 是随机均匀分布在 0..m-1 中的。 [到目前为止，还不错。]
现在（以及对 random_drmath() 的所有进一步调用）我们希望从 r 中统一提取一个随机值 0..n-1，如上所述。所以 -- 步骤 (3) -- 构造 nq，它是 n 小于或等于 m 的 最大 倍数。如果 r >= nq 我们不能使用它，因为 nq..m-1 中的值少于 n -- 这是通常的 "reject" 标准。
因此，r < nq 可以 return 一个值——步骤 (4)。这里的技巧是将 m 和 r 视为数字 "base-n"。 r 的 ls "digit" 被提取（r % n）和 returned。然后m和r右移一位"digit"（q = m // n和r // n），存入"pool"。我认为很明显，此时 r 和 m 仍然是 r < m 和 r 随机均匀分布在 0..m-1 中。但是 m 不再是 2 的幂——不过没关系。
但是，如果 r >= nq 必须同时减少 r 和 m -- 步骤 (5) -- 然后重试。简单地说，可以设置 m = 1 ; r = 0 并重新开始。但我们所做的是从 m 和 r 中减去 nq，这样 r 均匀分布在 0..m-1 中。这最后一步感觉很神奇，但我们知道 r 在 nq..m-1 中并且每个可能的值都有相等的概率，所以 r-nq 在范围 0..m-nq-1 中并且每个可能的值还是概率相等！ [记住while循环最前面的'invariant'就是r是随机均匀分布在0..m-1中的。]
对于小 n，拒绝步骤将丢弃大部分 r，但对于小 n（与 N 相比），我们希望不要经常拒绝。相反，对于大 n（与 N 相比），我们可能会期望更频繁地拒绝，但这至少保留了一些我们到目前为止已经吃掉的随机位。我觉得可能有一种方法可以保留更多的 r...但是还没有想到一种简单的方法...如果读取一个随机位的成本很高，它可能是值得尝试找到一个不简单的方法！
FWIW：设置 N = 128 我得到：
FDR: for 100000 values ranges=3.. 15: 389026 bits cost=1.2881
DrMath: for 100000 values ranges=3.. 15: 315815 bits cost=1.0457
FDR: for 100000 values ranges 3.. 31: 476428 bits cost=1.2371
DrMath: for 100000 values ranges 3.. 31: 410195 bits cost=1.0651
FDR: for 100000 values ranges 3.. 63: 568687 bits cost=1.2003
DrMath: for 100000 values ranges 3.. 63: 517674 bits cost=1.0927
FDR: for 100000 values ranges 3..127: 664333 bits cost=1.1727
DrMath: for 100000 values ranges 3..127: 639269 bits cost=1.1284
随着 n 接近 N，单位价值成本上升。