In the question of assessing the pseudorandom quality of a Marsaglia multiply-with-carry oscillator with 2N bits of state, of the sort underlying LMDx after LMD1 [EDIT: As in, (2^(N-1))<=A<(2^N)], it occurred to me that pictures might be of some use.
To do this, I took various A values that are possible with N=9. (By "possible", I mean that the period (P=(A*(2^(N-1))-1)) is a Sophie Germain prime.) Then I created a map of the entire cycle space. It's pretty clear that only 4 cycles exist in such an oscillator:
1. 0 maps to itself.
2. ((A-1)*2^N)+((2^N)-1) maps to itself. This is a "nuisance cycle" because it's easily overlooked and threatens to shut down the oscillator if chosen as a seed.
3a. One of the big cycles has period P.
3b. There are some integers greater than or equal to (A*(2^N)) which eventually find their way onto cycle 3a, but never return to 3b due to limits on the maximum possible output value within 3a.
4a. The other big cycle has period P as well.
4b. Analagous to cycle 3b, there are points which degenerate into to cycle 4a as well.
The number of integers in 3b and 4b is empirically similar, but not equal. I can't explain the difference.
You can see all this in the images below, which have A values of 495, 465, 459, 402, 390, 369, 297, and 270, respectively. There is a bright area, which contains 3a and 4a, and a dark area, which contains 3b and 4b. The upper left and lower right corners of the bright area are white pixels indicating cycles 1 and 2. The rest is red and blue, for cycles 3 and 4.
These images show clearly why these oscillators suffer from bias in the high bit: once you jump from the dark to the bright region, you can't return. One way to deal with that is to engineer A so that the dark area has negligible size.
And I don't know about you, but I'm seeing squarish cells and somewhat nonrandom lower frequency oscillations in the images. Still, it looks very solid for such a simple function. (They are losslessly encoded 512x512 GIF images, so there are no JPEG artifacts here. Right-click and "open in new window" if your browser is scaling them in some annoying way, which mine appears to be doing.)
No comments:
Post a Comment