math/rand package underlying algorithm

[athi...@gmail.com]

Hi all,

I was checking the documentation of the math/rand package but I couldnt find any mention on the generator algorithm.
I checked the source and it looks like a linear congruential generator, is this correct?

Regards,
Alex

[Anthony Martin]

No. It's an Additive Lagged Fibonacci Generator (ALFG)
described by S_n ≡ S_(n-273) + S_(n-607) mod 2^31.

It's the same code used in Plan 9's rand(2).

The comments refer to D. P. Mitchell and J. A. Reeds
(Don Mitchell and Jim Reeds, respectively). Presumably,
they came up with algorithm while working at Bell Labs.

I've never found a paper describing it.

Cheers,
Anthony

[Anthony Martin]

Anthony Martin <al...@pbrane.org> once said:
> athi...@gmail.com once said:
> > I was checking the documentation of the math/rand package but I couldnt
> > find any mention on the generator algorithm.
> > I checked the source and it looks like a linear congruential generator, is
> > this correct?
>
> No. It's an Additive Lagged Fibonacci Generator (ALFG)
> described by S_n ≡ S_(n-273) + S_(n-607) mod 2^31.

Sorry. I meant "mod 2^63". Plan 9's algorithm is mod 2^31.

Anthony

[Uli Kunitz]

Wikipedia has an entry about Lagged Fibonacci Generators. Additive is only one variant. The subtractive variant is discussed in Knuth's The Art of Computer Programming volume 2 chapter 3.6. As the Wikipedia article he mentions problems with birthday spacing tests as well as problem with high resolution simulations. Some mitigations are discussed.

It is definitely not appropriate for any cryptographic use and if it is relevant for your simulation work then you will know what to use anyway. 

[athi...@gmail.com]

Ok that helps a bit. I dont need crypto quality randoms since I work with simulations mostly. But the wiki article doesnt sound good for this algo. If I have time I will try the TestU01 battery tests and compare it with mersenne.
Thanks for the help.
Alex