(2005)
数 学 杂 志
.(PRC)
一般组合逆同余法的算法与偏差分析
*
李 琼1,金升平1,陈定方2
(1.武汉理工大学统计学系,湖北武汉,430063)
(2.中国科学院计算所智能信息处理开放研究实验室,北京,100080)
摘要:本文研究了逆同余产生伪随机数的方法,给出了一般的组合逆同余法算法.将已
有结果进行理论比较,得到了一个较好的伪随机数序列的产生方法.
关键词:计算机模拟;伪随机数;逆同余法;组合逆同余法
MR(2000)主题分类号:30Q 中图分类号:
文献标识码:A 文章编号:0255-7797(2005)02-0171-04
1 引言
线性同余发生器固有的晶状结构的缺陷,因其太规则而无法适合某些问题的模拟.
许多非线性伪随机数发生器被提出而且进行了广泛的研究,逆同余发生器是非线性伪随
机数发生器中的一种,由于它在任意k维空间的随机性的机理研究得较为深入,因而是一
种很好的发生器[1+6].利用组合逆同余发生器,可以得到周期更长、性能优良的伪随机数.
随机数序列的统计独立性是最重要的衡量指标,检验均匀分布伪随机数序列的相邻
项的统计独立性的方法是序列检验.给定维数k,[0,1)k集合中任意N 个点t0,t1,…,tN-1
∈[0,1)k,定义偏差指标
DN(t0,t1,…,tN-1)=sup
J
FN(J)-V(J) (1)
这里上确界的取值范围是[0,1)k中的所有子区间J,FN(J)是t0,t1,…,tN-1落入J中的点
的个数除以N,V(J)是J的k维体积.设x0,x1,… 是[0,1)上的纯周期的且周期为2的
均匀伪随机数序列,考虑序列x0,x1,… 的相邻项组成的向量
xn = (xn,xn+1,…,xn+k-1)∈ [0,1)k, n=0,1,…,2-1
记 D(k)2 =D2(x0,x1,…,x2-1) (2)
2 逆同余法
逆同余发生器主要有两种类型,一是模数为质数,另一种是模数为2的幂,下面介绍
模数为质数的情形.设质数p≥5,记Zp = 0,1,…,p-{ }1 ,Zp是质数p的剩余同余类,
* 收稿日期:2002-09-12 接收日期:2003-09-18
作者简介:李 琼(1964-),女,湖北黄石,副教授,硕士,主要研究统计与优化计算.
Email:qli,
因而是一个p阶有限域.再记Z*p = 1,…,p-{ }1 ,对任意c∈Z*p ,c关于Zp 的乘数的
逆记为c-1,特别规定0-1=0,选择a,b∈Z*p 使得x2-bx-a是域Zp上的一个二次本原
多项式[9],选择初值y0,产生Zp 上的序列如下:
yn+1 =ay-1+b modp, n=0,1,2,… (3)
由 Fermat 小 定 理[8] 知,y-1 = yp-2mod p. 序 列 y0,y1,… 的 周 期 为 p 且
y0,y1,…,yp-{ }1 =Zp.由此我们得到[0,1)上的均匀伪随机数序列x0,x1,…,其中xi=
yi
p
.以下设ymodm为整数y取模m 的最小非负余数,y=zModm表示整数y、z关于
模m同余.
3 一般组合逆同余法的算法
由(通常的)逆同余法产生的序列,组合得到更一般的组合逆同余序列的算法如下.
设r个互不相同的质数p1,p2,…,pr≥5,m=p1p2…pr,(y(i)n )n≥0∈Zpi 为如下定义的序
列
y(i)n+1 =ai(y(i)n )pi-2+bimodpi n≥0, i=1,2,…,r (4)
其中z2-biz-ai为Zpi 上的本原多项式,则(4)定义的(y
(i)
n )n≥0∈Zpi 是纯周期的且周期
为pi,记xn(i)=yn
(i)
pi
,n≥0,mi = mpi
,i=1,…,r,令5i(i=1,…,r)是任意r个整数,
考虑(x(i)n )n≥0 的组合后再取小数部分
xn =51x(1)n +…+5rx(r)n mod1 (5)
其中xmod1表示实数x的小数部分.由(6)式决定a、b两个常数
a=Σ
r
i=1
m2i52iaimodm, b=Σ
r
i=1
mi5ibimodm (6)
定理1 设最大公约数gcd(pi,5i)=1,i=1,…,r,a,b由(6)式确定,只要
y0 =Σ
r
i=1
mi5iy(i)0 Modm 则由 yn+1 =ay-(m)-1n +bmodm, n=0,1,2,…
生成的序列满足
yn =Σ
r
i=1
mi5iy(i)n modm,xn =Σ
r
i=1
5ix(i)n mod1
其中(y(i)n )n≥0 ∈Zpi 由(4)生成,xn
(i)=yn
(i)
pi
,n≥0, i=1,…,r.
证 首先注意到mi=0modpj,2i8j,因此以下两式等价:
yn =Σ
r
i=1
mi5iy(i)n modm Tyn =mi5iy(i)n Modpi, i=1,…,r
下面用归纳法证明yn =mi5iy(i)n modpi,i=1,…,,有
y0 =Σ
r
j=1
mj5jy(j)0 Modpi=mi5iy(i)0 Modpi.
若对 2n≥0,有yn =mi5iy(i)n modpi,i=1,…,r,则由yn+1 =ay-(m)-1n +bmodm知
yn+1 =ay-(m)-1n +bmodpi
=Σ
r
j=1
m2j52jajy-(m)-1n +Σ
r
j=1
mj5jbj modpi
271 数 学 杂 志
=mi252iaiy-(m)-1n +mi5ibimodpi
=mi5i[mi5iai(mi5iy(i)n )-(m)-1+bi]modpi
=mi5i[aimi-(m)5-(m)i (y(i)n )-(m)-1+bi]modpi
由Fermat小定理知m-(m)i 5-(m)i modpi=1以及(y(i)n )-(m)-1y(i)n modpi=1,
(y(i)n )pi-2y(i)n modpi=1,再由逆元唯一性知(y(i)n )-(m)-1 = (y(i)n )pi-2modpi,于是
yn+1 =mi5i[ai(y(i)n )pi-2+bi]modpi=mi5iy(i)n+1modpi
这就是所需要的结果.
定理2 设gcd(pi,5i)=1,pi为质数,x2-bix-ai是域Zpi 上的一个二次本原多项
式,y(i)n+1 =ai(y(i)n )-1+bi,z(i)n+1 =a52i(z(i)n )-1+b5imodpi, n≥0, i=1,2,…,r,
则当z(i)0 =5iy(i)0 时,有z(i)n =5iy(i)n ,n=1,2,3,….
证 下面用归纳法证明.n=0时结论成立,假设对n≥0,有z(i)n =5iy(i)n ,则
z(i)n+1 =a52i(z(i)n )-1+b5i =a52i(5iy(i)n )-1+b5i =5i a(y(i)n )-1+( )b =5i(y(i)n+1)-1
这就是所需要的结果.
文献[5]的结果相当于定理1中5i=1(i=1,…,r)的特殊情况.利用定理1,只需计
算同一组逆同余序列,就可组合出多种周期等于组成序列的周期之积,但性能优良的伪随
机数序列,因而极大地节省了计算量.
4 一般逆同余法组合的偏差分析
由(1)所定义的偏差指标,是分析伪随机数随机性和独立性的重要手段,由定理2及
文献[5]的结果,可以得到如下两个定理,这里略去其证明过程.
定理3 设k≥2,其它条件如定理1,则有
D(k)m < 1
m
1
2
(2
(
logm+75
)kP
r
i=1
(2k-2+ k
p
1
2i
)+km
定理4 对任意k≥2,其它条件如定理1,则存在组合序列满足
D(k)m ≥ 12((+2)
m-
1
2P
r
i=1
pi-3
pi-( )1
1
2
对于固定的m的质因数个数r,k≥2,定理3说明对任意组合逆同余法产生的序列有
D(k)m =O(m-
1
2(logm)k),定理4说明存在组合逆同余法产生的序列,使D(k)m 至少有m-
1
2 的
数量级.然而如果m仅由较小的质数组成,则r是(logm/loglogm)的数量级,因而
P
r
i=1
(2k-2+ k
p
1
2i
)=O(m’)
对任意’ > 0 成立,这样就可得到 D(k)m = O(m-
1
2+’)对任意’ > 0 成立.因为
P
r
i=1
pi-3
pi-( )1
1
2
≥2-
r
2,类似地可以得到存在组合逆同余法产生的序列,使D(k)m 至少有
m-
1
2-’的数量级.我们注意到,[0,1)k 上的独立的均匀分布的m 个点几乎总是有数量级
m-
1
2(loglogm)
1
2,在这种意义上,本文提出的一般组合逆同余伪随机数是真正随机数的一
个很好的模型.
371 李 琼等 一般组合逆同余法的算法与偏差分析
参考文献:
[1] Eichenauer-HerrmannJ.,-linearcongruentialpseudorandomnumbergenerator[J].
,1986,27:315-26.
[2]
[J].,1989,52(185):135-144.
[3] [J].Math.
Comp,1991,56(193):297-301.
[4] ofa new class ofinversivecongruential
pseudorandomnumbers[J].,1993,60(196):375-843.
[5] [J].Math.
Comp,1994,63(207):293-299.
[6] Eichenauer-HerrmannJ.,:
anaverage-caseanalysis[J].,65(213):215-225.
[7] 金升平,陈定方.乘同余发生器的概率分布与快速算法[J].数据采集与处理,2002,17(2):142-
145.
[8] 华罗庚.数论导引[M],北京:科学出版社,1979,24-34.
[9] 阮传概.近世代数及其应用[M],北京:北京邮电学院出版社,1988,272-276.
ONTHEALGORITHMANDDISCREPANCYANALYSIS
OFCOMPOUNDINVERSIVECONGRUENTIAL
PSEUDO-RANDOMNUMBERS
LIQiong(李 琼),JINSheng-ping(金升平)
(,WuhanUniversityofTechnology,Wuhan430063,China)
CHENDing-fang(陈定方)
(,Beijing100080,China)
Abstract:Byusinginversivecongruentialmethod,thispaperresearchesthealgorithmtogenerate
theoreticalcomparisonthepreviousresultsandthepresentones,itputsforwardagoodmethodto
generatepseudo-randomserials.
Keywords:computersimulation;pseudo-randomnumber;inversivecongruentialmethod;
compoundinversivecongruentialmethod
2000MRSubjectClassification:30Q
471 数 学 杂 志
