tim@bhpmrl.oz.au (Tim Monks) (11/07/90)
Can anyone supply a proof that the period of the Berkeley random(3B) random number generator is r.(2^r - 1) ? I have looked at the source code for random(3B) and it appears that it is just a lagged-Fibonacci generator of the form : state(n) = ( state(n-r) + state(n-s) ) mod (2^32) x(n) = ( state(n) >> 1) mod (2^31 -1) Where x(n) is the sample returned by the call to random(3B), and state is an internal table of longs, addressed as a circular list. When the state table takes its default size of 128 bytes, the lags are r=31, s=3. The comments in the code claim without proof that the periodicity of the generator is approximately r.(2^r -1), or approximately 15.(2^31 -1) for the default table length. As I understand Knuth (The Art of Computer Programming, Vol 2, pp.26-27) a generator of the form : x(n) = ( x(n-r) + x(n-s) ) mod (2^m), r > s will have a period of length 2^f.(2^r -1) where 0 <= f < m. Working through exercise 11c, p34 (ibid), I think that the period of the generator : x(n) = ( x(n-31) + x(n-3) ) mod (2^32) is 2^31.(2^31 - 1) ~ 2^62. Can anyone refute or support this ? Thanks, Tim -- Dr. Tim Monks Image Processing & Data Analysis Group | (direct) (+61-3)566-7448 BHP Melbourne Research Laboratories | (switch) (+61-3)560-7066 245 Wellington Rd, Mulgrave, 3170, | (fax) (+61-3)561-6709 AUSTRALIA | (EMAIL) tim@bhpmrl.oz.au