最近在做帧同步的实时对战，要自己接管随机数的产生，所以看了一下随机数生成的相关算法。因为游戏会跑在不同平台（iOS/Android）及不同硬件上，所以使用的算法有以下的要求：1. 不能依赖系统；2. 不能依赖硬件；3. 计算中不能使用浮点数（不同平台不同硬件有可能结果不同）。再结合效率方面的考虑，最终选择采用了线性同余算法，并在基础上做了一定的加强。这篇博客主要记录关于这个线性同余算法产生随机数的一些思考。
首先要搞清楚随机数的定义，真正的随机数都不是计算出来的，这里我们说的随机数其实都是伪随机数，随机数伪随机数的定义，具体的论证等资料可以自行查阅。产生伪随机数的算法有很多种，线性同余算法基于整数的加、乘和求模，算法简单但是具有较强的规律性与周期性。怎么在这个基础上尽量降低规律性与周期性，使得在更广范围内覆盖更多可能就是我们的目标。
首先要了解的是线性同余函数公式
，最终结果受乘数λ，加数C和模数M决定。M通常我们会使用一个较大的素数，而λ,C的选取在很大程度上会影响生成的随机数的质量。我们尝试使用不同的λ与C去生成一系列的随机数并观察他们。为了直观感受一些列的随机数是否足够随机，我们用这些数字作为X,Y填充一张1024 * 512的位图，观察图上的点的位置，可以得知这一系列随机数在1024 * 512范围内随机分布的情况。
（图一）
（图二）使用最基础的线性同余公式生成的随机数，因乘数λ、加数C参数不同，有的时候比较随机（图一），有的时候呈现出比较强的规律性（图二），但周期性都是十分短。在多次尝试中能成功填充的点从几千到几万个，但并不能完全填充整张图，证明周期性在1024*512种组合中都无法确保不重复。这样的随机数算法显然是不够好的。要在线性同余算法的基础上加强，首先想到的是计算Xn时，不再只用Xn-1参与，而是用X1到Xn-1的加和。
使用加和版本的线性同余算法，套用不同的参数λ、C再次生成随机数填充位图观察：
（图四）
可以看出加和版本的线性同余算法产生的随机数，因乘数λ、加数C参数不同，有的时候呈现出比较强的规律性（图三），有的时候比较随机（图四）。数量上从10w到50w不等，大部分情况无法覆盖1024*512种情况，极少数情况下能完全覆盖。选取一组较好的λ,C参数，使用加和版本的线性同余算法产生的随机数其实已经可以满足游戏功能的需求了，如果还想加再优化，则要从参数λ,C的变化入手。
在多次测量的过程中，用不同的参数λ,C能得出不同的表现，那只要λ,C不再取固定值，就相当于混合了使用多个加和线性同余算法生成结果的混合来做随机数。这样做即使一组λ,C生成的随机数有一定的周期性与规律性，但混用多组结果，就能把周期性与规律性再次降低（但无法消除）。
那么如何给λ,C动态取值呢。方法有两种：
第一种是预先生成一张素数表，让λ,C在这张表中循环取值，这种方式λ,C之间没有规律性（素数性质），但周期性的大小就取决于这张素数表的大小，通常而言不会有太多组变化，预生成的表最多也就是几百个。
第二种方式就是λ,C也动态计算得出。这样做其实问题就回到最初的原点，如何使用代码动态生成随机数然后尽量让这些数字的规律性与周期性尽量低。通过上面的分析已经知道，如果λ,C也使用代码生成的话，在周期性上比方法一有更大的优势（选取较好的λ,C可以在1024*512区间内就有几十万种组合，参考图四），但规律性上没有方法一好。
无论是采用方法一还是方法二，本质上都是在混用多个（有限个）线性同余公式的结果，所以一定还是会有周期性与规律性的问题。方法一优势在于规律性非常低，但素数表的大小决定了周期性大小，通常做不到太多变化，而且占用内存。方法二λ,C组合非常多，不需要额外内存，但要额外计算，并且这些λ,C是会有一定的规律性的，优势是周期性非常长，但规律性上没有方法一好的。
其实对于游戏逻辑而言，采用固定λ,C的加和线性同模产生的随机数已经足够了，效率还会比较高。但如果想做一个质量很高的随机数生成器，个人建议是采用方法一，然后预先打出一万以内的素数作为λ,C组合使用，这样的λ,C组合已经有上百万种了，混用一百万个加和版本的线性同余算法来生成随机数的话，规律性与随机性方面应该都能满足计算机领域的使用了。
最后有几点值得注意的是：
一、计算时使用int或int64，有符号或无符号，对于随机数的生成都会有很大影响，计算时要注意
二、如果λ,C 较小而M 非常大，在初期会出现连续的递增情况，这三个参数的选取要注意。