|
|
网上常能见到的一段 JS 随机数生成算法如下，为什么用 9301, 49297, 233280 这三个数字做基数？
关注者
1,374
被浏览
191,865
7 个回答
Observe only
很多人认为这是简单的Magic Number，其实这背后有内在的原因，这三个数字并不是随便乱选出来的。
入门级的选择标准
这种伪随机数生成器叫做线性同余生成器（LCG, Linear Congruential Generator)，几乎所有的运行库提供的rand都是采用的LCG，形如：
I_{n+1}=aI_n+c\ (mod\ m)
生成的伪随机数序列最大周期m，范围在0到m-1之间。要达到这个最大周期，必须满足
- c与m互质
- a - 1可以被m的所有质因数整除
- 如果m是4的倍数，a - 1也必须是4的倍数
以上三条被称为Hull-Dobell定理。
作为一个伪随机数生成器，周期不够大是不好意思混的，所以这是要求之一。
可以看到，a=9301, c = 49297, m = 233280这组参数，以上三条全部满足。
进阶级的选择标准
要在伪随机数生成器界混，仅仅入门是不够的。
从工程的角度来讲， (m-1)a+c 的值要（在合理的范围内）足够小，以避免溢出的问题。
从安全（实用）性的角度来讲，还要满足良好的随机性，这一点可以通过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就是质数）
- 接近 (\frac{1}{2}-\frac{1}{6}\sqrt{3} )m ,(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/te sts/theory/spectral/[3] Knuth, Donald E. (1981), The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, p. 89.
一般在游戏开发的时候我们需要使用一些随机数字，以便可以控制或者再现游戏操作。举个例子说明：例如，在设置关卡或重置关卡时，您可能希望看起来是随机的，但是每次载入关卡时都一样。那么这时候我们该怎么做？其实有很多方法来实现所谓的“种子随机生成数字”，如果你想要的算法的任何细节，你可以例如检查这个链接（ http://www.ict.griffith.edu.au/anthony/info/C/RandomNumbers）。但基本上他们原理都是一样的：你用一个“种子”（一个你选择引导算法的数字）初始化算法。每一个种子都会返回自己独特的一组“随机”数字，例如：每次我种下数字6，我都会得到相同的一组生成的“随机”数字。每次种子10号，我得到相同的一组“随机”号码，这取决于你到底设置因子是'6'还是'10'等等 ...
由于这个事实：种子随机数是可预测的，这并不坏，但只是不使用它来进行加密操作等目的......
下面有一个简单的算法，它非常简单，当然，这也不是什么新东西。
// 初始化种子
Math.seed = 6;
Math.seededRandom = function(max, min) {
max = max || 1;
min = min || 0;
// 根据数值进行随机值计算
Math.seed = (Math.seed * 9301 + 49297) % 233280;
var rnd = Math.seed / 233280;
return min + rnd * (max - min);
}
你可能会问：为什么是（seed* 9301 + 49297）％233280，这几个数字又是什么原因？好吧！答案既简单又复杂：9301，49297和233280的组合提供了一组非常均匀的“随机”数字。 但是请不要问为什么，这是复杂的部分，一些非常聪明的人很早以前就知道了这些数字，我也不能告诉你他们是怎么做到的，无非是深入的了解了一些算法、定理以及工程等方面的概念。比如线性同余生成器、Hull-Dobell定理等。
这里进行了一个项目的测试以便测试该算法的性能，以及生成集的分布如何：只需点击运行按钮，看看结果，这对于100.000个数字仍然在10-15ms的范围内，因此相当快。 数字的分布也是一样的，你可以看到。
Math.seed = 6;
Math.seededRandom = function(max, min) {
max = max || 1;
min = min || 0;
Math.seed = (Math.seed * 9301 + 49297) % 233280;
var rnd = Math.seed / 233280.0;
return min + rnd * (max - min);
}
var c, r = 0,
l = 100000,
t,
random = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
seededRandom = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
for (c = 0; c < l; ++c) {
r = 5+5;
}
t = new Date().getTime();
for (c = 0; c < l; ++c) {
r = Math.random();
random[(r * 10) | 0] += 1;
}
s = '';
s += ('<p>生成 ' + l + ' 随机数: <br/>');
s += ('Math.random(): <b>' + (new Date().getTime()-t) + 'ms</b>' );
s += ('<br />随机分布：'+random.join(', ')+' <hr /> ');
t = new Date().getTime();
for ( c = 0; c < l; ++c ) {
r = Math.seededRandom();
seededRandom[(r*10)|0] += 1;
}
s += ('Math.seededRandom(): <b>' + (new Date().getTime()-t) + 'ms</b>' );
s += ('<br />随机分布：'+seededRandom.join(', ') + '</p>');
$('body').html(s);
在游戏开发中我们可以应用这个功能，所以不管你多长时间重新加载页面，关卡的级别都是一样的，我所做的只是用“Math.seededRandom（）”替换“Math.random（） ”。