RNG Testing

[Abel]

Those interested in random number testing may find the following informative.

http://csrc.nist.gov/rng/rng2.html
"December 9, 2004: A new version of the Statistical Test Suite (Version 1.7) has
been released. This version is intended for use on PC based platforms and, due
to the apparent interest level, will become the default (and only supported
platform) for future releases."

On any scale of user friendliness, StsGui.exe is not.  You'll need a screen resolution better than 800x600 to start off.  Should you hit a "ret_val is <6>" barrier, try one bit stream of 1,000,000 bits.  When the tests finish, results are spread over a slew of files in the experiments folder.  To find out what they mean, consult SP800-22b.pdf.  Quantitatively, most boil down to P's and Q's (P+Q=1).  Probabilities are usually related to a theoretical bell-shaped curve dependent on sample size, modulus, etc.  Each test yields a number lying somewhere along the x-axis and P is conventionally the fraction of the area under the curve to the left of this point (and Q to the right).  Walker's ENT program labels a RNG suspect when a result falls in the bottom or top decile - that's going to happen 20% of the time with a perfectly good RNG.  STS adopts a 1% cutoff.

STS requires bit streams of 0's and 1's as input and can read them from either an ASCII file with '0' and '1' characters or a binary file.  At a minimum, this restricts one to using numbers generated with a base that's a power of two.  A base of 3, for example would generate packed 2-bit sequences 00, 01, 10, with equal probability and the fact that there are twice as many 0's as 1's is grounds for immediate rejection.  While STS is state-of-the-art, it's scarcely compatible with the level of instant gratification this PC user expects.

On the home front, I've been trying an alternative approach for a basic chi-square RNG test of the distribution of values in an integer array.  Typical screen output:

Code Select Expand


RandMW               Array     Delta
Probability (Q) =  0.269519  0.347000
Probability (Q) =  0.451860  0.978125
Probability (Q) =  0.957924  0.488127
Probability (Q) =  0.649694  0.626607
Probability (Q) =  0.377276  0.134692
Probability (Q) =  0.993757  0.522341
Probability (Q) =  0.793849  0.803142
Probability (Q) =  0.771217  0.149080
Probability (Q) =  0.302457  0.378456
Probability (Q) =  0.866893  0.117077
Probability (Q) =  0.631799  0.205647
Probability (Q) =  0.180079  0.656550
Probability (Q) =  0.138409  0.769996
Probability (Q) =  0.921084  0.937276
Probability (Q) =  0.212303  0.440617
Probability (Q) =  0.012543  0.224712
Probability (Q) =  0.208118  0.172013
Probability (Q) =  0.629240  0.919936
Probability (Q) =  0.689821  0.068737
Probability (Q) =  0.165569  0.605325
-------------------------------------
Mean (x2)       =  1.022341  0.954545
Variance (x12)  =  1.126725  1.028489
Initial Seed = 7E347832
Size and Base: 500000 , 1000

Press SpaceBar to repeat or any other key to quit.

RandMW is Michael's proposed RNG and these are results for arrays of 500,000 integers modulus 1000 (0-999).  The first column of numbers shows chi-square probabilities for 20 separate runs.  If the distribution is random, their mean should be 1/2 and their variance 1/12.  The deviations found are within the 25% or so expected for 20 numbers.

The second column used the array obtained from the circular differences of the first-column array's elements.  The first column is invariant to any ordering in array elements and reveals nothing about serial correlations.  By replacing x(i) with x(i+1)-x(i), we can detect these correlations.  In one test, using the same seed to recreate identical arrays, sorting 500 elements within a 100K array reduced the second column to 0.000000's while leaving the first unscathed.

It might be noted that it took only a second to generate, test, and display results for the 10 million numbers involved - and, should anything look suspicious, one may continue on to the next 20 tests, etc., etc., etc.  No physical files are involved - arrays are created in RAM and tested in situ.

For the record, I haven't found any statistical difference in using Michael's or my own formulation of the Park-Miller algorithm.  This is important as Michael's uses the most significant bits of the seed, whereas mine uses the least significant bits.  As fmul soundly beats fdiv in clock cycles, advantage MW.

All software, source and executable, zipped below.  The EXE was written in IBasic, the DLLs in Masm32.  To expedite testing alternative RNGs, a plugin DLL methodology is used, template included.  Included are plugins for Michael's code, the original Masm32 library code, msvcrt code, and RANDU (IBM).  For the last, use odd moduli only (see the asm); for the Masm32 function a seed of 0x48d931d8 gets you quickly into the oops regime.  Even dubious RNGs return statistically useful results if not pushed too far.  The 15-bit msvcrt function works quite well unless you use a modulus >1000 or chance to flip a coin a million times.  By playing with size and modulus, one can see in the stats the gradual deterioration of RNG performance.

Abel


[attachment deleted by admin]

[Abel]

I've wrapped the above RNG test program in a Basic GUI.  Unzip all to any
directory and execute to play with the included LCG generators.  The notes
may guide you to regimes of underwhelming performance.  If you want to roll
your own, add your algorithm to the template, assemble as another DLL and
add it to the pack (Rand*.dll).

If anyone has working code to change the text color for individual Listview
subitems, I'd be obliged.  It appears to be a real hassle using the info MS
makes public.

Abel


[attachment deleted by admin]