在上一个博客中，我知道了基于物理现象的真随机数生成器。 但是，由于真随机数的生成速度慢，在实际计算中需要，所以计算机内的随机数全部由程序算法，即某个公式函数生成。 但是，对于相同的随机种子和函数，所得到的随机数序列是一定的，因此所得到的随机数是可预测的并且具有周期，不能称为真随机数，因此称为伪随机数(例如
但是，别看了假字就小看我。 这也有学问。 看起来很简单的几个公式，也许是冷静的水蜜桃几代人努力的成果。 相关研究可以写好几本书。 顺便说一下，亚裔唯一获得图灵奖的姚期智正在研究伪随机数生成论(thepseudorandomnumbergeneratingtheory )。
这里重点介绍两种常用的算法。 这意味着“同余法”(Congruential method )和“梅森旋转算法”(Mersenne twister )
1、同余法
联合法(Congruential method )是一种常用的随机数生成方法，在许多编程语言中被使用。 最明显的是java。 java.util.Random类使用的是同位法中的——线性同位法(Linear congruential method )，此外，还使用了乘方同余法(multiplicativecongruentialmethod ) 现在，打开java的源代码，看看线性同余法的真面目吧！
在Eclipse中键入java.util.Random，然后按F3键导航到Random类的源代码。
首先，我看到了这样的说明。
翻译后：
此类的一个实现用于生成一系列伪随机数。 该类使用48位种子修改为线性同余式以生成随机数。 (见Donald Kunth 《计算机编程的艺术》第二卷，章节3.2.1 )。
很明显，java的Random类采用线性综合法得到随机数。
接下来，我们找到了构造函数和一些方法。 其中包括获得48位种子的过程。
私密性统计数据透明龙seeduniquifier
=newatomiclong (8682522807148012 l；
1 /**
2 * createsanewrandomnumbergenerator.thisconstructorsets3* theseedoftherandomnumbergeneratoavalueverylikely4* tobedististion
6公共随机(7this ) seeduniquifier ) (^System.nanoTime ) )； (9) 9
10隐私保护联盟((11//l ) ECUyer，' tablesoflinearcongruentialgeneratorsof 12//differentsizesandgoof
13 for (； (14长目前=seeduniquifier.get )； 15长下一步=current * 18178349727652981 l； 16if (seeduniquifier.compareandset (current，next ) ) 17返回下一步； 十八(十九)二十
21私密性统计信息龙seeduniquifier 22=newatomiclong (8682522807148012 l； 23公共随机(长序列) 24if (getclass )==Random.class ) 25this.seed=newatomiclong (初始序列) (seed ) ) 26 else { 27 }//subclassmighthaveoverridensetseed
28 this.seed=newAtomicLong (； 29 seed (seed； 30}31 ) 32专用锁定加密(长序列) 33返回(seed^multiplier )掩码； (三十五)三十五。
Java.util.concurrent.atomic.atomic long
publicfinalbooleancompareandset (长外观，
长更新)
atomicallysetsthevaluetothegivenupdatedvalueifthecurrentvalue
== the expected value.Parameters:
expect - the expected value
update - the new value
Returns:
true if successful. False return indicates that the actual value was not equal to the expected value.
这里使用了System.nanoTime()方法来得到一个纳秒级的时间量，参与48位种子的构成，然后还进行了一个很变态的运算——不断乘以181783497276652981L，这里的nanotime可以算是一个真随机数，不过有必要提的是，nanoTime和我们常用的currenttime方法不同，返回的不是从1970年1月1日到现在的时间，而是一个随机的数——只用来前后比较计算一个时间段，比如一行代码的运行时间，数据库导入的时间等，而不能用来计算今天是哪一天。
好了，现在我不得不佩服这位工程师的变态了：到目前为止，这个程序已经至少进行了三次随机：
1、获得一个长整形数作为“初始种子”(系统默认的是8682522807148012L)
2、不断与一个变态的数——181783497276652981L相乘(天知道这些数是不是工程师随便滚键盘滚出来的-.-)(compare and set 保证数据的一致性)
3、与系统随机出来的nanotime值作异或运算，得到最终的种子
再往下看，就是我们常用的得到随机数的方法了，我首先找到了最常用的nextInt()函数，代码如下：
public int nextInt() {
return next(32);
}
代码很简洁，直接跳到了next函数：
1 protected int next(intbits) {2 longoldseed, nextseed;3 AtomicLong seed = this.seed;4 do{5 oldseed =seed.get();6 nextseed = (oldseed * multiplier + addend) &mask;7 } while (!seed.compareAndSet(oldseed, nextseed));8 return (int)(nextseed >>> (48 -bits));9 }
View Code
OK,祝贺一下怎么样，因为我们已经深入到的线性同余法的核心了——没错，就是这几行代码！
在分析这段代码前，先来简要介绍一下线性同余法。
在程序中为了使表达式的结果小于某个值，我们常常采用取余的操作，结果是同一个除数的余数，这种方法叫同余法(Congruential method)。
线性同余法是一个很古老的随机数生成算法，它的数学形式如下：
Xn+1 = (a*Xn+c)(mod m)
其中，
m>0,0
这里Xn这个序列生成一系列的随机数，X0是种子。随机数产生的质量与m，a，c三个参数的选取有很大关系。这些随机数并不是真正的随机，而是满足在某一周期内随机分布，这个周期的最长为m(一般来说是小于M的)。根据Hull-Dobell Theorem，当且仅当：
1. c和m互素;
2. a-1可被所有m的质因数整除;
3. 当m是4的整数倍，a-1也是4的整数倍时，周期为m。所以m一般都设置的很大，以延长周期。
现在我们回过头来看刚才的程序，注意这行代码：
nextseed = (oldseed * multiplier + addend) & mask;
和Xn+1=(a*Xn+c)(mod m)的形式很像有木有！
没错，就是这一行代码应用到了线性同余法公式！不过还有一个问题：怎么没见取余符号？嘿嘿，先让我们看看三个变量的数值声明：
private static final long multiplier = 0x5DEECE66DL;private static final long addend = 0xBL;private static final long mask = (1L << 48) - 1;
其中multiplier和addend分别代表公式中的a和c，很好理解，但mask代表什么呢？其实，x & [(1L << 48)–1]与 x(mod 2^48)等价。解释如下：
x对于2的N次幂取余，由于除数是2的N次幂，如：
0001，0010，0100，1000。。。。
相当于把x的二进制形式向右移N位，此时移到小数点右侧的就是余数，如：
13 = 1101 8 = 1000
13 / 8 = 1.101，所以小数点右侧的101就是余数，化成十进制就是5
然而，无论是C语言还是java,位运算移走的数显然都一去不复返了。(什么，你说在CF寄存器中？好吧，太高端了点，其实还有更给力的方法)有什么好办法保护这些即将逝去的数据呢？
学着上面的mask，我们不妨试着把2的N次幂减一：
0000，0001，0011，0111，01111，011111。。。
怎么样，有启发了吗？
我们知道，某个数(限0和1)与1作与(&)操作，结果还是它本身；而与0作与操作结果总是0，即：
a & 1 = a, a & 0 = 0
而我们将x对2^N取余操作希望达到的目的可以理解为：
1、所有比2^N位(包括2^N那一位)全都为0
2、所有比2^N低的位保持原样
因此， x & (2^N-1)与x(mod 2^N)运算等价，还是13与8的例子：
1101 % 1000 = 0101 1101 & 0111 = 0101
二者结果一致。
嘿嘿，讲明白了这个与运算的含义，我想上面那行代码的含义应该很明了了，就是线性同余公式的直接套用，其中a = 0x5DEECE66DL, c = 0xBL, m = 2^48，就可以得到一个48位的随机数，而且这个谨慎的工程师进行了迭代，增加结果的随机性。再把结果移位，就可以得到指定位数的随机数。
接下来我们研究一下更常用的一个函数——带参数n的nextInt：
1 public int nextInt(intn) {2 if (n <= 0)3 throw new IllegalArgumentException("n must be positive");4
5 if ((n & -n) == n) //i.e., n is a power of 2
6 return (int)((n * (long)next(31)) >> 31);7
8 intbits, val;9 do{10 bits = next(31);11 val = bits %n;12 } while (bits - val + (n-1) < 0);13 returnval;14 }
显然，这里基本的思路还是一样的，先调用next函数生成一个31位的随机数(int类型的范围)，再对参数n进行判断，如果n恰好为2的方幂，那么直接移位就可以得到想要的结果；如果不是2的方幂，那么就关于n取余，最终使结果在[0,n)范围内。另外，do-while语句的目的应该是防止结果为负数。
你也许会好奇为什么(n & -n) == n可以判断一个数是不是2的次方幂，其实我也是研究了一番才弄明白的，其实，这主要与补码的特性有关：
众所周知，计算机中负数使用补码储存的(不懂什么是补码的自己百度恶补)，举几组例子：
2 ：0000 0010 -2 ：1111 1110
8 ：0000 1000 -8 ：1111 1000
18 ：0001 0010 -18 ：1110 1110
20 ：0001 0100 -20 ：1110 1100
不知道大家有没有注意到，补码有一个特性，就是可以对于两个相反数n与-n，有且只有最低一个为1的位数字相同且都为1，而更低的位全为0，更高的位各不相同。因此两数作按位与操作后只有一位为1，而能满足这个结果仍为n的只能是原本就只有一位是1的数，也就是恰好是2的次方幂的数了。
不过个人觉得还有一种更好的判断2的次方幂的方法：
n & (n-1) == 0
感兴趣的也可以自己研究一下^o^。
好了，线性同余法就介绍到这了，下面简要介绍一下另一种同余法——乘同余法(Multiplicative congruential method)。
上文中的线性同余法，主要用来生成整数，而某些情景下，比如科研中，常常只需要(0，1)之间的小数，这时，乘同余法是更好的选择，它的基本公式和线性同余法很像：
Xn+1=(a*Xn )(mod m )
其实只是令线性公式中的c=0而已。只不过，为了得到小数，我们多做一步：
Yn = Xn/m
由于Xn是m的余数，所以Yn的值介于0与1之间，由此到(0，1)区间上的随机数列。
除此之外，还有混合同余法，二次同余法，三次同余法等类似的方法，公式类似，也各有优劣，在此不详细介绍了。
同余法优势在计算速度快，内存消耗少。但是，因为相邻的随机数并不独立，序列关联性较大。所以，对于随机数质量要求高的应用，特别是很多科研领域，并不适合用这种方法。
不要走开，下篇博客介绍一个更给力的算法——梅森旋转算法(Mersenne Twister)，持续关注啊！