给定一个产生 1 到 5 范围内的随机整数的函数，编写一个产生 1 到 7 范围内的随机整数的函数。
这等效于 Adam Rosenfield 的解决方案，但对于某些读者而言可能更清楚一些。假定 rand5（）是一个函数，该函数返回 1 到 5 之间（含 1 和 5）的统计随机整数。
int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}它是如何工作的？这样想：想象一下将这个二维阵列打印在纸上，将其固定在飞镖板上，然后随机向其投掷飞镖。如果您命中非零值，则它是 1 到 7 之间的统计随机值，因为有相等数量的非零值可供选择。如果击中零，则继续投掷飞镖，直到击中非零为止。这就是这段代码的作用：i 和 j 索引在飞镖板上随机选择一个位置，如果结果不好，我们将继续扔飞镖。
就像亚当说的那样，这在最坏的情况下可以永远持续下去，但从统计上讲，最坏的情况永远不会发生。 :)
没有（完全正确）的解决方案会在恒定的时间内运行，因为 1/7 是以 5 为底的无限小数。一个简单的解决方案是使用拒绝采样，例如：
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7预期的运行时为循环的 25/21 = 1.19 迭代，但永远循环的可能性极小。
除了第一个答案外，我还要添加另一个答案。 rand7()每次调用的rand5()的调用次数最小化，以最大程度地利用随机性。也就是说，如果您认为随机性是一种宝贵的资源，那么我们希望在不丢弃任何随机位的情况下尽可能多地使用随机性。 此答案也与 Ivan 答案中提出的逻辑有些相似之处。
随机变量的熵是一个定义明确的量。对于这需要在 N 个随机变量具有相等概率（均匀分布）状态，熵为 log 2 N. 因此， rand5()具有熵的大约 2.32193 位，并且rand7()具有大约熵 2.80735 比特。如果我们希望最大程度地利用随机性，则需要使用每次对rand5() rand7()每次调用所需的 2.80735 位熵。 rand7()每次调用都比 log（7）/ log（5）= 1.20906 对rand5()调用更好。
旁注：除非另有说明，否则此答案中的所有对数均以 2 为底。 rand5()返回范围为 [0，4] 的数字，并且rand7()返回范围为 [0，6] 的数字。将范围分别调整为 [1，5] 和 [1，7] 是微不足道的。
那么我们该怎么做呢？我们会生成一个介于 0 和 1 之间的无限精确的随机实数（假装我们可以实际计算和存储这样一个无限精确的数，稍后再解决）。我们可以通过在基体 5 产生其数字生成这样的数：我们选择该随机数为 0。 a 1 a 2 a 3 ...，其中每个数字一个i是通过调用选择rand5()例如，如果我们的 RNG 为所有i i = 1，则忽略了它不是非常随机的事实，这将对应于实数 1/5 + 1/5 2 + 1/5 3 +.。 。= 1/4（一个几何级数的和）。
好的，所以我们选择了一个介于 0 和 1 之间的随机实数。我现在声称这样一个随机数是均匀分布的。直观地讲，这很容易理解，因为每个数字都是统一选取的，并且数字是无限精确的。但是，对此的正式证明有些复杂，因为现在我们处理的是连续分布而不是离散分布，因此我们需要证明我们的数字位于区间 [ a ， b ] 中的概率等于该间隔的长度， b - a 。证明留给读者练习）。
现在我们已经从 [0，1] 范围内均匀选择了一个随机实数，我们需要将其转换为 [ rand7()的输出。我们如何做到这一点？与我们所做的恰好相反 - 我们将其转换为以 7 为底的无限精确的十进制数，然后每个以 7 为底的数字将对应rand7()一个输出。
以前面的例子为例，如果我们的rand5()产生一个无限的 1，那么我们的随机实数将是 1/4。将 1/4 转换为基数 7，我们得到无穷小数 0.15151515 ...，因此我们将产生输出 1、5、1、5、1、5 等。
好的，所以我们有了主要思想，但是还有两个问题：我们实际上无法计算或存储无限精确的实数，那么如何只处理其中的有限部分呢？其次，我们如何实际将其转换为基数 7？
我们可以将 0 到 1 之间的数字转换为以 7 为底的一种方法如下：
为了解决无限精度的问题，我们计算了部分结果，并且还存储了结果的上限。也就是说，假设我们rand5() ，并且两次都返回 1。到目前为止，我们生成的数字是 0.11（以 5 为底）。 rand5()的无限次调用的其余部分产生什么，我们生成的随机实数永远不会大于 0.12：0.11≤0.11xyz ... <0.12 始终是正确的。
因此，跟踪当前的数字以及它可能取得的最大值，我们将两个数字都转换为基数 7。如果它们在前k位一致，那么我们可以安全地输出后k位 - 不管以 5 为基数的无限流是什么，它们将永远不会影响以 7 为基数的表示形式k
这就是算法 - 生成rand7()的下一个输出，我们只生成所需数量的rand5()位数，以确保我们确定地知道随机实数转换中的下一个位数以 7. 为基础。这是一个带有测试工具的 Python 实现：
import random
rand5_calls = 0
def rand5():
global rand5_calls
rand5_calls += 1
return random.randint(0, 4)
def rand7_gen():
state = 0
pow5 = 1
pow7 = 7
while True:
if state / pow5 == (state + pow7) / pow5:
result = state / pow5
state = (state - result * pow5) * 7
pow7 *= 7
yield result
else:
state = 5 * state + pow7 * rand5()
pow5 *= 5
if __name__ == '__main__':
r7 = rand7_gen()
N = 10000
x = list(next(r7) for i in range(N))
distr = [x.count(i) for i in range(7)]
expmean = N / 7.0
expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))
print '%d TRIALS' % N
print 'Expected mean: %.1f' % expmean
print 'Expected standard deviation: %.1f' % expstddev
print
print 'DISTRIBUTION:'
for i in range(7):
print '%d: %d (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
print
print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)请注意， rand7_gen()返回一个生成器，因为它具有涉及将数字转换为基数 7 的内部状态。测试工具调用next(r7)来产生 10000 个随机数，然后测量它们的分布。仅使用整数数学，因此结果完全正确。
还要注意，这里的数字变得非常大，非常快。 5 和 7 的幂快速增长。因此，由于使用 bignum 算法，在生成大量随机数后性能将开始显着下降。但是请记住，我的目标是最大化随机位的使用，而不是最大化性能（尽管这是次要目标）。
在这方面的一个来看，我提出 12091 调用rand5()为 10000 个调用rand7()实现了最小的日志（7）/ 日志（5）调用平均至 4 个显著数字，并且所得到的输出是均匀的。
为了将此代码移植到没有内置任何大整数的语言，您必须将pow5和pow7的值限制为本机整数类型的最大值 - 如果它们太大，然后重置所有内容并重新开始。 rand7() rand5()每次调用的平均调用次数增加很少，但是希望即使对于 32 位或 64 位整数，也不应增加太多。