目前最常用的随机数产生器是下面这种模式,叫做Linear Congruential Method:
Xn+1 = (aXn + c) mod m, n >= 0
变换为k步长的形式如下:
Xn+k = (a^kXn + (a^k - 1)c/b) mod m, k >= 0,n >= 0,其中b = a - 1
Linear Congruential Method的若干问题:
1) m的选取:
m应该足够大,因为LCM法产生不同的数值最多为m个;m的选取还应该使计算机计算时尽量快。
让m等于计算机的字长w计算起来会非常快,但人们往往选取m=w ± 1。这是因为:
如果d整除m,令
Yn = Xn mod d,
那么
Yn+1 = (aYn + c) mod d.
即{Xn}序列的低位会陷入一个更小的循环,这个循环的最大长度为d。即Xn序列低位的随机性没有高位的随机性强。
可以用快速的方法来计算aX mod (w+1),基于下面这个式子:
aX = q(w + 1) + (r - q) if aX = qW + r
aX mod (w-1)的计算与此类似。
2) a的选取:
a的选取应使序列的周期尽量长。
Theorem:Linear congruential sequence的周期为m当且仅当:
i) c与m互质;
ii) b = a - 1,对m的每一个质因数p,b是p的倍数;
iii) 如果m是4的倍数,b是4的倍数。
potency
b = a - 1,potency定义为使下式成立的最小的s:
b^s ≡ 0 (modulo m).
由于:
Xn = c(n + C(n,2)b + ... + C(n,s)b^(s-1)) mod m.
因此,s的大小,即potency,能够表征序列的随机度;如果potency太小,如为1,则Xn ≡ cn (modulo m),这显然是一个非常不随机的序列。
其他产生随机数的办法
Xn = (a1Xn-1 + ... + akXn-k) mod p,p为素数
能够产生周期最长为p^k-1的序列。
Randomizing by shuffling的办法:
利用两个随机数序列Xn和Yn,将Xn产生的数放在一个池中,然后由Yn产生一随机位置来取出这个池中的数,并将取出的随机数由新产生的Xn来填充。这个办法在某些情况下能增强随机性。
改进的办法是让Xn和Yn为同一个序列,即随机位置和池中的数值都有Xn产生。
[The art of computer programming,Random Numbers]