在我的嵌入式项目中，我有一个处理任意长度整数的biginteger类。我希望能够生成一个介于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不为零，那么它将是无效的，仅仅重新生成那个字节永远不会使它有效。但仅仅将其强制设置为零似乎也是错误的。
答案是，通常不可能在常数时间内生成[0,n)中的随机无偏整数。一个值得注意的例外是当随机数的来源产生无偏随机比特并且n是2的幂时。
例如，假设我们有一个"true"随机发生器，可以产生无偏的随机比特。那么，除非n是2的幂，否则只有两种可能的方法:
- 它可以使用模化(或Lemire的乘移化)。这将在恒定时间内运行，但会引入偏差(某些数字比其他数字更有可能生成)。
- 可采用拒绝采样。这不会引入偏差，但在最坏的情况下可以永远运行(即使它具有预期的常数时间复杂度)。许多种类的算法都属于这一类，包括模约简，然后是拒绝步骤(如果
n不是2的幂，这是必要的)，以及快速掷骰子(使用随机比特)。
(关于这两种算法的调查，请参阅我关于整数生成算法的注释。关于快速掷骰子的实现，请参阅我的另一个答案。
在这个意义上，Knuth和Yao在1976年表明，任何仅使用随机比特产生具有给定概率的随机整数的算法都可以表示为二叉树，其中随机比特表示遍历树的方式，每个叶子(端点)对应于一个结果。(Knuth和Yao，《非均匀随机数生成的复杂性》，《算法与复杂性》，1976年)在这种情况下，[0,n)中的每个整数出现的概率为1/n。如果1/n有一个非终止的二叉展开(如果n不是2的幂)，这个二叉树必然是-
- 有一个"infinite"深度,或者
- 包括"rejection"树末端的叶子，
在这两种情况下，算法都不会在常数时间内运行。
模或类似约简相当于一个二叉树，其中拒绝叶被标记的结果取代——但由于可能的结果比拒绝叶更多，只有一些结果可以取代拒绝叶，从而引入偏差。如果你在一定次数的迭代后停止拒绝，同样的二叉树——以及同样的偏差——就会产生。(参见L. Devroye的非均匀随机变量生成第15章，1986)
因此:通常，整数生成器可以是无偏或常数时间，但不能同时是。
如果你不能容忍永远运行的最坏情况，那么你唯一能做的就是设置一个固定的最大拒绝数或使用减少，这两种方法都会引入偏差。但是，这种偏差可能可以忽略不计，这取决于您的应用程序(例如，如果算法"失败"的几率;对于应用程序而言，与"成功"的机会相比可以忽略不计)。随机整数生成还有安全方面的问题，这个问题太复杂了，无法在本文中讨论。
如果您的任意最大值是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的无偏结果，但这是一个较小的问题来解决。