本文讨论从一个已知随机数生成器产生另一个随机数生成器的算法问题。
已知从1-10的随机数生成函数random10()，问如何生成1-20的随机数生成函数。
20是10的两倍，我们使用两个random10()，生成一次1-10的随机数；然后再调用random10()函数一次，并把其生成的随机数除2取余，这个余或者是0或者是1，根据这个0还是1映射第一个random10()生成的随机数在1-10区间，还是11-20区间。
int random20() {
return random10() + 10 * (random10()%2);
}
这个函数有限制的条件：
目标随机函数的范围必须是原随机函数的倍数，否则随机数取余的时候会不不均匀，即原函数范围是1..N，那么目标函数必须是1..M(M=N*K)(K是正整数，并且K<=N，也就是M不能超过N*N，在前面例子中M就不能超过100)的格式。
int randomM() {
return randomN() + N * (randomN()%(M/N));
}
问题：
如果M不是N的倍数怎么办，即 M%N > 0。
其实还是可以借鉴上面的经验。
- 我们算出M和N的最大公倍数，假设是P，则
P%M == 0
P%N == 0 - 安装前面的办法生成随机函数randomP()
- 把randomP()的值映射到M的区间，因为P也是M的倍数。
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ,....P
|---M1 --|--M2--|--M3--|--Mx--|--M(P%N)--|
|----N1----|----N2----|----N3----|----Nx----|----N(P%M)----|
如图示，对于任意randomP()，如果值位于区间Nx，那么输出x。这样就输出在1..M之间的随机数。
举一个例子：已知Random7()，求Random5()
因为7和5不是倍数关系，先计算7和5的最小公倍数，即35；根据前面的公式，我们得到35的随机函数。
int random35() {
return random5() + 7 * (random5()%(35/7));
}
下面我们得到random5，因为每一个random35()的值都是1..35，我们把1-35分成5分，每一份有7个数字：
1: 1..7
2: 8..14
3: 15..21
4: 22..28
5: 29..35
根据random35()返回的值坐落在哪一个区间，就取哪一个区间值，例如：
当random35() => 2，则返回1，
当random35() => 7，则返回1，
当random35() => 18，则返回3，
当random35() => 32，则返回5，
...
现在我们可以总结出random5的内容了：
int random5() {
return random35()%5 + 1
}
贴出程序文本如下：
#include <stdio.h>
#include <stdlib.h>
int random7() {
return random()%7 + 1;
}
int random35() {
return random7() + 7 * (random7()%(35/7));
}
int random5() {
return random35()%5 + 1;
}
int main(int argc, char * argv[]) {
char ch;
do {
int i = 0;
for (i=0;i<10;i++) {
printf("%d ", random5());
}
printf("\n");
} while((ch = getchar()) != 'q');
}
问题2：
上面办法比较复杂，有没有简单的办法呢，网上有这样的思路：
int random5() {
return random7() % 5 + 1
}
这也能生成1..5的随机数。
但是我觉得这个不是真的随机数，不能在1..5之间随机生成，因为random7的范围是(1..7)，后面的6..7取余后映射到1..2，会导致random5里面1..2的输出概率偏高，而不能做到1..5之间的随机输出，因为这其实是在(1,2,3,4,5,1,2)这7个数里面随机选取而已，1和2被输出的概率是其他的两倍。
问题3：
进一步，如果给出random5()函数，如何生成random7()函数呢？
用我们前面的方法是不行的，因为超出了限制性条件，35 > 5 * 5了。
很多人给出这样的思路，生成一个5*5的矩阵，矩阵的数字从上往下，从左到右，依次填入1,2,3,...7这七个数字：
| 1 2 3 4 5
---+-------------
1 | 1 2 3 4 5
2 | 6 7 1 2 3
3 | 4 5 6 7 1
4 | 2 3 4 5 6
5 | 7 1 2 3 4
然后调用两次random5()分别得到横坐标和纵坐标，取矩阵对应的数字值，作为随机数输出。
这个问题3和前面问题2有同样的疑问，因为矩阵里面的数字不是均匀分布，最后是1,2,3,4，显然这4个数字的输出概率会高于其他的5,6,7三个数字，导致random7不是真正的1..7之间的随机，1,2,3,4的输出概率大于其他概率。
那怎么解呢，唉，还没有找到更好的办法。
问题4：
另一方面，如果给出random7()函数，如何生成random5()函数呢？
似乎很简单哦：
int random5() {
return random7() % 5;
}
这个办法是不是可行呢；这个算法是可以生成1..5的随机数，但是如果我们统计数量足够大，就会发现1和2的概率会高于其他数字，因为，random7()生成1..7的随机数，余之后得到的数字是(1,2,3,4,5,1,2)这7个数字里面，1和2出现了两次，这样在这7个数字里面随机挑选的时候，1和2的处境概率就会高于其他数字。
那怎么办呢？我也没有找到呢，囧。
几点总结
上述算法只针对如下严格条件才能是完美解决方案：已知randomN，求randomM。
- M是N的倍数，即M%N==0
- M不超过N*N
- 假设M/N=K，那么满足N是K的倍数，即N%K==0
假如N=10，M=20，则满足条件。
假如N=10，M=30，则不满足条件，因为10%3 != 0，不满足这个条件的结果就是导致余数部分的出现概念会大于其他数值，最终产生的随机数并不真正随机。使用使用二维矩阵看，就是矩阵内的数字会有些数字多余其他数字，那么随机选取的时候，他们的出境概率就高于其他数字。
