網上常能見到的一段 JS 隨機數生成演算法如下,為什麼用 9301, 49297, 233280 這三個數字做基數?
見到這個隨機數生成演算法好幾次了,乍看有點雞肋本來用Math.random()就可以的事。想不清楚為什麼他要用9301,49297,233280這三個數字?其中有道理嗎?還是僅是隨意選的三個數?但是這個組合貌似流傳很廣。好多小網站源碼里都見到過。
function rnd( seed ){
seed = ( seed * 9301 + 49297 ) % 233280; //為何使用這三個數?
return seed / ( 233280.0 );
};function rand(number){
today = new Date();
seed = today.getTime();
return Math.ceil( rnd( seed ) * number );
};myNum=(rand(5));
Google了一下這3個數字,一些說法也是人云亦云沒有找到合理的解釋。
例如:Generate Repeatable Random Numbers (in JS)You may ask: Why 『(seed * 9301 + 49297) % 233280『 ?!
The answer is both simplecomplicated: The combination of 9301, 49297 and 233280 provide a very even distributed set of 「random」 numbers. Please don』t ask WHY – that』s the complicated part, some very smart people figured out those numbers quite some time ago, and I also cannot tell you how they did it.很聰明的前人算出來的?。。。
=============================================================
又找到一個頁面 http://www.ict.griffith.edu.au/anthony/info/C/RandomNumbers 好像有列舉,但是沒能看懂,ACM之類的。。,有人能解釋下不?
Simple (bad) Psuedo Random Number Generator (Sic)
The low bit typically just toggles between calls.random() {
seed = ( seed * mulitiplier + increment ) % modulus;
return seed;
}Table of Good values
Multiplier Increment Modulus
25173 13849 65536
9301 49297 233280
??
很多人認為這是簡單的Magic Number,其實這背後有內在的原因,這三個數字並不是隨便亂選出來的。
入門級的選擇標準這種偽隨機數生成器叫做線性同餘生成器(LCG, Linear Congruential Generator),幾乎所有的運行庫提供的rand都是採用的LCG,形如:
生成的偽隨機數序列最大周期m,範圍在0到m-1之間。要達到這個最大周期,必須滿足
- c與m互質
- a - 1可以被m的所有質因數整除
- 如果m是4的倍數,a - 1也必須是4的倍數
以上三條被稱為Hull-Dobell定理。
作為一個偽隨機數生成器,周期不夠大是不好意思混的,所以這是要求之一。
可以看到,a=9301, c = 49297, m = 233280這組參數,以上三條全部滿足。
進階級的選擇標準
要在偽隨機數生成器界混,僅僅入門是不夠的。
從工程的角度來講,的值要(在合理的範圍內)足夠小,以避免溢出的問題。
從安全(實用)性的角度來講,還要滿足良好的隨機性,這一點可以通過Knuth"s Spectral Test來評估(見[2][3]),要通過2,3,4,5以及6維的Spectral Test才行。Spectral Test考察的就是生成的偽隨機數序列在超空間的網格結構(lattice structure),當年IBM的RANDU子程序鬧出的烏龍,連3維的Spectral Test就不能通過,上圖嘲諷下:
其中每個點代表三個連續的RANDU生成的偽隨機數值,可以看到所有偽隨機數分布在了15個二維平面上。在這種要求面前,c的值最好:
- 是質數 (c = 49297就是質數)
- 接近
,(m = 233280時為49297.86460172205)
所以有了這樣一些基本的標準,能夠選擇的參數範圍就小了很多,弄個程序跑下Spectral Test,就能得到可選的參數組。
如果想要更加詳盡的了解LCG偽隨機數生成器的性質以及參數選取、測試的數學理論,可以嘗試閱讀《計算機程序設計藝術》卷2第3章。參考資料:
[1] http://nuclear.fis.ucm.es/COMP-PHYS/RANDOM/RandomNumbers.pdf
[2] http://random.mat.sbg.ac.at/tests/theory/spectral/
[3] Knuth, Donald E. (1981), The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, p. 89.
為啥不用random? 新瀏覽器 可能會用 音效卡噪音 因素加入到 隨機數生成的方法中去。
在瀏覽器里玩的話,如果自己來搞,也許陀螺儀 等設備的 一些 信息的加入。也可以增加隨機演算法的健壯性。如果再加入一些用戶態 比如 滑鼠坐標 滾動條位置啊 等等都參與其中 都可以把隨機性 這件事 做到更好 會不會更有趣些?
順便說一下,這個代碼是有問題的。
首先,rand函數裡面today沒有var,會造成全局污染,其次,如果你以很高的頻率調用這個隨機函數,會出現一大堆相同的數值。雖然js的效率比較低所以重複的次數不會很多……大概會重複個10~20次……這個和各種因素有關。。
你可以這樣試試
for (var i = 0; i &< 1000; i++) console.log(rand(10));
這玩意應該是這樣的。
rand = (function(){
var today = new Date();
var seed = today.getTime();
function rnd(){
seed = ( seed * 9301 + 49297 ) % 233280;
return seed / ( 233280.0 );
};
return function rand(number){
// return Math.ceil(rnd(seed) * number);
return Math.ceil(rnd() * number);
};
})();
myNum = (rand(5));
應該這樣會合理一些。
線性同餘生成器,常用的一組參數。
公式很簡單,a,c,m分別就是你這3個數字:
適用這個公式,類似的還有很多組合。
維基百科有這個演算法的介紹,以及很多常見組合的來源:
Linear congruential generatorLinear congruential generator
你這個流派,可能是來自Numerical Recipes:
Original source of #x60;(seed * 9301 + 49297) % 233280#x60; random algorithm?
return seed / ( 233280.0 );
想問下這裡的233280.0 為什麼要帶個一位小數?
酷帖留名~,再修改一小下
var rand = (function(){
var seed = (new Date()).getTime()
function r(){
seed = (seed*9301+49297)%233280
return seed/(233280.0)
}
return function(number){
return Math.ceil(r()*number)
}
})()
推薦閱讀:
※大學學的不是喜歡的專業怎麼辦?
※寫代碼時,縮進使用 tab 還是空格?
※計算機系學生,感覺自己編程能力很差勁,怎麼提高自己編程能力?
※遊戲編程裡面有哪些經典或者很酷的演算法?
※為什麼很多人喜歡 Python?
TAG:前端開發 | JavaScript | 演算法 | 數學 | 編程 |