偽隨機數發生器

通過程序得到的隨機數無論什麼算法都一定是通過遞推公式得到的序列，這本身就違反了隨機的定義，所以它們都不是真正的隨機數。偽隨機數中一個很重要的概念就是“種子”，種子決定了隨機數的固定序列，例如在C語言rand函數得到的序列每次都是相同的，如果想得到不同序列需要調用srand設置種子；同理在Java中new Random(1)的構造函數參數來設置種子 ^[1]  。

i：平方取中法：

這個方法是由馮·諾伊曼在1946年提出的，思想很簡單：

選擇一個m位數Ni作為種子，做平方運算（記為Ni+ 1 = （Ni * Ni）...)，結果若不足2m個位，在前補0。在這個數選中間m個位的數作為Ni+1。這個算法明顯又很大弊端，不僅週期短而且分佈不均勻，比如10000平方取中結果就一直為00000了。

ii：常數取中法：

此方法與平方取中法稍有不同，只是把一個隨機數的平方換成了隨機數與常數的乘積（記為Ni+1 = （K * Ni）...)，對於隨機分佈等沒有什麼提升。

iii：乘法取中法：

此方法是對平方取中法的一定優化，公式記為Ni+1 = （Ni * Ni-1）...

同餘是啥不知道的同學見我《素性測試》中的wilson檢測中有解釋

同餘法是大部分變成語言的RNG所採用的算法，線性同餘方程為：Ni+1 = a Ni + C （mod m），其中a為乘子，C為增量，m為膜。產生的隨機序列Rn = Ni / m。

同餘法當m越大，Ni的範圍也就越大，隨機分佈的也就越均勻，Rn也就分佈的更均勻，所以m取值應儘可能的大，充分利用計算機字長。對於如何獲得滿週期隨機數是存在判定定理的，當且僅當滿足下列條件時，踐行同餘法是滿週期的：

1.C與m互質

除此之外還有二次同餘，三次同餘等，原理差不多。

由於計算機特有的邏輯移位運算，可以對種子N0左移n位得到M1，右移n位得到M2，將M1與M2做邏輯相加運算得到隨機數N1，

公式為Ni+1 = Ni >> n + Ni << n.移位法速度非常快，但對初始值要求較高，很難得到滿意的隨機序列。

梅森旋轉算法是當今生成隨機數質量最好的算法，如php，python，perl等流行編程語言內置的PRNG都是採用該算法實現。

下面是來至wiki的介紹：

梅森旋轉算法（Mersenne twister）是一個偽隨機數生成算法。由松本真和西村拓士在1997年開發，基於有限二進制字段上的矩陣線性遞歸 ^[3]  。可以快速產生高質量的偽隨機數， 修正了古典隨機數發生算法的很多缺陷 ^[2]  。