|
本帖最后由 lisa527 于 2013-11-18 13:39 编辑
( P0 p q0 ~ b$ j$ R; S( B- L7 m- t
这个问题困扰我好久了,现在一次性了结
4 `8 K n- b" U% ]---------------------------------------------------------------------------------------------------
! v' P& Y2 u* x. c, t- M& U-随机数是怎么生成的
6 R0 c. m7 r0 N7 h4 o* x, K基于计算机方法生成的随机数称为伪随机数,因为其计算方法已知,不是完全的随机。现在比较流行的生产伪随机数的方法是 Linear Congruential Generation (混合同余法).
' F% i1 T3 K G, SLinear Congruential Generation (LCG)[1]方法如下:
$ X/ ^8 Z8 i/ l# i/ ]' q9 M, AX_i=(aX_(i-1)+c)mod m (1). ]. N" G3 y# m: K6 v
R_i= X_i/m
& q: U; M% i& e# A3 dSeed: X_0
( t' V5 L1 k& N7 v5 b* U: `9 e5 |, ^
# l4 f( a% u# D: o) z-什么是stream?$ w8 R! ]& h; c# U
基于m的限制,生成的随机数都是循环的,而且最大的循环周期是m。假设生成的随机数周期为P,随机数序列可以写作: X_0,X_1,…X_P,X_0,X_1…
/ A% T! a" I' w1 K正因为它的循环性,取0-P之间任何一个数做seed都可以生成整个随机数列。& p# j. w. c/ E1 Y; l
为了方便起见,我们把长度为P的随机数分为若干个随机数流(stream),比如说,分成b个,每个stream的长度为P/b: {X_0,X_1,…X_(P/b-1)}, {X_(P/b),…X_(2P/b-1)}…, ?' ^2 ]; Q+ O" ^0 W5 @
f7 }4 K8 e3 `* [* O+ e-Stream有什么用?. {/ p' f$ C$ l2 l7 E
通过观察(1)式可以得知,X_i 和 X_(i-1)是相关的。为了避免这种相关性,仿真时常常会选取不同的stream产生各个过程的随机数。
" T S8 e% H& R0 o/ q4 u7 f& y3 i' k) Q3 |
为此专门写了篇blog在http://blog.sina.com.cn/sui5277 |
|