这相当于Adam Rosenfield的解决方案，但对一些读者来说可能更清楚一些。它假设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;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

就像亚当说的，在最坏的情况下，它可以一直运行下去，但从统计上看，最坏的情况永远不会发生。：）

假设rand(n)在这里表示“从0到n-1均匀分布的随机整数”，下面是使用Python的randint的代码示例，它具有这种效果。它只使用randint(5)和常量来产生randint(7)的效果。其实有点傻

from random import randint
sum = 7
while sum >= 7:
    first = randint(0,5)   
    toadd = 9999
    while toadd>1:
        toadd = randint(0,5)
    if toadd:
        sum = first+5
    else:
        sum = first

assert 7>sum>=0 
print sum

什么是简单的解决方案?(rand5() + rand5()) % 7 + 1 减少内存使用或在较慢的CPU上运行的有效解决方案是什么?是的，这是有效的，因为它只调用rand5()两次，空间复杂度为O(1)

考虑rand5()给出从1到5(包括)的随机数。 (1 + 1) % 7 + 1 = 3 (1 + 2) % 7 + 1 = 4 (1 + 3) % 7 + 1 = 5 (1 + 4) % 7 + 1 = 6 (1 + 5) % 7 + 1 = 7

(2 + 1) % 7 + 1 = 4 (2 + 2) % 7 + 1 = 5 (2 + 3) % 7 + 1 = 6 (2 + 4) % 7 + 1 = 7 (2 + 5) % 7 + 1 = 1 .

(5 + 1) % 7 + 1 = 7 (5 + 2) % 7 + 1 = 1 (5 + 3) % 7 + 1 = 2 (5 + 4) % 7 + 1 = 3 (5 + 5) % 7 + 1 = 4 .

等等

就是这样，均匀分布，零rand5调用。

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

需要事先播种。

在php中

function rand1to7() {
    do {
        $output_value = 0;
        for ($i = 0; $i < 28; $i++) {
            $output_value += rand1to5();
        }
    while ($output_value != 140);
    $output_value -= 12;
    return floor($output_value / 16);
}

循环生成16到127之间的随机数，除以16生成1到7.9375之间的浮点数，然后舍入得到1到7之间的整数。如果我没记错的话，得到7个结果中的任何一个的概率都是16/112。

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

与选定的解决方案不同，该算法将在常数时间内运行。然而，它对rand5的调用比所选解决方案的平均运行时间多2次。

请注意，这个生成器并不完美(数字0比任何其他数字都有0.0064%的可能性)，但对于大多数实际目的，保证恒定的时间可能比这种不准确性更重要。

解释

这个解源于数字15624能被7整除的事实，因此，如果我们可以随机且均匀地生成从0到15624的数字，然后对7取余，我们就可以得到一个近乎均匀的rand7生成器。将rand5滚动6次，将0到15624之间的数字统一生成，并使用这些数字组成以5为基数的数字，如下所示:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

mod 7的属性允许我们稍微简化一下方程:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

So

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

就变成了

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

理论

15624这个数字不是随机选择的，而是可以用费马小定理来发现的，该定理指出，如果p是质数，那么

a^(p-1) = 1 mod p

这就得到，

(5^6)-1 = 0 mod 7

(5^6)-1等于

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

这是一个以5为底的数，因此我们可以看到，这种方法可以用于从任何随机数发生器到任何其他随机数发生器。尽管在使用指数p-1时总是会引入对0的小偏差。

为了更准确地推广这种方法，我们可以有这样一个函数:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)