百科问答小站 logo
百科问答小站 font logo



网上常能见到的一段 JS 随机数生成算法如下,为什么用 9301, 49297, 233280 这三个数字做基数? 第1页

  

user avatar   akfish 网友的相关建议: 
      

很多人认为这是简单的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]

nuclear.fis.ucm.es/COMP

[2]

random.mat.sbg.ac.at/te

[3] Knuth, Donald E. (1981), The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, p. 89.




  

相关话题

  过度依赖框架有什么不好? 
  如果你有很多枚鸡蛋,和一个n层高的楼,你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解? 
  程序员发现 Bug 的时候是怎样一种心境? 
  为什么很多计算机上的阿拉伯数字零(0)中间都有一个斜杠(/)? 
  编写基于机器学习的程序,有哪些编写和调试的经验和窍门? 
  1 不可以被 3 除尽,但为什么圆可以被三等分? 
  计算机视觉顶级会议论文中比较适合初学计算机视觉的人做的复现实验有哪些? 
  关于波达规则 孔多塞悖论和阿罗不可能定理? 
  0基础开始,Leetcode200道题要多久左右? 
  普通程序员如何正确学习人工智能方向的知识? 

前一个讨论
中国农历各月份别称里一月首阳,二月绀香,首阳绀香指的是什么?
下一个讨论
从国家层面来讲,中国的游戏产业算成功吗?





© 2024-11-08 - tinynew.org. All Rights Reserved.
© 2024-11-08 - tinynew.org. 保留所有权利