美女性爱网站,色黄视频在线观看,小嫩苞一区二区三区,老色批TV,国产婬荡交换XXXⅩ,天天日天天干天天草,色之综合天天综合色天天棕色,www.黄色电影

（給前端大學(xué)加星標(biāo)，提升前端技能.）

作者：李銀城
https://zhuanlan.zhihu.com/p/205359984

在JavaScript里面產(chǎn)生隨機(jī)數(shù)的方式是調(diào)用Math.random，這個(gè)函數(shù)返回[0, 1)之間的數(shù)字，如：

如果想要產(chǎn)生整數(shù)的隨機(jī)數(shù)，那么只需要稍微換算一下，例如產(chǎn)生[10, 20]之間的整數(shù)，那么可通過(guò)以下代碼即可：

Math.floor(Math.random() * 11) + 10

如何實(shí)現(xiàn)一個(gè)自定義的random的函數(shù)呢，即怎么實(shí)現(xiàn)一個(gè)隨機(jī)數(shù)發(fā)生器（RNG，Random Number Generator），一個(gè)比較簡(jiǎn)單的實(shí)現(xiàn)如下代碼所示：

// from stackoverflow
var seed = 1;
function random() {
var x = Math.sin(seed++) * 10000;
return x - Math.floor(x);
}

如上代碼，這個(gè)函數(shù)需要一個(gè)種子seed，每次調(diào)用random函數(shù)的時(shí)候種子都會(huì)發(fā)生變化。在控制臺(tái)進(jìn)行實(shí)驗(yàn)：

可以看到，結(jié)果還是挺隨機(jī)的。為什么隨機(jī)數(shù)發(fā)生器需要一個(gè)種子呢？因?yàn)閷?duì)于一個(gè)沒(méi)有輸入的函數(shù)，不管執(zhí)行多少次，其運(yùn)行結(jié)果都是一樣的，所以需要有一個(gè)不斷變化的入?yún)ⅲ@個(gè)入?yún)⒕徒蟹N子，每運(yùn)行一次種子就會(huì)發(fā)生一次變化。

那么我們直接用Math.random不就好了嗎，為什么還要自己實(shí)現(xiàn)一個(gè)random函數(shù)呢？有一些場(chǎng)景需要我們能控制隨機(jī)數(shù)的產(chǎn)生，例如在在線大轉(zhuǎn)盤(pán)場(chǎng)景里面，轉(zhuǎn)盤(pán)的轉(zhuǎn)動(dòng)是隨機(jī)的，但是各方需要保持一樣的隨機(jī)，所以如果各方都使用相同的隨機(jī)函數(shù)，就能夠保證各方產(chǎn)生的隨機(jī)序列是一樣的，如下圖所示：

甲觸發(fā)開(kāi)始之后，通知其他各方，并帶上一個(gè)當(dāng)前的時(shí)間戳，所有人使用這個(gè)時(shí)間戳做為隨機(jī)種子，并使用相同的隨機(jī)數(shù)函數(shù)，那么就能保證所有人產(chǎn)生的隨機(jī)序列是一樣的。

然后我們?cè)賮?lái)看一下C庫(kù)里面的rand函數(shù)，這個(gè)函數(shù)返回[0, RANDMAX)之間的整數(shù)（ RANDMAX 根據(jù)實(shí)現(xiàn), 最小值 >= 32767 ），如下代碼所示：

/* 初始化隨機(jī)數(shù)發(fā)生器，使用當(dāng)前時(shí)間戳（秒）*/
srand((unsigned) time(&t));

