将范围从1-5扩大到1-7
给定一个产生1到5范围内的随机整数的函数，编写一个函数，该函数产生1到7范围内的随机整数。
这相当于亚当罗森菲尔德的解决方案，但对于一些读者来说可能会更清楚些。 它假定rand5（）是一个函数，它返回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()调用rand7() ，以最大化随机性的使用。 也就是说，如果你认为随机性是一种宝贵的资源，我们希望尽可能多地使用它，而不会丢掉任何随机比特。 这个答案也与伊万答案中提出的逻辑有一些相似之处。
随机变量的熵是一个明确的数量。 对于一个具有相同概率（均匀分布）的N个状态的随机变量，熵是log2N。因此， rand5()具有大约2.32193比特的熵，并且rand7()具有大约2.80735比特的熵。 如果我们希望最大化我们对随机性的使用，我们需要使用rand5()每次调用的所有2.32193比特的熵，并将它们应用于生成每次调用rand7()所需的2.80735比特的熵。 那么最基本的限制就是，对rand7()每次调用，我们可以不比log（7）/ log（5）= 1.20906调用rand5() rand7() 。
注意事项：除非另有说明，否则答案中的所有对数将以2为底。 rand5()将假定返回范围[0，4]中的数字，并且rand7()将假定返回范围[ rand7() ]中的数字。 分别调整范围为[1,5]和[1,7]是微不足道的。
那么我们该怎么做呢？ 我们生成一个0到1之间的无限精确的随机实数（假设我们实际上可以计算并存储这样一个无限精确的数字 - 稍后我们会解决这个问题）。 我们可以通过生成基数为5的数字来生成这样一个数字：我们选择随机数0. a 1 a 2 a 3 ...，其中每个数字a i通过调用rand5()来选择。 例如，如果我们的RNG为所有i选择了一个i = 1，那么忽略那个不是非常随机的事实，那对应于实数1/5 + 1/52 + 1/53 + ... = 1/4（几何系列之和）。
好的，所以我们选择了一个0到1之间的随机实数。我现在声称这个随机数是均匀分布的。 直观地说，这很容易理解，因为每个数字都是一致的，数字无限精确。 然而，对此的一个形式化证明涉及更多一些，因为现在我们处理的是连续分布而不是离散分布，所以我们需要证明我们的数字位于区间[ a ， b ]的概率等于该间隔的长度， b - a 。 证明留给读者练习=）。
现在我们有一个从[0，1]范围内统一选择的随机实数，我们需要将它转换为一系列在[ rand7() ]范围内的均匀随机数来生成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次产生10000个随机数，然后测量它们的分布。 只使用整数数学，所以结果是完全正确的。
还要注意这里的数字变得非常大，非常快。 5和7的权力迅速增长。 因此，由于算术运算，在生成大量随机数之后，性能将开始显着降低。 但请记住，我的目标是最大限度地利用随机比特，而不是最大化性能（尽管这是次要目标）。
在这一次运行中，我对rand7() rand5()进行了1次rand7()调用，调用rand7()达到log（7）/ log（5）次数的平均值，达到4个有效数字，结果输出一致。
为了将此代码移植到没有内置任意大整数的语言中，必须将pow5和pow7的值限制为本地整型的最大值 - 如果它们变得太大，然后重置一切并重新开始。 这会增加对rand7() rand5()每次调用rand7() rand5()平均调用rand7() ，但希望它对于32位或64位整数不应增加太多。