如何在恒定时间内生成无偏随机 bigint
How to generate an unbiased random bigint in constant time
在我的嵌入式项目中，我有一个处理任意长度整数的双整数 class。我希望能够生成一个介于 0 和任意数字之间的随机 bigint。假设我有一个高质量的随机字节源。
我见过的所有实现基本上都做同样的事情：
- 生成一个字节数正确的大数字，
- 如果大于max，重新生成
我看到这个实现的问题是它可能需要很长时间。想象一下 max = 2^2049-1 =(01 FF .. FF)。该算法将生成 257 个字节，然后检查最高有效字节是 <=1。所以它有 254/256 的机会生成一个全新的 257 字节数字。在（诚然不太可能）最坏的情况下，这个循环可能会持续几分钟或几年。
我的问题是：
在生成的数字太大的情况下，有没有办法保留我已经生成的大部分字节？
仅重新生成最高有效字节是否有效，还是会引入偏差？将结果右移一位怎么样？
有什么方法可以使时间具有确定性，同时又能避免偏差？
--
另一种边缘情况：max = 2^2048 + 1 = (01 00 .. 01) 在这种情况下，如果剩余字节为 0，则最高有效字节可以为非零，后跟 00 或 01。所以大多数时候，如果 MSB 不为零，那么它将无效，并且仅仅重新生成该字节永远不会使其有效。但是强制将其设置为零似乎也是错误的。
如果您的任意最大数是 2 减 1 的幂，则可以使用随机位源（例如抛硬币）来填充这些位。这给出了一个均匀分布的数字。您可以使用高质量的 RNG 以 32 位或 64 位为一组生成位，并无偏差地截断最后一个字。
现在，如果您的任意最大数不是 2 减 1 的幂，请使用上述技术在 0..1 范围内创建统一分数。分数使用的位数越多，结果的偏差就越小。
例如，调用任意最大数 M，选择一个 n 以便
2^n >> M /* 2^n is much greater than M */
现在，你的随机数是
M * (rand(2^n) / 2^n)
其中 rand 是上面第一段中描述的过程。
随机数生成器创建具有整数位数的随机数。如果数字在统计上确实是随机的，那么每一位都独立于其他位，您可以使用或丢弃它们的任意组合。对于您的示例，您可以简单地丢弃 7 位并获得一个无偏差的数字。
对于不是 2 的幂的范围，您可以分解范围的大小并为每个范围获取一个随机数，然后将它们合并。如果我们假设一个函数 randint(n) 提供一个介于 0 和 n-1 之间的无偏随机数，则一般公式为：
(((randint(A) * B + randint(B)) * C + randint(C)) * D + randint(D)) ...
例如，如果您的范围是 0-10^616-1，您可以将其计入 5^616*2^616。
rand_10_616 = randint(5^616) * 2^616 + randint(2^616)
显然，您仍然无法获得 5^616 的无偏结果，但这是一个需要解决的小问题。
答案是一般不可能在常数时间内生成[0,n)内的随机无偏整数。一个值得注意的例外是随机数源产生无偏随机位并且 n 是 2 的幂。
例如，假设我们有一个“真正的”随机生成器并且可以生成无偏随机位。那么，除非n是2的幂，否则只有两种可能的处理方式：
- 它可以使用模约简（或 Lemire 的乘法再移位约简）。这将 运行 在常数时间内，但会引入偏差（一些数字比其他数字更容易生成）。
- 可以使用拒绝抽样。这不会引入偏差，但在最坏的情况下可以永远 运行 （即使它具有预期的恒定时间复杂度）。许多算法都属于这一类，包括模数约简和拒绝步骤（如果
n 不是 2 的幂，这是必需的），以及 Fast Dice Roller（使用随机位） .
（请参阅我在 integer generating algorithms for a survey of both kinds of algorithms. For a Fast Dice Roller implementation, see another answer of mine 上的注释。）
在这个意义上，Knuth 和 Yao 在 1976 年表明，任何仅使用随机位以给定概率生成随机整数的算法都可以表示为二叉树，其中随机位指示遍历树的方式每个叶子（端点）对应一个结果。 （Knuth 和 Yao，“非均匀随机数生成的复杂性”，算法和复杂性，1976 年。）在这种情况下，[0, n) 中的每个整数都可以以 1/n 的概率出现。如果 1/n 有一个不终止的二叉展开式（如果 n 不是 2 的幂就是这种情况），这个二叉树必然是——
- 具有“无限”深度，或者
- 在树的末端包含“拒绝”叶子，
并且在任何一种情况下，算法都不会 运行 在常数时间内。
Modulo 或类似的归约等同于二叉树，其中拒绝叶被标记的结果替换——但是由于可能的结果比拒绝叶多，所以只有一些结果可以代替拒绝叶，引入偏见。如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树和相同类型的偏差。 （另见 L. Devroye，1986 年 非均匀随机变量生成 的第 15 章。）
因此：一般来说，整数生成器可以或者无偏或者常数-时间，但不是两者。
如果您不能永远容忍 运行ning 的最坏情况，那么您唯一能做的就是设置一个固定的最大拒绝次数或使用减少次数，这两者都会引入偏差。但是，根据您的应用程序，这种偏差可能可以忽略不计（例如，如果算法“失败”的可能性与其“成功”的可能性相比可以忽略不计，对于应用程序的目的）。随机整数生成还有安全方面的问题，太复杂了，无法在此答案中讨论。
在我的嵌入式项目中，我有一个处理任意长度整数的双整数 class。我希望能够生成一个介于 0 和任意数字之间的随机 bigint。假设我有一个高质量的随机字节源。
我见过的所有实现基本上都做同样的事情：
- 生成一个字节数正确的大数字，
- 如果大于max，重新生成
我看到这个实现的问题是它可能需要很长时间。想象一下 max = 2^2049-1 =(01 FF .. FF)。该算法将生成 257 个字节，然后检查最高有效字节是 <=1。所以它有 254/256 的机会生成一个全新的 257 字节数字。在（诚然不太可能）最坏的情况下，这个循环可能会持续几分钟或几年。
我的问题是：
在生成的数字太大的情况下，有没有办法保留我已经生成的大部分字节？
仅重新生成最高有效字节是否有效，还是会引入偏差？将结果右移一位怎么样？
有什么方法可以使时间具有确定性，同时又能避免偏差？
--
另一种边缘情况：max = 2^2048 + 1 = (01 00 .. 01) 在这种情况下，如果剩余字节为 0，则最高有效字节可以为非零，后跟 00 或 01。所以大多数时候，如果 MSB 不为零，那么它将无效，并且仅仅重新生成该字节永远不会使其有效。但是强制将其设置为零似乎也是错误的。
如果您的任意最大数是 2 减 1 的幂，则可以使用随机位源（例如抛硬币）来填充这些位。这给出了一个均匀分布的数字。您可以使用高质量的 RNG 以 32 位或 64 位为一组生成位，并无偏差地截断最后一个字。
现在，如果您的任意最大数不是 2 减 1 的幂，请使用上述技术在 0..1 范围内创建统一分数。分数使用的位数越多，结果的偏差就越小。
例如，调用任意最大数 M，选择一个 n 以便
2^n >> M /* 2^n is much greater than M */
现在，你的随机数是
M * (rand(2^n) / 2^n)
其中 rand 是上面第一段中描述的过程。
随机数生成器创建具有整数位数的随机数。如果数字在统计上确实是随机的，那么每一位都独立于其他位，您可以使用或丢弃它们的任意组合。对于您的示例，您可以简单地丢弃 7 位并获得一个无偏差的数字。
对于不是 2 的幂的范围，您可以分解范围的大小并为每个范围获取一个随机数，然后将它们合并。如果我们假设一个函数 randint(n) 提供一个介于 0 和 n-1 之间的无偏随机数，则一般公式为：
(((randint(A) * B + randint(B)) * C + randint(C)) * D + randint(D)) ...
例如，如果您的范围是 0-10^616-1，您可以将其计入 5^616*2^616。
rand_10_616 = randint(5^616) * 2^616 + randint(2^616)
显然，您仍然无法获得 5^616 的无偏结果，但这是一个需要解决的小问题。
答案是一般不可能在常数时间内生成[0,n)内的随机无偏整数。一个值得注意的例外是随机数源产生无偏随机位并且 n 是 2 的幂。
例如，假设我们有一个“真正的”随机生成器并且可以生成无偏随机位。那么，除非n是2的幂，否则只有两种可能的处理方式：
- 它可以使用模约简（或 Lemire 的乘法再移位约简）。这将 运行 在常数时间内，但会引入偏差（一些数字比其他数字更容易生成）。
- 可以使用拒绝抽样。这不会引入偏差，但在最坏的情况下可以永远 运行 （即使它具有预期的恒定时间复杂度）。许多算法都属于这一类，包括模数约简和拒绝步骤（如果
n不是 2 的幂，这是必需的），以及 Fast Dice Roller（使用随机位） .
（请参阅我在 integer generating algorithms for a survey of both kinds of algorithms. For a Fast Dice Roller implementation, see another answer of mine 上的注释。）
在这个意义上，Knuth 和 Yao 在 1976 年表明，任何仅使用随机位以给定概率生成随机整数的算法都可以表示为二叉树，其中随机位指示遍历树的方式每个叶子（端点）对应一个结果。 （Knuth 和 Yao，“非均匀随机数生成的复杂性”，算法和复杂性，1976 年。）在这种情况下，[0, n) 中的每个整数都可以以 1/n 的概率出现。如果 1/n 有一个不终止的二叉展开式（如果 n 不是 2 的幂就是这种情况），这个二叉树必然是——
- 具有“无限”深度，或者
- 在树的末端包含“拒绝”叶子，
并且在任何一种情况下，算法都不会 运行 在常数时间内。
Modulo 或类似的归约等同于二叉树，其中拒绝叶被标记的结果替换——但是由于可能的结果比拒绝叶多，所以只有一些结果可以代替拒绝叶，引入偏见。如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树和相同类型的偏差。 （另见 L. Devroye，1986 年 非均匀随机变量生成 的第 15 章。）
因此：一般来说，整数生成器可以或者无偏或者常数-时间，但不是两者。
如果您不能永远容忍 运行ning 的最坏情况，那么您唯一能做的就是设置一个固定的最大拒绝次数或使用减少次数，这两者都会引入偏差。但是，根据您的应用程序，这种偏差可能可以忽略不计（例如，如果算法“失败”的可能性与其“成功”的可能性相比可以忽略不计，对于应用程序的目的）。随机整数生成还有安全方面的问题，太复杂了，无法在此答案中讨论。