/* 輸出 0 到 49 之間的 5 個(gè)隨機(jī)數(shù) */
for( i = 0; i < n ; i++ ) {
  printf("%d\n", rand() % 50);

上面代碼先調(diào)用srand設(shè)置隨機(jī)種子，使用的種子是調(diào)用time函數(shù)返回的時(shí)間戳，單位為秒，然后再調(diào)用rand函數(shù)生成隨機(jī)數(shù)?？梢园l(fā)現(xiàn)，這個(gè)函數(shù)存在一個(gè)明顯缺陷：當(dāng)你在同一秒內(nèi)運(yùn)行該程序，產(chǎn)出的隨機(jī)數(shù)將會(huì)是一樣的。

C庫(kù)的rand函數(shù)實(shí)現(xiàn)非常簡(jiǎn)單，如下代碼所示：

staticunsignedlongintnext= 1;  // 初始種子為1

int rand(void) // RAND_MAX assumed to be 32767
{
next= next* 1103515245+ 12345;
return(unsignedint)(next/ 65536) % 32768;
}

void srand(unsignedint seed)
{
next= seed;
}

代碼第一行的next便表示種子，而隨機(jī)數(shù)是通過(guò)簡(jiǎn)單的四則運(yùn)算得到的，效率會(huì)比我們上面的使用的求解正弦會(huì)更高一些。

那么為什么JavaScript的Math.random不需要種子呢，它是怎么實(shí)現(xiàn)的呢？ES5對(duì)Math.random的規(guī)定是這樣的：

15.8.2.14 random ( )
Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

翻譯一下就是，產(chǎn)生的值是在[0, 1)之間，并且具有大致的均勻分布，不用帶參數(shù)。

我們可以看一下V8里面是怎么實(shí)現(xiàn)Math.random的，它的實(shí)現(xiàn)代碼是在math-random.cc和math.tq這兩個(gè)文件，實(shí)現(xiàn)邏輯如下代碼所示：

// 取出當(dāng)前隨機(jī)數(shù)的狀態(tài)
State state = native_context.math_random_state();
// 如果cache還沒(méi)初始化，那么進(jìn)行初始化
if(state.s0 == 0&& state.s1 == 0) {
uint64_t seed;
// 產(chǎn)出一個(gè)隨機(jī)種子
  random_number_generator()->NextBytes(&seed, sizeof(seed));
// 把種子進(jìn)行哈希散射生成另兩個(gè)數(shù)s0和s1
  state.s0 = base::RandomNumberGenerator::MurmurHash3(seed);
  state.s1 = base::RandomNumberGenerator::MurmurHash3(~seed);
}

// 取出cache
FixedDoubleArray cache = native_context.math_random_cache();
// Create random numbers.
for(int i = 0; i < kCacheSize; i++) { // kCacheSize = 128;
// Generate random numbers using xorshift128+.
// 使用s0和s1進(jìn)行一些位移運(yùn)算得到一個(gè)隨機(jī)數(shù)(s0)
base::RandomNumberGenerator::XorShift128(&state.s0, &state.s1);
// 把整數(shù)的隨機(jī)數(shù)轉(zhuǎn)成小數(shù)，并存到cache里面
  cache.set(i, base::RandomNumberGenerator::ToDouble(state.s0));
}

具體過(guò)程如上注釋所示，每次會(huì)一次性產(chǎn)生128個(gè)隨機(jī)數(shù)，并放到cache里面，供后續(xù)使用。我們比較關(guān)心的是代碼第7行的隨機(jī)種子是怎么產(chǎn)生的。經(jīng)過(guò)打斷點(diǎn)調(diào)試，我們發(fā)現(xiàn)最后是調(diào)用RandBytes函數(shù)，這個(gè)函數(shù)是通過(guò)讀取/dev/urandom文件的8個(gè)字節(jié)得到一個(gè)隨機(jī)數(shù)。urandom是Linux系的系統(tǒng)上源源不斷產(chǎn)生隨機(jī)數(shù)據(jù)的特殊文件。而在Windows系統(tǒng)上則會(huì)調(diào)用rands函數(shù)，rands是Windows系統(tǒng)提供的一個(gè)隨機(jī)性足夠強(qiáng)的隨機(jī)數(shù)發(fā)生器。而在其他系統(tǒng)則是通過(guò)獲取當(dāng)前系統(tǒng)高精度的時(shí)間戳。所以我們看到Chromium隨機(jī)數(shù)的源頭是借助了操作系統(tǒng)的能力。

我們可以把cache里面的128個(gè)數(shù)字打印出來(lái)，并和控制臺(tái)的運(yùn)行結(jié)果進(jìn)行對(duì)比，如下圖所示：

打印的結(jié)果是從后往前取的，如果index為0，說(shuō)明隨機(jī)數(shù)用完了，需要重新生成一批隨機(jī)數(shù)。這里我們也看到，在Chrome控制臺(tái)未執(zhí)行Math.random之前，我們已經(jīng)能夠預(yù)測(cè)到下一個(gè)隨機(jī)數(shù)是什么了。所以這里的隨機(jī)數(shù)具有可預(yù)測(cè)性，這種由算法生成的隨機(jī)數(shù)也叫偽隨機(jī)數(shù)。只要種子確定，隨機(jī)算法也確定，便能知道下一個(gè)隨機(jī)數(shù)是什么。

當(dāng)我們查閱MDN文檔的時(shí)候，文檔上說(shuō)Math.random是不安全的，不能夠做為安全用途，如加密，如下圖所示：

需要使用window.crypto.getRandomValue函數(shù)。為什么說(shuō)Math.random是不安全的呢？從V8的源碼可以看到Math.random的種子來(lái)源是/dev/random，取64位，種子的可能個(gè)數(shù)為2 ^ 64隨機(jī)算法相對(duì)簡(jiǎn)單，只是保證盡可能的隨機(jī)分布。

通過(guò)查閱一些資料我們發(fā)現(xiàn)window.crypto.getRandomValue的實(shí)現(xiàn)在Safari，Chrome和Opera瀏覽器上是使用帶有1024位種子的ARC4流密碼。你可能會(huì)說(shuō) 2 ^ 64難道還不夠大嗎？我們知道撲克牌有52張，總共有52 ! = 2 ^ 226種組合，如果隨機(jī)種子只有2 ^ 64種可能，那么可能會(huì)有大量的組合無(wú)法出現(xiàn)。

當(dāng)隨機(jī)數(shù)種子范圍較少或者是算法不夠優(yōu)，在多次取值之后可能會(huì)出現(xiàn)周期性，有人做了個(gè)實(shí)驗(yàn)，如下圖所示：

左圖是PHP的rand函數(shù)在Windows上的結(jié)果，右圖是通過(guò)一個(gè)高質(zhì)量的隨機(jī)數(shù)發(fā)生器產(chǎn)生的結(jié)果。這個(gè)實(shí)驗(yàn)通過(guò)不斷產(chǎn)生隨機(jī)色值，然后打點(diǎn)，就得到以上結(jié)果。可以看到，左圖出現(xiàn)了一些規(guī)律性的花紋，而右圖則是無(wú)規(guī)律的噪點(diǎn)。

接著，我們?cè)僬f(shuō)一下隨機(jī)數(shù)的一個(gè)應(yīng)用：洗牌算法——給定一個(gè)數(shù)組如[1, 2, 3, 4, 5, 6]，處理為一個(gè)隨機(jī)排列的數(shù)組如輸出為[3, 1, 6, 2, 5, 4]。一個(gè)標(biāo)準(zhǔn)解法如下代碼所示：

