What is the period of the Berkeley random(3B) generator

[Tim Monks]

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 at bhpmrl.oz.au