这个答案更像是一个从Rand5函数中获得最大熵的实验。因此，T有点不清楚，几乎可以肯定比其他实现慢得多。

假设0-4为均匀分布，0-6为均匀分布:

public class SevenFromFive
{
  public SevenFromFive()
  {
    // this outputs a uniform ditribution but for some reason including it 
    // screws up the output distribution
    // open question Why?
    this.fifth = new ProbabilityCondensor(5, b => {});
    this.eigth = new ProbabilityCondensor(8, AddEntropy);
  } 

  private static Random r = new Random();
  private static uint Rand5()
  {
    return (uint)r.Next(0,5);
  }

  private class ProbabilityCondensor
  {
    private readonly int samples;
    private int counter;
    private int store;
    private readonly Action<bool> output;

    public ProbabilityCondensor(int chanceOfTrueReciprocal,
      Action<bool> output)
    {
      this.output = output;
      this.samples = chanceOfTrueReciprocal - 1;  
    }

    public void Add(bool bit)
    {
      this.counter++;
      if (bit)
        this.store++;   
      if (counter == samples)
      {
        bool? e;
        if (store == 0)
          e = false;
        else if (store == 1)
          e = true;
        else
          e = null;// discard for now       
        counter = 0;
        store = 0;
        if (e.HasValue)
          output(e.Value);
      }
    }
  }

  ulong buffer = 0;
  const ulong Mask = 7UL;
  int bitsAvail = 0;
  private readonly ProbabilityCondensor fifth;
  private readonly ProbabilityCondensor eigth;

  private void AddEntropy(bool bit)
  {
    buffer <<= 1;
    if (bit)
      buffer |= 1;      
    bitsAvail++;
  }

  private void AddTwoBitsEntropy(uint u)
  {
    buffer <<= 2;
    buffer |= (u & 3UL);    
    bitsAvail += 2;
  }

  public uint Rand7()
  {
    uint selection;   
    do
    {
      while (bitsAvail < 3)
      {
        var x = Rand5();
        if (x < 4)
        {
          // put the two low order bits straight in
          AddTwoBitsEntropy(x);
          fifth.Add(false);
        }
        else
        { 
          fifth.Add(true);
        }
      }
      // read 3 bits
      selection = (uint)((buffer & Mask));
      bitsAvail -= 3;     
      buffer >>= 3;
      if (selection == 7)
        eigth.Add(true);
      else
        eigth.Add(false);
    }
    while (selection == 7);   
    return selection;
  }
}

每次调用Rand5添加到缓冲区的比特数目前是4/5 * 2，所以是1.6。 如果包括1/5的概率值，则增加0.05，因此增加1.65，但请参阅代码中的注释，我不得不禁用它。

