|Perl: the Markov chain saw|
Re: Testing for randomness (spectral testing)by BrowserUk (Pope)
|on Oct 24, 2003 at 07:09 UTC||Need Help??|
You might find this technique interesting.
What this does is plots pairs of random numbers on an X-Y grid and increments the color value at the pixel plotted. If the PRNG is a good one, the color will tend to increase linearly and evenly over time. However, if the generator is a bad one, then the colour will tend to clump and string. With really bad generators (as with the two Linear congruential generators commented out in the code), the clumping will slowly form a lattice work where the sequence starts to repeat.
This implementation is fairly crude, but does demonstrate the technique quite vividly. The nice thing is that you can test for the interaction between the natural periodicity of the generator, and the reduction in periodicity that occurs when the sequence is used modulo some number as with typical usage.
Running this against perl rand function, at least the one that comes with AS 802, for 100 million iterations modulo 1000, and it shows it to be a pretty good generator with a very low level of clumping.
I originally saw this method (spectral testing) performed on a very powerful 3d workstation, with a dynamically adjustable alpha setting that allowed you to 'see through' the cube of plotted data and see how the latticing appears throughout in regular striations.
I wish I could have posted a couple of comparative outputs here, but you can get a feel for how the technique works from the graphics on this page. The output from the program above looks remarkable similar to the diagrams about halfway down that page.
The display() sub above is coded to automatically display the .png produced every so often, (controlled by the -D=N), under Win32 assuming that you have a picture viewer associated with the .png extension.
Update: For some instant gratification, try running the program with the settings:
Examine what is said, not who speaks."Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail