随机数，正如它的名字那样神秘。在工作的一年里被它糊弄了好多次，所以我准备把这些坑给记下来。

¶真随机数

随机数分为真随机数与伪随机数。所有真随机数，也就是说它是玩真的，琢磨不定，前一个数与后一个数之间没有任何关联。通常用物理的方式来获得，例如抛硬币、掷骰子。如果你玩过 Arduino 或者其它单片机，肯定知道没有接入任何输入的模拟端口也能用来产生真随机数——这也属于物理方法，因为这些模拟输入会受到宇宙射线的影响。由于它无法预知的特点，常常用于安全领域，例如在生成GPG密码的时候，建议你做一些奇怪的事，比如胡乱敲打键盘或移动鼠标，以增加一些熵。

¶伪随机数

而所谓伪随机数，正如它的名字，它看起来琢磨不定，但事实上却是有规则的。通常是用数学的方法来产生伪随机数，前一个数与后一个数之间存上某种算法上的联系。但是在相当长的一个周期内，看起来就像是随机的，你很难准确猜出下一个数字是什么。当然它了仅仅是很难而已，在历史上有人通过穷举的方法在很短的时间内破解了在线牌内游戏的发牌顺序，有兴趣的话可以读一读网络游戏安全揭密。

既然伪随机数这么不给力，为什么还要用它？因为它很廉价，很容易就可以实现，不过最重要的是它非常适用于某些应用环境。

试想一个程序员在开发一个很复杂的程序，它用了一个真随机数生成器。天有不测风云，他的程序出BUG了。他正准备重新运行了他的程序来捕捉这个BUG，可惜这次BUG没有发生……一切都是随机的，这让他很苦恼。后来他换了伪随机数生成器，预设了一个数字作为随机数生成器的种子，此后的每一个随机数都由这个种子迭代产生。这样每次运行这个程序，都会得到一样的结果，除非种子变了。于是他终于可以轻松的重现碰到的BUG了。在确定他的程序没有BUG之后，他使用真随机数来生成种子，或者将伪随机数生成器换成真随机数生成器。

由于伪随机数的序列总是由某个种子唯一确定，所以这也使得伪随机数可以作为保存现场的关键因素。很多游戏使用伪随机数总子来保存地形或者游戏录像，网游用它来同步战斗画面，一些艺术设计师使用它来挑选中意的随机艺术等等，真是功不可没。

¶如何产生伪随机数

¶随机数表

产生伪随机数的方法有很多，在中学课本里提到过一种简单的方法叫随机数表，翻到书本后面的附录，会看到一大片数字。然后老师说，随便选一个数字作为第一个数，然后按你喜欢的方式顺着数，跳着数，转着圈数，你就得到伪随机数了。也有人模拟这种方法在程序里嵌入一张大的随机表用来做查询。

¶现代方法

对比上面这种简单粗暴的方法，现代科学工作者更加明智，他们设计了很多有趣的算法。例如线性同余法，（可以在数据结构与算法分析——C语言描述的书中找到详细的算法和描述）；还有目前运用最广泛的梅森旋转算法。

¶实践

在一个网游项目的实践中，我发现梅森旋转算法的质量要比线性同余法高很多，当服务端产生的种子较为相近的时候，线性同余法产生的第一个随机数的区间也会相对集中，不够发散，而梅森旋转算法则不会。

实际上我不是很明白服务器的种子是如何产生的，虽然随机数的范围很广，在0到2^32-1之间，但种子却总是在一个8位数附近徘徊。起初使用线性同余法，这种方法对连续的种子很敏感，如果种子很接近，产生的第一个随机数也很接近，这导致AI的初次行为很固定。后来不得不用梅森旋转算法来改变这种状况。为了使客户端（javascript） 能与服务端（php）使用相同的种子产生相同的随机序列，我将 php 的 mt_rand() 移值到了 javascript。

¶随机数应用

¶基本用法

很多语言提供的基本随机数生成器是32位整型的，返回0到2^32-1之间的整数。假设这个函数叫 int rand() 如何用它实现更丰富的随机数函数呢？

返回 [0, n) 之间的整数：

int randInt(n) {
    return rand()%n;
}

返回 [0, 1) 之间的浮点数：

float randFloat() {
    return rand()/4294967296; // 4294967296=2^32
}

如果要返回 (-1, 1) 呢？在一些游戏开发书籍，例如游戏编程中的人工智能技术上看到过这样的代码，用于初始化人工神经网络的权值：

float randClamped() {
    return randFloat() - randFloat();
}

它确实能返回 (-1, 1) 但实际上却了不是均匀分布的，这个函数产生的随机数会集中在 0 附近。不知道是否有意为之，不过看它的名字应该是一个通用函数，正确的方法应该是用映射的方式：

float randClamped() {
    return randFloat() * 2 - 1;
}

我们可以写一个更通用的函数，用于产生 [m, n) 之间的浮点数：

float randFloat(float m, float n) {
    return randFloat() * (n - m) + m;
}

¶其它应用

在JS或者AS社区，常常可以看到一种很简洁数组乱序的写法：

[1,2,3,4,5,6,7,8,9,0].sort(function(a,b){
    return Math.random()<0.5?-1:1;
});

这种简明的写法是不是让人眼睛一亮，感觉非常酷！不过，没错，这又是一个坑，如果你只是单纯用它来打乱一下数组，这没什么问题，就像你把糖倒到咖啡里，然后用勺子搅拌了一下下——是的，还不够均匀。我写了一个测试，统计了一下这个算法产生的分布，发现每个数字留在原来的位置上的几率更大一些，在10000次乱序过程中，1留在原来的位置上2886次，1跑到0的位置上只有14次。

如果想要均匀一些的乱序算法，可以考虑使用 Fisher–Yates shuffle ，也很容易实现。

¶趣题

有一个有趣的问题，假如你有一个 int rand_1_5() 能产生等概率的 1 2 3 4 5 的随机整数，如何用它产生等概率的 int rand_1_7() 呢？相关的讨论可以到这里围观。