如何使用一个随机数生成器构造另一个随机数生成器

有一次在知乎突然看到一个很有趣的问题，

如何用一个1-8随机数生成器制作一个1-7随机数生成器？

还有leetcode的这个问题

用 Rand7() 实现 Rand10()

总体就是讨论如何使用一个随机数生成器构造另一个随机数生成器，并且希望效率比较高，我这里只是提炼一下各位大佬的想法。具体想看各种数学细节的可以看知乎的那个回答。

在此之前，我们先来思考一个比较简单的问题，如何用rand(2)构造rand(4)，这个有同学一看很简单啊，直接让rand(2)产生2次，拼到一起，就得到了一个rand(4)的随机数生成器了。

这样就相当于两次rand(2)结果得到了rand(4),其实再思考一下，我们上边的过程，其实本质上是将多个二进制数字相组合转换为了四进制数字。

那我再来思考一下如何使用rand(4)来构造rand(2)，有同学说这也很简单啊，每次生成一个rand(4)，其实相当于生成了两个rand(2)，把每次生成的rand(4)转化为二进制，就得到了两个rand(2)。这里我们相当于把一个四进制数字转化为了多个二进制数字。

到这里我们已经又了基本的思路，就是进制转换，如果要用rand(m)去构造rand(n)： 1. 如果m>n，那么就将每次生成的一个m进制数字转化为多个n进制数字 2. 如果m<n，那么就将多个生成的n进制数字转化为一个m进制数字

有同学可能说了，有问题啊，上班的rand(4)构造rand(2)，4恰好是2的平方，可以刚好构造，如果让你用rand(2)构造rand(5)呢？这里我们采用一种就简单的方法——丢弃采样。

比如使用rand(8)构造rand(7),最简单的方法也不用什么进制转换，直接调用rand(8),调用结果=7就舍弃，继续调用，直到返回一个符合要求的值即可。这就是丢弃采样。

再来看我们rand(2)生成rand(5)，该怎么操作呢？2位rand(2)最多表示到rand(4)，rand(5)必须3位，那么每次进行三次rand(2)，结果大于等于5就丢弃即可，这么就可以得到一个rand(5)生成器。 用rand(5)去构造rand(2)也是依然，一个5进制数字转换为2进制，是3位，但注意最高位并没有完全利用，所以只能利用后两位，相当于，一个rand(5)可以生成两个rand(2)。

这里我们已经完成了最基本任意随机数生成器的构造。但由于我们采用了丢弃采样，所以依然存在部分的丢弃，如果优化的话，就要尽可能减少这部分的丢弃。下面说一下一种优化思路。

比如我们用rand(2)去生成rand(5)，每次相当于会进行一部分的丢弃，我们可以看到2^7和5^3比较接近，所以我们可以每次调用7次rand(2),相当于得到了3个rand(5)，具体怎么操作呢，每次对于这个7位的二进制串，如果大于等于125就舍弃，否则的话就可以转化为3个5进制的数字，这样就得到了3个rand(5)。这样利用率就大大增加了。