JAVA均匀生成随机数

公式推导

假如有一个函数rand2()会均匀生成[1,2]的随机数，现在想要实现一个rand4()的函数，第一次接触该类问题时，第一反应是如下所示：

rand2() + rand2() = ? ==> [2,4]
   1    +   1     = 2
   1    +   2     = 3
   2    +   1     = 3
   2    +   2     = 4

// 为了把生成随机数的范围规约成[1,n]，于是在上一步的结果后减1
(rand2()-1) + rand2() = ? ==> [1,3]
   0       +   1     = 1
   0       +   2     = 2
   1       +   1     = 2
   1       +   2     = 3

会发现生成的数字不是等概率的，造成这种情况的原因也很明显，有些数字是可以通过几个组合得来，有的只能通过一种组合得来

若我们把(rand2()-1)乘以2，则会得到

(rand2()-1) × 2 + rand2() = ?
   0            +   1     = 1
   0            +   2     = 2
   2            +   1     = 3
   2            +   2     = 4

得到的结果恰好是等概率的。我们可以通过这种方法实现rand2()->rand4()

我们再举个例子：有两个均匀随机函数rand9()和rand7()，a=(rand9-1)*7，b = rand7，result = a+b

则能得到下列表格的结果：

a\b	1	2	3	4	5	6	7
0	1	2	3	4	5	6	7
7	8	9	10	11	12	13	14
14	15	16	17	18	19	20	21
21	22	23	24	25	26	27	28
28	29	30	31	32	33	34	35
35	36	37	38	39	40	41	42
42	43	44	45	46	47	48	49
49	50	51	52	53	54	55	56
56	57	58	59	60	61	62	63

可以看到这样也可以均匀随机的生成[1,63]的随机数，则可以得到这样的一个规律：

已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数
即实现了 rand_X*Y()

公式：

LC题目+优化

题目

再来看看Leetcode上的这一题：470. 用 Rand7() 实现 Rand10()

要实现rand10()，就需要先实现rand_N()，并且保证N大于10且是10的倍数。这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。

rand_N()的实现方法可以通过上面推导出来的规律得到：

(rand7()-1) × 7 + rand7() ==> rand49()

但是这样实现的N不是10的倍数，这该怎么处理？这里就涉及到了“拒绝采样”的知识了，也就是说，如果某个采样结果不在要求的范围内，则丢弃它。基于上面的这些分析，再回头看下面的代码，想必是不难理解了。

class Solution extends SolBase {
    public int rand10() {
        while(true) {
            int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数
            if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数
        }
    }
}

优化

根据上面的分析，我们已经知道(rand7() - 1) * 7 + rand7() 等概率生成[1,49]范围的随机数。而由于我们需要的是10的倍数，因此，需要舍弃掉[41, 49]这9个数。优化的点就始于——我们能否利用这些范围外的数字，以减少丢弃的值，提高命中率总而提高随机数生成效率。

当生成的随机数x在[41,49]时，我们拒绝采样这一部分，而舍弃的这一部分我们可以得到[1,9]的均匀随机数，我们将这一随机数通过上面的处理后就可以得到[1,63]的随机数，若这次生成的随机数在[61,63]时，我们也拒绝采样这一部分，而舍弃的这一部分我们可以得到[1,3]的均匀随机数，我们将这一随机数通过上面的处理后就可以得到[1,21]的随机数，若这次生成的随机数为21，则我们拒绝采样21，但是舍弃的21只能得到1这一个随机数，没有用处，所以我们只能重新生成[1,49]的随机数。代码如下：

class Solution extends SolBase {
    public int rand10() {
        while(true){
            int a = (rand7()-1)*7;
            int b = rand7();
            int num = a+b;
            if(num<=40)return num%10+1;
            a = (num-40-1)*7;
            b = rand7();
            num = a+b;
            if(num<=60)return num%10+1;
            a = (num-60-1)*7;
            b = rand7();
            num = a+b;
            if(num<=20)return num%10+1;
        }
    }
}

执行效率也比上面快了许多

保留的数字范围可以通过下面这个公式得到：

假设有rand_X，想得到rand_Y，
a = (rand_X()-1)*Y，b = rand_X();
则保留范围为：

返回的数字为：

参考题解链接：从最基础的讲起如何做到均匀的生成随机数