_jaskell

<< Haskell Tips: fail 函数的注意事项 | 首页 | 2006-10-30 线性同余与伪随机数产生器 版权声明 :转载时请以超链接形式标明文章原始出处和作者信息及 本声明 http://jaskell.blogbus.com/logs/3727980.html 线性同余与伪随机数产生器 通常,我们访问一个列表时会采用以下方法: for index in xrange(len(slist)): process(slist[index]) 或者: for item in slist: process(item) 以上这都是顺序访问列表中所有元素的一种办法,但有时候我们希望采取的方法是能够尽量随机地访问列表中所有元素,这时有没有也和上面一样简洁有效的办法呢? 对于这个问题我们可以做一个转换,看成是一个这样的问题:我能够在一个循环中随机地、不重复地依次产生出从 0 到 n 之间的所有整数吗?看到这个问题你大概想到了这和“伪随机数产生器”很类似,是的,我们要做的就是一个“伪随机数产生器”,如果有了这个“伪随机数产生器”我们就可以很方便地写出以下代码: for index in RandomNumberGenerator(n): process(slist[index]) 有什么方法可以方便地做到这些呢?答案是“线性同余方法”,我们现在来了解一下这个方法,从维基上我们可以查到如下信息: 线性同余方法 ( LCG )是个产生 伪随机数 的方法。 它是根据 递归 公式: 其中 A , B , M 是产生器设定的常数。 LCG 的周期最大为 M ,但大部分情况都会少于 M 。要令 LCG 达到最大周期,应符合以下条件: B , M 互质 ; M 的所有质因子的 积 能整除 A − 1 ; 若 M 是 4 的 倍数 , A − 1 也是; A , B , N 0 都比 M 小; A , B 是正整数。 如果想看英文解释的可以看以下这些: Linear congruential generators (LCGs) The period of a general LCG is at most M, and in most cases less than that. The LCG will have a full period if: 1. B and M are relatively prime 2. A-1 is divisible by all prime factors of M. 3. A-1 is a multiple of 4 if M is a multiple of 4 4. M > max(A, B, V 0 ) 5. A > 0, B > 0 从上面我们可以了解到要产生一个周期为 M 的“伪随机数产生器”必须满足的条件,现在我们就执照这些要求去实现一个我们需要的“伪随机数产生器”吧。 假设这里我们的 M = 0x1000000 ,由于 M 是 4 的倍数,因此也要求 A-1 也是 4 的倍数,另外我们来看一下 M 的质因子,由于我们给出的 M 是个十六进制数,因此所有的质因子都是 2 ,这就要求我们的 A-1 也都能够被 M 的所有质因子的积整除,比如 2 、 4 、 8 、 16 等等,要达到这两个要求很容易,我们这里取一个相对较大的数 A 为 0x15A51 ,则我们可以看到 A-1 满足以上两个要求。由于对于 B 的要求很简单,只要求 B 与 M 互质即可,因此我们可以简单地设置 B 为 1 。这样我们来写一个周期为 0x1000000 的“伪随机数产生器”吧: def random(seed): return (seed * 0x15A51 + 1) % 0x1000000 def test(): index = seed = 1 while True: process(slist[index]) index = random(index) if index == seed: break 现在就可以“随机而且不重复地”访问一个有 0x1000000 个元素的列表了。可是如果列表的元素有变化时,如果设计这个“伪随机数产生器”呢?这个问题就留在以后有时间再分析吧。 随机文章: 趣味问题: 给出一个整数 n ,求在 0 到 n 之间出现的 '1' 的总个数 2006-09-18 IP地址识别与有穷状态机 2006-09-10 解最短路径的“狄斯奎诺”算法 (Dijkstra's shortest path algorithm) 2006-09-07 Haskell Tips 2006-09-05 非递归方式的全排列方法 2006-09-03 收藏到: Del.icio.us Tag: 线性同余 伪随机数 产生器 引用地址: jaskell 发表于 15:04:28 | 编辑 | 继续话题 | 转发 | 推荐 发表评论

原始快照:web.archive.org