Unsigned 8-Bit XOR-Shift Pseudo-Random Number Generator Algorithm Test.
   by William Donnelly

Visual pattern comparison tests of several PRNG's.

Additional information, description, and explanation below-bottom.

This page was coded for Firefox 3.x+, but should work on any modern browser.

Also see 8bitPRNGtest.html for algorithm analysis tests.

Note: Please use this link when referring to this site:
    http://www.donnelly-house.net/programming/cdp1802/8bitPRNGcolor.html

Choosing 65,536 random numbers and visually displaying them graphically takes time, so please be patient. JavaScript is fast, but a lot is being done behind the scenes.

More information, description and explanation about what is going on here.

This page is one of two that is attempting to verify that a conversion of the 32-Bit XOR-Shift PRNG to 8-Bit, using JavaScript, is a valid conversion, and will work as a PRNG for the CDP1802 microprocessor, and other 8-bit computers, as well.

Read below to find out more detailed information, but the final conclusion is that this PRNG should be viable and usable for most situations, but especially games and other programs like that. Note that this routine is not "cryptographically secure", which should be evident.

These tests are simple compared to the DieHard, DieHarder, and other more complex and thorough tests that are normally performed to insure that a pseudo-random number generator algorithm is as random as possible, and does not have any weaknesses, or to what level and degree those exist.

Along with the associated page, 8bitPRNGtest.html, this page displays the 65,536 chosen random numbers using several display options, which will show patterns. We are using the human eye and mind to detect these patterns, because it is pretty good at doing that. It will easily pick up on obvious patterns, but not "super-complex" patterns, so it isn't "perfect", but it will do a decent job for the most part.

As can be seen in the available options above, it looks like the 8-bit conversion does at least a decent job of choosing fairly random numbers. The (non-) patterns look similar to the JavaScript patterns -- i.e., "random". ("snow", "noise", no obvious patterns) The other PRNG examples show obvious patterns, which means that they are very weak PRNG's. (and probably should not be used)

An additional test is performed to see if the random number sequence repeats within the 65,536 values. All (almost all?) pseudo-random number generators repeat after some cycle (periodicity), ideally after a very large number of iterations. The test here checks to see if the first 16 random numbers chosen repeat, which is probably a good enough test for our purposes. (and it's not a perfect test in the sense that it only checks for 16 values, which could possibly not be a long enough sequence to test for, and therefore might generate a "false positive")

A more vigorous (real) test was added called the Frequency (Monobit) Test. The new algorithm passes this test similarly to the JavaScript random() function, which additionally suggests that the Unsigned 8-Bit XOR-Shift PRNG Algorithm is most-probably a valid and usable PRNG. For additional information, see the NIST Special Publication 800-22 Revision 1a document, "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications", Section 2.1 from the Computer Security Division, Computer Security Resource Center website. Most of the tests described in that document are fairly difficult to implement, so only Monobit was chosen.

A (separate) periodicity test suggests (barring error, etc.) that the Unsigned 8-Bit XOR-Shift PRNG Algorithm repeats on (or approximately, or after?) 1,032,056,991 iterations. (over 1 billion, a little over 41 million less than 2^30) If this is true, then this is additional proof that the algorithm is valid (-ish) and pretty good. (probably) The only question at this point is how to properly seed the PRNG. (so the same sequence of random numbers is not produced every time (from initial use))

The RANDU PRNG is a somewhat famous, and infamous, PRNG. I encourage you to follow the link(s) and read about it. Because it was "converted" to 8-bit here, I think it becomes particularly weak.

The Mult13P1 algorithm (and most or all of those like it) is a fairly weak PRNG, and should generally be avoided. They are simple algorithms that are (relatively) easy to implement, but do not work well. See the other page for more information about it.

For 'fun', a PRNG algorithm was created by the author using the first 10,000 digits of the Pi constant. (Pi10K) It was thought that this might be a good algorithm, since the digits of Pi are either completely random, or seem to be. (are they?) The implementation of the algorithm may be, or is, poor. (apparently -- or there are other "issues") You can see that the patterns returned look "dark", which suggests that there is something wrong. The reported Monobit number is 0, which suggests something is VERY wrong. If you look at an analysis report like was done for the other algorithm, 8bitPRNGtestPI.html, you can see why there are severe issues. This is a VERY weak and poor PRNG.

 
# END #

E-mail the author / creator / programmer: Contact William Donnelly