Overview
The quality of pseudo random number generators varies widely.
Some are barely able to create more than a dozen unique numbers,
while others can go on for ages without falling into repeating patterns.
There are a number of ways to check the quality of random number generators,
the most famous of which are the
Diehard tests.
However, these tests can only look at the output of a generator and guess
if it is random. Because this study uses custom implementations of the
different pseudo random number generators, it's possible for the testing
suite to directly access the internal state of the generator and make
observations that most randomness tests cannot.
To take advantage of this, four tests have been created to gauge the
effectiveness and randomness of any generator being examined.
Seeds
Pseudo random number generators are initialized using a seed value.
To perform this battery of tests, six predetermined seed values are
used for each test.
These values, in order, are as follows:
| SEED | NOTES |
| 1138 | The famous number used as an easter egg by Lucasfilm. |
| 65535 | The largest value that can be stored in an unsigned 16-bit integer. |
| 8675309 | Jenny's phone number, from the song by Tommy Tutone. |
| 16777216 | The number of colors possible using True Color (24-bit) graphics. |
| 123456789 | A nine digit number created by counting from 1 to 9. |
Test 1: Period Length
A random number generator's
period is the number of results that can be
generated before the generator either repeats itself or falls into a loop. Both
conditions restrict how random the generator can be.
This test is performed by initialing the generator with the given seed, then
drawing 80,000 results. After each result, the generator's internal state is checked
and if the current state is a repeat of a previous one, the test ends.
The generator is considered to have passed this test if there was no repeated state
during the 80,000 queries. Note that many generators will be able to pass this test
even if their output is not that random - all that matters is their internal state
is always unique.
Test 2: Dice Rolling
This test attempts to see if the results from the generator are skewed in some way by
using the generator's output to roll virtual dice. In theory, there should be a roughly
equal chance of getting each number on a 6-sided dice. In practice, the output tends to
favor specific outcomes.
This test is performed by initialing the generator with the given seed, then
drawing a result as a floating point number (obtained by dividing the output by
the generator's maximum possible result). This number is then compared to six
ranges (eg, a number between 0.32 and 0.48 is considered to be a 2 ). A counter
keeps track of how many results fall into each range. This is then done 10000 times
for each seed and the results tallied. Finally, a graph of the overall percentages
is rendered.
The generator is considered to have passed this test if there is a roughly even
spread between the ranges (around 16% per outcome; shown as a red line on the chart).
Test 3: Dart Throwing
This is a variation on the classic Parking Lot test. Virtual darts are "thrown"
at a dart board. Each dart is represented by an X,Y coordinate pair, while the
dart board is simply an area of 100x100 possible spaces.
This test is performed by initialing the generator with the given seed. Next,
12,000 darts are thrown at the dartboard. To do this, each dart is created by
generating two random floating point numbers and multiplying them against 100
to get the dart's target coordinates. The distance formula is used to check
if there is already a dart in this approximate location. If so, the throw
"misses" and the new dart is discarded. If not, the throw "lands" and the
new dart is added to the list of darts on the dartboard.
The generator is considered to have passed this test if at least 6,000 darts
managed to hit the dartboard.
Test 4: Crush Test
This test uses the famous zlib library to locate sections of redundant output from
a random number generator. In other words, a file is produced and then "zipped".
Since the compression algorithm uses redundancy and repetition to reduce the
target file's size, this can be used to quickly observe how random the output
of a pseudo random number generator really is.
This test is performed by initialing the generator with the given seed and
writing 10000 results to a file. Since many generators cannot produce a full
64-bit integer as output, only the least significant byte is stored. This
file is then compressed using zlib. The size of the original file is then
compared with the size of the compressed file and expressed as a percentage.
The generator is considered to have passed this test if the compressed file at least
70% as large as the original. Some generators are random enough that the compressed
file is actually
larger than the original, which means there wasn't enough
redundant data for compression to work properly.
Test 5: Plot Test
This test attempts to visualize how random the output of the generator is by
plotting 32768 points in a 256x256 field.
This test is performed by initialing the generator using Jenny's number as the seed,
then creating a 256x256 pixel image filled with white. Using the least significant byte,
32768 X,Y coordinates are generated and mapped to the image. Each time a point is marked,
the color value is decremented by 50. This allows us to clearly see when a point is
repeated multiple times - the darker the pixel, the more times it appeared in the sample.
The generator is considered to have passed this test if the resulting image
resembles static. The generator fails this test if there are repeating patterns,
few unique points, or if the points create a striped image.
Test 6: Example Output
After the other five tests are completed, the generator is reinitialized using
Jenny's number as the seed and 400 results are drawn.
This is not a test per se; its purpose is to allow readers to see a sampling of the generator's possible output.
