今天在微博上到一篇如何使用隨機(jī)數(shù)的文章，讓我回憶起剛上大一時學(xué)C語言時，書后有道調(diào)用rand()函數(shù)的練習(xí)題，當(dāng)時覺得好神奇，想知道它是怎么實(shí)現(xiàn)的，大二時候?qū)WJava又遇到了random()函數(shù)，恰巧當(dāng)時上機(jī)課我有機(jī)會問老師，遺憾的是老師只是告訴我那是偽隨機(jī)數(shù)，課后查查資料才了解。如今來一篇關(guān)于隨機(jī)數(shù)發(fā)生器博文來回憶一下神奇的隨機(jī)數(shù)。
眾所周知，我們平時所使用的無論什么編程語言都會提供一個隨機(jī)數(shù)函數(shù)，而且它是偽隨機(jī)數(shù)（Pseudo Random Number），它是由算法計(jì)算得出的，是可以預(yù)測的，也就是說當(dāng)隨機(jī)種子相同時，對于同一個隨機(jī)函數(shù)，得出的隨機(jī)數(shù)列是固定不變的，亞裔唯一圖靈獎得主姚期智就是研究的就是偽隨機(jī)數(shù)生成論；與之對應(yīng)的就是真隨機(jī)數(shù)（True Random Number）它是真正的隨機(jī)數(shù)，無法預(yù)測且無周期性；還有一種是產(chǎn)生隨機(jī)數(shù)的發(fā)生器是密碼學(xué)偽隨機(jī)數(shù)發(fā)生器(Cryptographically Secure Pseudo-Random Number Generator)常用的算法有 MD5 ，SHA1 等標(biāo)準(zhǔn), 這里不做過多討論，說說最基本的前兩種：
一、真隨機(jī)數(shù)發(fā)生器
像無法實(shí)現(xiàn)永動機(jī)一樣，想要實(shí)現(xiàn)真隨機(jī)數(shù)靠程序是永遠(yuǎn)無法實(shí)現(xiàn)的，很多情況下只能看老天的眼色，比如布朗運(yùn)動，量子效應(yīng)，放射性衰變等。第一個真隨機(jī)數(shù)發(fā)生器是1955年由Rand公司創(chuàng)造的，而在1999年，intel發(fā)布Intel810芯片組時，就配備了硬件隨機(jī)數(shù)發(fā)生器，基于IntelRNG的真隨機(jī)數(shù)生成器可以生成滿足獨(dú)立性和分布均勻性的真隨機(jī)數(shù)，目前大部分芯片廠商都集成了硬件隨機(jī)數(shù)發(fā)生器，只要安裝相應(yīng)驅(qū)動，了解讀取寄存器地址，可以直接調(diào)用發(fā)生器。Intel810RNG的原理大概是：利用熱噪聲(是由導(dǎo)體中電子的熱震動引起的)放大后，影響一個由電壓控制的振蕩器，通過另一個高頻振蕩器來收集數(shù)據(jù)。TRNG的類型主要有：
1.基于電路的TRNG：
i.振蕩器采樣：就是上述Intel采用的方式。
ii.直接放大電路噪聲：利用電路中各種噪聲，如上述的熱噪聲作為隨機(jī)源，由于強(qiáng)度小，所以先要對其放大，然后對一定時間內(nèi)超過閾值的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，這樣就產(chǎn)生的隨機(jī)數(shù)。.
iii.電路亞穩(wěn)態(tài):亞穩(wěn)態(tài)表示觸發(fā)器無法在規(guī)定時間內(nèi)達(dá)到一個可確認(rèn)狀態(tài)，一定條件下，觸發(fā)器達(dá)到兩個穩(wěn)態(tài)的幾率為50%，所以先使電路進(jìn)入亞穩(wěn)態(tài)，之后根據(jù)狀態(tài)轉(zhuǎn)化為隨機(jī)數(shù)。
iv.混沌電路：不可預(yù)測，對初始條件的敏感的依賴性。以及混沌電路在芯片中易于實(shí)現(xiàn)的特點(diǎn)，可以產(chǎn)生效果不錯的隨機(jī)數(shù)。
2.基于其他物理源的TRNG
如宇宙射線，粒子衰變，空氣噪聲等作為隨機(jī)源，來產(chǎn)生隨機(jī)數(shù)。
3.其他物理信息TRNG
人為可以產(chǎn)生隨機(jī)數(shù)嗎？當(dāng)然能！聽說一個HR拆選簡歷的方式是往天上一扔，掉在桌子上的簡歷就通過，這個HR確認(rèn)懂隨機(jī)啊，而且是真隨機(jī)。這類隨機(jī)生活中隨處可見，擲骰子，抓麻將，或者統(tǒng)計(jì)一個月內(nèi)帝都PM2.5的數(shù)值。
對于真隨機(jī)發(fā)生器我個人認(rèn)為未來是可以通過生物計(jì)算機(jī)來獲取的。
二、偽隨機(jī)數(shù)發(fā)生器
通過程序得到的隨機(jī)數(shù)無論什么算法都一定是通過遞推公式得到的序列，這本身就違反了隨機(jī)的定義，所以它們都不是真正的隨機(jī)數(shù)。偽隨機(jī)數(shù)中一個很重要的概念就是“種子”，種子決定了隨機(jī)數(shù)的固定序列，例如在C語言rand函數(shù)得到的序列每次都是相同的，如果想得到不同序列需要調(diào)用srand設(shè)置種子；同理在Java中 new Random(1)的構(gòu)造函數(shù)參數(shù)來設(shè)置種子。下面介紹生成PRNG的幾種常見方法：
1.取中法：
i.平方取中法：
這個方法是由馮·諾伊曼在1946年提出的，思想很簡單：
- public class CustomRandom {
- static final int FIGURES = 10000;
- static long mRandom;
- public static void main(String[] args) {
- long seed = System.currentTimeMillis();
- mRandom = seed % FIGURES;
- for (int i = 0; i < 10; i++)
- System.out.println(getRandom(seed));
- }
- private static long getRandom(long seed) {
- return mRandom = (mRandom * mRandom / (long) Math.pow(10, 5/2)) % FIGURES;
- }
- }
ii：常數(shù)取中法
iii：乘法取中法：
2.同余法
- public class CustomRandom {
- static final int A = 3;
- static final int M = (1 << 31) - 1 ;
- private static long mRandom;
- public static void main(String[] args) {
- mRandom = System.currentTimeMillis() / Integer.MAX_VALUE;
- for (int i = 0; i < 10; i++) {
- mRandom = (mRandom * A) % M;
- System.out.println(mRandom);
- }
- }
- }
- public class CustomRandom {
- static final int N = 5;
- static long mRandom;
- public static void main(String[] args) {
- long mRandom = System.currentTimeMillis();
- for (int i = 0; i < 10; i++) {
- mRandom = Math.abs((mRandom >> N) + (mRandom << N));
- System.out.println(mRandom);
- }
- }
- }
4.梅森旋轉(zhuǎn)算法
梅森旋轉(zhuǎn)算法（Mersenne twister）是一個偽隨機(jī)數(shù)生成算法。由松本真和西村拓士在1997年開發(fā)，基于有限二進(jìn)制字段上的矩陣線性地鬼
。可以快速產(chǎn)生高質(zhì)量的偽隨機(jī)數(shù)， 修正了古典隨機(jī)數(shù)發(fā)生算法的很多缺陷。
下面的一段偽代碼使用MT19937算法生成范圍在[0, 232 ? 1]的均勻分布的32位整數(shù)
- <span style="font-size:10px;"> //創(chuàng)建一個長度為624的數(shù)組來存儲發(fā)生器的狀態(tài)</span>
- int[0..623] MT
- int index = 0
- //用一個種子初始化發(fā)生器
- function initialize_generator(int seed) {
- i := 0
- MT[0] := seed
- for i from 1 to 623 { // 遍歷剩下的每個元素
- MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
- }
- }
- // Extract a tempered pseudorandom number based on the index-th value,
- // calling generate_numbers() every 624 numbers
- function extract_number() {
- if index == 0 {
- generate_numbers()
- }
- int y := MT[index]
- y := y xor (right shift by 11 bits(y))
- y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
- y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
- y := y xor (right shift by 18 bits(y))
- index := (index + 1) mod 624
- return y
- }
- // Generate an array of 624 untempered numbers
- function generate_numbers() {
- for i from 0 to 623 {
- int y := (MT[i] & 0x80000000) // bit 31 (32nd bit) of MT[i]
- + (MT[(i+1) mod 624] & 0x7fffffff) // bits 0-30 (first 31 bits) of MT[...]
- MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
- if (y mod 2) != 0 { // y is odd
- MT[i] := MT[i] xor (2567483615) // 0x9908b0df
- }
- }
- }
作者：nash