function shuffle(arr) {
for(let i = 0; i < arr.length; i++) {
let j = i + Math.random() * (arr.length - i) >> 0;
    swap(arr, i, j)
}
}

原理是每次都和當(dāng)前及后面的數(shù)之中隨機(jī)選中一個(gè)進(jìn)行交換，如1可以和1, 2, …, 6任選一個(gè)進(jìn)行交換，而當(dāng)?shù)谝粋€(gè)位置確定好了之后就不再動(dòng)它了，所以2是和2及之后的數(shù)字進(jìn)行交換。在控制臺(tái)實(shí)驗(yàn)這個(gè)算法的效果，如下圖所示：

可以看到，每次運(yùn)行都能夠產(chǎn)生一個(gè)隨機(jī)排列的數(shù)組。這也正是上面提到的大轉(zhuǎn)盤(pán)所使用的方法。

然后我們?cè)賮?lái)看一個(gè)不好的案例：《當(dāng)隨機(jī)不夠隨機(jī)：一個(gè)在線撲克游戲的教訓(xùn)》，這個(gè)案例說(shuō)的是1999年的時(shí)候一個(gè)很流行的在線撲克網(wǎng)站公布了他們所使用的洗牌算法，如下圖所示：

它使用的語(yǔ)言是Pascal，邏輯實(shí)現(xiàn)和我們上面的標(biāo)準(zhǔn)解法類(lèi)似，但是有一些明顯的bug。原文里面列了幾個(gè)，這里我們也討論一下：

