Posted on 2008-04-15 14:01
Fox 阅读(4323)
评论(3) 编辑 收藏 引用 所属分类:
G游戏编程
Author: Fox
John von Neumann说：Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.
所以，在讨论算法实现随机数的时候，总是说“伪随机数”。
现在，应用最广的随机数生成算法是由Derrick Henry Lehmer1951年给出的线性同余法：
Xn+1 = ( aXn + c ) mod m, n>=0.
在上一篇伪随机数的论述中，并没有给出X0, a, c, m的取值规则，只是给出了ANSI C和Microsoft Visual C++的实现。
在这儿我们可以自己先思考一下，我们期望从上式中得到的随机数应该满足：
1) 上式的输出足够随机，这是最基本的要求；
2) 上式给出尽量多的输出，越接近m个越好（不可能超过m），即周期尽量长，最好为m，这样才能保证上式满足均匀分布（m个数在周期m中各出现一次m个数出现的概率相等）；
3) 上式的生成速度足够快。
最容易想到的，m的取值为计算机字大小（如2^32或2^64）。
但是这儿有个很严重的问题：Xn低位的随机性很弱。原因如下：
令d|m, 且
Yn = Xn mod d
则
Yn+1 = ( ( aXn + c ) mod m ) mod d
= ( aYn + c ) mod d
上述表达式的意义即：Yn为Xn低k位（d=2^k），这样的Yn序列形成周期为d甚至更短的同余序列。举例说明：d为2^1时，Yn为Xn的最低位（可假定为1或0），若Yn+1 != Yn，则Yn+2 == Yn必定成立，仅当a、c皆为奇数时Yn、Yn+1将0、1交替，否则，为常数（0或1）。
暂时抛开随机性不管，先找到周期为m的随机序列中的取值规则。
Donald Knuth在The Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2节对m, a, c和X0取值规则的表述：
1) gcd(c, m) = 1. 即c, m互素，再白一点，c, m除1之外没有其他公因子；
2) 任给质数p, p|m ==> p|(a-1). 即m%p==0，则(a-1)%p==0。
3) 4|m ==> 4|(a-1). 即m%4==0，则(a-1)%4==0。
这个证明过程对于我这样的数论基础不是很扎实的搞应用技术的人来说有点难以理解了。有兴趣的话，还是去看3.2.1.2的证明吧:-)。
上面的规则告诉我们，满足了上述规则后，可以保证序列周期为m。对于前面提到的关于随机性的问题，既然Xn低位的随机性比较弱，可以只取Xn的高位作为输出。高位的随机性和统计意义由a, c确定，其取值涉及统计检验，具体的也还是看3.3吧。
这篇文章解决了具有统计意义的随机数的部分理论问题。
PS: 之前曾经BS过Windows Live Writer，当时觉得Writer编辑功能太少，不能直接设定链接文字的字体颜色，知道CSS可以设定之后，又觉得Word 2007编辑的Blog转成html之后太大，而且也知道Word 2007上面是可以设置链接的target为_blank的。现在发现Writer还是很不错的了，原来是可以设定格式的，也可以直接编辑html，而且可以Web预览，链接还可以加入到链接词汇表，挺方便的。
越来越发现Wikipedia是个和Google一样的好东西！