Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

You might find this technique interesting.

#! perl -slw use strict; use vars qw[ $X $Y $N $D ]; use GD; $|=1; #use constant { SEED => 0, A => 65537, C => 65539, M => 65536 }; # Rea +lly BAD!! #use constant { SEED => 0, A => 32717, C => 32719, M => 65536 }; # Bad + enough!! my $rnd = SEED; sub badRnd{ $rnd = (A * $rnd + C) % M; $rnd % $_[0] } $X ||= 1024; $Y ||= 1024; $N ||= 100_000_000; $D ||= 10; GD::Image->trueColor( 1 ); my $img = GD::Image->new( $X, $Y ); my $color =0; my $incr = 1; $img->fill( 0, 0, 0xffffff ); for( 0 .. $N ) { # my( $x, $y ) = ( int badRnd( $X ), int badRnd( $Y ) ); # printf "[$x:$y] "; my( $x, $y ) = ( int rand( $X ), int rand( $Y ) ); $img->setPixel( $x, $y, $img->getPixel( $x, $y ) + 1 ); printf "\r$_ " unless $_ % (1000); display() unless $_ % ($X * $Y * $D); } sub display { open IMG, '>plot.png' or die $!; binmode IMG; print IMG $img->png; close IMG; system( 'start /b plot.png' ); }

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:

P:\test>test -X=256 -Y=256 -D=1

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!


In reply to Re: Testing for randomness (spectral testing) by BrowserUk
in thread Testing for randomness by DrHyde

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (5)
    As of 2014-09-22 03:08 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (178 votes), past polls