random - 如何在恒定时间内生成无偏随机 bigint

Question

在我的嵌入式项目中，我有一个处理任意长度整数的 biginteger 类。我希望能够生成一个介于 0 和任意数字之间的随机 bigint。假设我有一个高质量的随机字节源。

我见过的所有实现基本上都做同样的事情:

1. 生成一个字节数正确的大数，
2. 如果大于max，重新生成。

我看到这个实现的问题是它可能需要很长时间。想象一下 max = 2^2049-1 =( 01 FF .. FF )。该算法将生成 257 个字节，然后检查最高有效字节是 <=1 .所以它有 254/256 的机会生成一个全新的 257 字节数字。在(诚然不太可能)最坏的情况下，此循环可能会持续几分钟或几年。

我的问题是:
在生成的数字太大的情况下，有没有办法保留我已经生成的大部分字节？
仅重新生成最高有效字节是否有效，还是会引入偏差？将结果右移一位怎么样？

有什么方法可以使时间具有确定性，同时仍能避免偏差？

--

另一个极端情况:max = 2^2048 + 1 = ( 01 00 .. 01 ) 在这种情况下，如果其余字节为 0 后跟 00，则最高有效字节可以为非零字节或 01 .所以大多数时候，如果 MSB 不为零，那么它将无效，并且仅仅重新生成该字节永远不会使其有效。但仅仅强制将其设置为零似乎也是错误的。

Answer 1

答案是一般不可能在常数时间内生成[0, n) 中的随机无偏整数。一个值得注意的异常(exception)是当随机数源产生无偏随机位并且 n 是 2 的幂时。

例如，假设我们有一个“真正的”随机生成器并且可以生成无偏随机位。然后，除非 n 是 2 的幂，否则只有两种可能的方法进行:

• 它可以使用模数缩减(或 Lemire 的乘法然后移位缩减)。这将在恒定时间内运行，但会引入偏差(一些数字比其他数字更有可能生成)。
• 它可以使用拒绝抽样。这不会引入偏差，但在最坏的情况下可以永远运行(即使它具有预期的恒定时间复杂度)。许多算法都属于这一类，包括模数约简和拒绝步骤(如果 n 不是 2 的幂，这是必需的)，以及 Fast Dice Roller (使用随机位)。

(请参阅我关于 integer generating algorithms 的注释以了解对这两种算法的调查。对于 Fast Dice Roller 实现，请参阅 another answer of mine。)

从这个意义上讲，Knuth 和 Yao 在 1976 年表明，任何仅使用随机位生成具有给定概率的随机整数的算法都可以表示为二叉树，其中随机位指示遍历树的方式和每个叶(端点)对应于一个结果。 (Knuth 和 Yao，“非均匀随机数生成的复杂性”，算法和复杂性，1976 年。)在这种情况下，[0, n) 中的每个整数都可以以 1/n 的概率出现。如果 1/n 有一个不终止的二进制扩展(如果 n 不是 2 的幂就是这种情况)，这个二叉树必然是——

• 有一个“无限”的深度，或者
• 在树的末端包含“拒绝”叶子，

无论哪种情况，算法都不会在恒定时间内运行。

模数或类似的归约等同于二叉树，其中拒绝叶被标记的结果替换——但由于可能的结果比拒绝叶多，所以只有部分结果可以代替拒绝叶，从而引入偏差.如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树和相同类型的偏差。 (另请参阅 L. Devroye 于 1986 年出版的 Non-Uniform Random Variate Generation 的第 15 章。)

因此:一般来说，整数生成器可以是无偏或恒定时间的，但不能两者兼而有之。

如果您不能容忍永远运行的最坏情况，那么您唯一能做的就是设置一个固定的最大拒绝次数或使用减少次数，这两者都会引入偏差。但是，根据您的应用程序，这种偏差可能可以忽略不计(例如，如果算法“失败”的可能性与其“成功”的可能性相比可以忽略不计，对于应用程序的目的)。随机整数生成也有安全方面的问题，这些问题太复杂了，无法在此答案中讨论。