资源描述：
《综述_产生伪随机数的若干新方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、年月数值计算与计算机应用第期’‘,综述产生伪随机数的若干新方法杨自强魏公毅中国科学院计算数学与科学工程计算研究所北京应用物理与计算数学研究所计算物理实验室丫丫五厦入入七。坛几夕。夕。‘。夕,呷‘云访邝呷。,云。夕坛红乞。。‘,乙二印呷,饭即瓦,‘”葱,,坛。‘红,一,,盯,,一一一一,,,,,一,产生随机数是方法的基础本文简要综述有关方法重点是近年来国际上,包括作者们,热门的一些新方法与评论的一些工作除了线性同余法外还将涉及非线性同,,,,余法序列进位加一借位减发生器法以及乘子和增量也在递,也介绍组合发推中变化的复合素数发生器和基于混沌映射产生随机数的方法除此之外生器
2、,特别是介绍,用于证明组合发生器优于单个发生器的一些理论结果基于这些理论可实际,我地构造优良的随机数发生器在本文中们也注意收集和指出某些发生器在应用中可能存在的一些问题,一本文所讨论的随机数只涉及传统方法中使用的伪随机数至于近几年在数学金融的超高维积分维数高达千维计算中十分有效的拟一方法所使用的拟随机数将在另文讨论年月日收到计算物理实验室基金试点项目资助数值计算与计算机应用年怪线性同余序列的长周期相关与稀疏网格结构线性同余法与乘子的选取,,线性同余法历史悠久因其算法简单至今仍被广泛使用其递推式为瓜瓜,乞,,⋯,,、,。式中参数和分别称为乘子增量和模如果这些参数和种子初
3、值都指定序列也就确定下来了通常取八弋,乞,,⋯,,。,作为区间上均匀分布的随机数线性同余法中一个最重要的特例是这时也称乘同余法给定,,后其余参数的选取应保证序列茂有最大的周期例如若,,为素数则应为的原根判断原根的一个易于操作的准则见是对汀一的任一素因子。都有一并汀,平方根准则与商显然参数的选取还应保证序列有较好的统计品质历史上,,这时在了附近取值,例常用平方根准则指导乘子的选取丽如弋一茂一,就是一个十分著名的随机数发生器这样做的主要考虑是便于计算机上实现另外是受,。二,,的一步顺序相关估计式的影响根据该式若了丽则瓜茂有,,较小的相关但是有些作者对平方根准则有异议例如可
4、见一等人的论著此外根据理论和经验检验得到的个最好乘子当”,‘一的可精时也与平方根准则不符特别是给出了瓜凡确计算的分布他使用一个与一步顺序相关有紧密关系的偏差准则又其含义见节使选简化为选取与若是的幂,则若是素数,则具有最小商的。·所谓商是指辗转相除法所得的商。的和引·艺各吼的定义如下,,’一一一,”,几一。,咖一二,式中川卜⋯卜甄且各步的内取最小值二,易知当了丽时有二认丽从而其商不会是最小的一个线性同余序列的长周期相关,为说明线性同余序列的长周期相关现象先看一个简单例子弋凡,此发生器产生周期为的如下序列·瓜,,,,,,,,,,,,,,,,,,,一为容易看出此序列的前半段
5、与后半段强相关今写出与它相关系数为的另一序列一、,,,,,,,,,,,,,,,,,,期杨自强等综述产生伪随机数的若干新方法,,显然后者只是前者前后两半段位置的互易换句话说线性同余发生器所得的序列其前后两半段是强相关的一,已从理论上证明了所有线性和非线性同余序列都存在长周期相关现象在,平行计算中我们应特别警惕和回避这种现象如果几个并行处理器分,别使用同一个同余序列的不同段落分割时应避开具有强相关的分点线性同余序列的稀疏网格结构与谱检验,,,线性同余序列的最大缺陷是高维不均匀性当把相继的个随机数汗弋⋯是维,茂看作空间上的一个点的座标时这些点只散布在维空间中的少数几个超平,
6、,面上并形成稀疏网格结构二维情形可见节的图均匀随机数是产生其它分布随机变数的基础用具有稀疏网格结构的线性同余序列产生其它分布随机变数时也可能会出,‘,八现一些不应有的问题见等例如两个独立的均匀随机数可经一,变换得到一对独立的正态分布随机变数从人从二‘二、‘,,、,、但如果来自同余序列则点,‘只落在一条螺线上这时从与就不是独立的了,人们在构造线性,自从发现高维稀疏网格现象之后同余发生器时自然要考虑参数的选择应使网格尽可能不那么稀疏这导致了一系列度量和检验网格稀疏程度的准则出现例如,,,,相邻平行超平面之间最大距离平行超平面的最小数目点间距和,,,检验等这些检验都属于理论
7、检验只要给定参数便可进行检验而不必实际产生具体,的序列基于相邻平行超平面之间最大距离的检验亦称谱检验该距离越大发生器越差‘,设乘同余发生器为茂则谱检验计算归结为求解极值·。‘一‘一,一、了矛爹⋯矛⋯映称为,,二姚式中该发生器的维精度而便是相邻平行超平面之间的最大距,离人们已经找到了上述极值问题的可行算法至少对三是如此也找到了最大距离的下限对于给定的值而言实践中人们还发现谱检验与该类的其它方法有很强的相关一,,性因此谱检验成为这类方法中最为流行而且也是最为重要的一个,怪逆同余与非线性同余发生器年代末,开始许多学者讨论称之为逆同余的一类新发生器这是非线性
