偽隨機數發生器用於在系統需要隨機數的時候，通過一系列種子值計算出來的偽隨機數。因為生成一個真正意義上的“隨機數”對於計算機來說是不可能的，偽隨機數也只是儘可能地接近其應具有的隨機性，但是因為有“種子值”，所以偽隨機數在一定程度上是可控可預測的。
基本介紹
- 中文名：偽隨機數發生器
- 外文名：pseudo random number generator
- 所屬學科：IT
- 所屬領域：程式設計
概述,方法,取中法,同餘法,移位法,梅森旋轉算法,
概述
通過程式得到的隨機數無論什麼算法都一定是通過遞推公式得到的序列，這本身就違反了隨機的定義，所以它們都不是真正的隨機數。偽隨機數中一個很重要的概念就是“種子”，種子決定了隨機數的固定序列，例如在C語言rand函式得到的序列每次都是相同的，如果想得到不同序列需要調用srand設定種子；同理在Java中new Random(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。
當 a = 1 並且 C != 0時，此同餘法稱為加法同餘法
當a != 1 並且 C = 0時，此同餘法稱為乘法同餘法
當a != 1 並且 C != 0時，此同餘法稱為混契約余法
同餘法當m越大，Ni的範圍也就越大，隨機分布的也就越均勻，Rn也就分布的更均勻，所以m取值應儘可能的大，充分利用計算機字長。對於如何獲得滿周期隨機數是存在判定定理的，若且唯若滿足下列條件時，踐行同餘法是滿周期的：
1.C與m互質
2.對於m的每一個質因子p，（a-1）為p的倍數
3.若m可被4整除， (a-1)也可被4整除。
除此之外還有二次同餘，三次同餘等，原理差不多。
移位法
由於計算機特有的邏輯移位運算，可以對種子N0左移n位得到M1，右移n位得到M2，將M1與M2做邏輯相加運算得到隨機數N1，
公式為Ni+1 = Ni >> n + Ni << n.移位法速度非常快，但對初始值要求較高，很難得到滿意的隨機序列。
梅森旋轉算法
梅森旋轉算法是當今生成隨機數質量最好的算法，如php，python，perl等流行程式語言內置的PRNG都是採用該算法實現。
下面是來至wiki的介紹：
梅森旋轉算法（Mersenne twister）是一個偽隨機數生成算法。由松本真和西村拓士在1997年開發，基於有限二進制欄位上的矩陣線性地鬼。可以快速產生高質量的偽隨機數， 修正了古典隨機數發生算法的很多缺陷。
