使用线性同余法生成随机数

one234

随机性的研究广泛存在于很多自然科学领域,如统计学,密码学,博弈论,量子力学等。

经典物理中,随机现象本质上并不是随机的,因为经典物理过程的所有变量都是可以被模拟的,一旦掌握了事件发生的所有外在因素,就可以算出结果,所以任何基于经典过程模拟的随机,都是伪随机。

量子物理中,量子态的坍缩过程是真正随机的,其随机性是微观粒子固有的内禀特性,与任何其他外部变量无关,所以量子系统的随机现象是真随机

经典计算机算法均具备确定的特性,所以真随机数无法由算法来生成。基于量子系统的随机数发生器目前使用成本比较高,对于绝大多数的日常应用,只要样本分布达标,伪随机数也可以满足要求。

线性同余法是一种古老的生成随机数的方法,算法简单容易理解,曾经被广泛应用,美国莱默尔在1951年提出,但由于其存在很大缺陷,现在已经弃用。

算法的递归公式定义如下:

如果期望结果达到最大周期,取值应该满足下述条件:

1> m 的所有质因数都能整除 a-1

2> 若m是4的倍数,a-1 也是

3> a, c, Xo  都比 m 小

例如:设 m=28,a=15,  c = 5,  Xo = 1 , 则有

所得随机序列为 20, 25, 16, 21, 12, 17, 8, 13, 4…

计算机编程语言Python计算示例:

def rng(m=28, a=15, c=5):
    rng.now = (a*rng.now + c) % m
    return rng.now
rng.now = 1
print([rng() for i in range(10)])

随机数生成还有其他算法,像平方取中发生器、乘积取中发生器、常数乘子发生器和斐波那契发生器等。有兴趣的读者可以自行研究。

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注