7.1 随机数
•
随机数在随机化算法设计中扮演着十分重要的角色。在现实计算
机上无法产生真正的随机数,因此在随机化算法中使用的随机数
都是一定程度上随机的,即伪随机数。
•
线性同余法是产生伪随机数的最常用的方法。由线性同余法产生
的随机序列 a0,a1,…,an ,满足:
•
其中 b0 , c0 , dm 。 d 称为该随机序列的种子。如何选
取该方法中的常数 b 、 c 和 m 直接关系到所产生的随机序列的随
机性能。这是随机性理论研究的内容,已超出本书讨论的范围。
从直观上看, m 应取得充分大,因此可取 m 为机器大数。
,2,1mod)(
1
0
nmcbaa
da
nn