差1錯(cuò)誤——因?yàn)閞andom函數(shù)返回的值是[0, 50]，所以導(dǎo)致第52張牌永遠(yuǎn)無(wú)法停留在第52個(gè)的位置
洗牌不均勻——這個(gè)算法可能會(huì)把之前已經(jīng)換好的牌重新調(diào)換順序，越往前排的位置得到的換牌機(jī)會(huì)會(huì)更多。
使用32位的種子——種子的可能性總共只用2 ^ 32個(gè)，相對(duì)于52！差很多。
使用ms的系統(tǒng)時(shí)間做為種子——這里使用的是從當(dāng)天午夜零點(diǎn)到當(dāng)前的ms數(shù)，而一天總共只有86,400,000ms，所以產(chǎn)生的隨機(jī)數(shù)總共只有這么多種可能，如果黑客將系統(tǒng)時(shí)間和服務(wù)的時(shí)間進(jìn)行同步到秒級(jí)，那么便可把可能性降低到1000種，然后再根據(jù)已知的牌進(jìn)行檢索便可準(zhǔn)確知道所使用的隨機(jī)種子是哪一個(gè)。

做為一個(gè)生產(chǎn)環(huán)境的應(yīng)用，這樣的實(shí)現(xiàn)是有明顯漏洞的。

和偽隨機(jī)數(shù)（Pseudo Random Number ）相對(duì)的是真隨機(jī)數(shù)（True Random Number ），真隨機(jī)數(shù)需要從現(xiàn)實(shí)世界進(jìn)行采集。上文所說(shuō)的/dev/urandom是生產(chǎn)偽隨機(jī)數(shù)的一個(gè)文件，而/dev/random則是生產(chǎn)真隨機(jī)數(shù)的文件，/dev/random的一種實(shí)現(xiàn)是通過(guò)設(shè)備驅(qū)動(dòng)程序采集背景噪音。有一個(gè)提供真隨機(jī)數(shù)的網(wǎng)站叫random.org：

它是通過(guò)采集大氣噪音生成的隨機(jī)數(shù)，你可以使用它提供的免費(fèi)接口做為你的隨機(jī)數(shù)來(lái)源。

今年還有廠商推出了量子隨機(jī)數(shù)手機(jī)，查閱了一下：

工作原理是：LED發(fā)出隨機(jī)數(shù)的光子，CMOS捕獲光源散粒噪聲產(chǎn)生隨機(jī)序列，量子芯片通過(guò)測(cè)量光量子態(tài)得到的隨機(jī)數(shù)來(lái)加密信息。

優(yōu)勢(shì)在于：量子隨機(jī)數(shù)生成芯片組通過(guò)生成不可預(yù)測(cè)且無(wú)模式的純隨機(jī)數(shù)，可以幫助智能手機(jī)用戶安全地使用特定服務(wù)。

把隨機(jī)數(shù)作為一個(gè)賣(mài)點(diǎn)，說(shuō)明隨機(jī)數(shù)還是挺重要的。

??愛(ài)心三連擊
點(diǎn)分享
點(diǎn)點(diǎn)贊
點(diǎn)在看

隨機(jī)數(shù)的故事

??愛(ài)心三連擊