调用Rand7消耗的比特数= 3 + 1/8 *(3 + 1/8 *(3 + 1/8 *(… 这是3 + 3/8 + 3/64 + 3/512…大约是3.42

通过从7中提取信息，我每次调用回收1/8*1/7位，大约0.018

这使得每次调用的净消耗为3.4比特，这意味着每一次Rand7调用到Rand5的比率为2.125。最优值应该是2.1。

我可以想象这种方法比这里的许多其他方法都要慢得多，除非调用Rand5的代价非常昂贵(比如调用一些外部熵源)。

假设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

这里我们使用约定的rand(n) -> [0, n - 1]

从我读到的许多答案中，它们要么提供了一致性，要么提供了暂停保证，但不能同时提供(adam rosenfeld的第二个答案可能)。

然而，这样做是可能的。我们基本上有这样的分布:

这给[0-6]上的分布留下了一个漏洞:5和6没有 发生的概率。想象一下，现在我们试图通过移动 概率分布和求和。

事实上，我们可以把初始分布平移1，然后 重复将得到的分布与移位的初始分布相加 2，然后3，以此类推，直到7，不包括在内(我们涵盖了整个范围)。 如下图所示。颜色的顺序，对应 步骤，是蓝色->绿色->青色->白色->品红->黄色->红色。

因为每个插槽由7个移位分布中的5个覆盖(移位从 0到6)，因为我们假设随机数是独立于1的 Ran5()呼叫另一个，我们获得

p(x) = 5 / 35 = 1 / 7       for all x in [0, 6]

这意味着，给定来自ran5()的7个独立随机数，我们可以 计算一个在[0-6]范围内具有均匀概率的随机数。 实际上是ran5()概率 分布甚至不需要均匀，只要样本是均匀的 独立(所以每次试验的分布保持不变) 同样，这也适用于5和7之外的其他数字。

这为我们提供了以下python函数:

def rand_range_transform(rands):
    """
    returns a uniform random number in [0, len(rands) - 1]
    if all r in rands are independent random numbers from the same uniform distribution
    """
    return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic

可以这样使用:

rand5 = lambda : random.randrange(5)

def rand7():
    return rand_range_transform([rand5() for _ in range(7)])

如果我们调用rand7() 70000次，我们可以得到:

max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0:  10019
1:  10016
2:  10071
3:  10044
4:  9775
5:  10042
6:  10033

这很好，尽管远非完美。事实上，我们的一个假设是 在这个实现中很可能是false:我们使用一个PRNG，因此，结果 的值依赖于上一个结果。

也就是说，使用一个真正随机的数字来源，输出也应该是 真正随机的。这个算法在任何情况下都终止。

但这是有代价的:我们需要为一个rand7()调用7次rand5() 调用。

function rand7() {
    while (true) { //lowest base 5 random number > 7 reduces memory
        int num = (rand5()-1)*5 + rand5()-1;
    if (num < 21)  // improves performance
        return 1 + num%7;
    }
}

Python代码:

from random import randint
def rand7():
    while(True):
        num = (randint(1, 5)-1)*5 + randint(1, 5)-1
        if num < 21:
                return 1 + num%7

100000次运行的测试分布:

>>> rnums = []
>>> for _ in range(100000):
    rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}

对于范围[1,5]到[1,7]，这相当于用一个5面骰子滚动一个7面骰子。

然而，如果不“浪费”随机性(或者在最坏的情况下永远运行)，就无法做到这一点，因为7的所有质因数(即7)都不能整除5。因此，最好的方法是使用拒绝抽样来获得任意接近于不“浪费”随机性的结果(例如，将多个5面骰子摇到5^n“足够接近”7的幂)。这个问题的解决方案已经在其他答案中给出了。

更一般地说，用p面骰子掷k面骰子的算法将不可避免地“浪费”随机性(并且在最坏的情况下永远运行)，除非“每个质数能除k也能除p”，根据B. Kloeckner的“用骰子模拟骰子”中的引理3。例如，举一个更实际的例子，p是2的幂，k是任意的。在这种情况下，这种“浪费”和无限的运行时间是不可避免的，除非k也是2的幂。

除了我的第一个答案，我想再补充一个答案。这个答案试图最小化每次调用rand7()时对rand5()的调用次数，以最大限度地利用随机性。也就是说，如果你认为随机性是一种宝贵的资源，我们就会尽可能多地利用它，而不丢弃任何随机比特。这个答案也与伊万的回答中的逻辑有一些相似之处。

The entropy of a random variable is a well-defined quantity. For a random variable which takes on N states with equal probabilities (a uniform distribution), the entropy is log2 N. Thus, rand5() has approximately 2.32193 bits of entropy, and rand7() has about 2.80735 bits of entropy. If we hope to maximize our use of randomness, we need to use all 2.32193 bits of entropy from each call to rand5(), and apply them to generating 2.80735 bits of entropy needed for each call to rand7(). The fundamental limit, then, is that we can do no better than log(7)/log(5) = 1.20906 calls to rand5() per call to rand7().

附注:除非另有说明，否则此答案中的所有对数都将以2为底。Rand5()将被假定为返回范围[0,4]的数字，rand7()将被假定为返回范围[0,6]的数字。分别将范围调整为[1,5]和[1,7]是很简单的。

So how do we do it? We generate an infinitely precise random real number between 0 and 1 (pretend for the moment that we could actually compute and store such an infinitely precise number -- we'll fix this later). We can generate such a number by generating its digits in base 5: we pick the random number 0.a1a2a3..., where each digit ai is chosen by a call to rand5(). For example, if our RNG chose ai = 1 for all i, then ignoring the fact that that isn't very random, that would correspond to the real number 1/5 + 1/52 + 1/53 + ... = 1/4 (sum of a geometric series).

Ok, so we've picked a random real number between 0 and 1. I now claim that such a random number is uniformly distributed. Intuitively, this is easy to understand, since each digit was picked uniformly, and the number is infinitely precise. However, a formal proof of this is somewhat more involved, since now we're dealing with a continuous distribution instead of a discrete distribution, so we need to prove that the probability that our number lies in an interval [a, b] equals the length of that interval, b - a. The proof is left as an exercise for the reader =).

现在我们有一个从范围[0,1]中均匀选择的随机实数，我们需要将它转换为范围[0,6]中的一系列均匀随机数，以生成rand7()的输出。我们怎么做呢?与我们刚才所做的正好相反——我们将其转换为以7为底的无限精确小数，然后每个以7为底的数字将对应于rand7()的一个输出。

以前面的例子为例，如果rand5()产生无限的1流，那么我们的随机实数将是1/4。将1/4换算成7为底，我们得到了无穷大小数0.15151515…，因此我们将产生作为输出1,5,1,5,1,5，等等。

好了，我们有了主要的思想，但还有两个问题:我们实际上无法计算或存储一个无限精确的实数，那么我们如何处理它的有限部分呢?第二，我们怎么把它换算成7进制呢?

将0到1之间的数字转换为以7为底的一种方法如下:

乘以7 结果的积分部分是下一个以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的幂增长很快。因此，在生成大量随机数后，由于大算术，性能将开始明显下降。但请记住，我的目标是最大化随机位的使用，而不是最大化性能(尽管这是次要目标)。

在一次运行中，我对rand5()进行了12091次调用，对rand7()进行了10000次调用，实现了log(7)/log(5)次调用的最小值，平均为4位有效数字，结果输出是均匀的。

为了将这段代码移植到一种没有内置任意大整数的语言中，您必须将pow5和pow7的值限制为本地整型类型的最大值——如果它们变得太大，则重置所有内容并重新开始。这将使每次调用rand7()时对rand5()的平均调用次数略有增加，但希望即使对于32或64位整数也不会增加太多。