Build a random number generator that passes the Diehard tests While there are many code golf questions on here involving randomness, I haven't seen one yet that actually asks for building an algorithmic pseudorandom number generator. There's this one that asks you to generate a bit stream, but the randomness tests provided on that one were not very rigorous, and it's not code-golf.

The program you write will have a single callable function that will return a random integer from 0 to 4294967295. This function must not call upon any libraries or other functions that were not also written as part of the program, especially calls to /dev/random or a language's built-in rand() library. More specifically, you are limited to the basic operators of the language you are working in, such as arithmetic, array access, and conditional flow control statements.

The score of your program is calculated as follows:

Score = C / R


Where C is the length of the code in characters, and R is the number of Diehard tests that your generator passes (If your random number generator does not pass at least one Diehard test, its score is infinity and it is disqualified). Your generator passes a Diehard test if the file it generates provides a range of P-values that appear to be distributed uniformly along the interval [0, 1).

To calculate R, use your random number generator with its default seed to generate a 16 MB binary data file. Each call of the function returns four bytes; if your function is too slow to return bytes, this will factor a trade-off into attaining a low score by how difficult it is to test. Then, run it through the Diehard tests and check the P-values provided. (Do not try and implement these yourself; use the ones provided here)

Lowest score wins, of course.
Perl 28 / 13 &approx; 2.15

sub r{$s^=~($s^=$s/7215)&lt;&lt;8}


log file here

Perl 29 / 13 &approx; 2.23

sub r{$s^=~($s^=$s&lt;&lt;8)/60757}


log file here

These are something of a variation on a Xorshift, using floating point division instead of a right shift. They both pass 13 of 15 tests, failing only tests 6 and 7. 

I'm not exactly sure how long the cycle is, but because the following code doesn't terminate in any short period of time, it's likely the full 232:

$start = r();
$i++ while $start != r();
print $i;




Perl 39 / 10 = 3.9

$s=$^T;sub r{~($s=$s*$s%4294969373)||r}


Note: if you're looking for a Blum-Blum-Shub-esque PRNG, Keith Randall's solution is far better than either of these.

As with my original solution below, this is also an implementation of the Blum Blum Shub, with one major difference. I uses a modulus slightly larger than 232 (M = 50971 &bull; 84263), and whenever a value is encountered that it is not a valid 32-bit integer (that is, larger than 232), it returns the next value in the rotation instead. In essense, these values are pruned out, leaving the rest of the rotation undisturbed, resulting in a nearly uniform distribution.

It seems to have helped. In addition to passing the same 9 tests as before, it now also convincingly passes the Minimum Distance test. A sample log file can be found here.



Perl 33 / 9 &approx; 3.67 (Invalid?)

 $s=$^T;sub r{$s=$s*$s%4294951589}


Note: this solution might be considered invalid, as the top-most 0.00037% of the range will never be observed.

A quick and dirty implementation of the Blum Blum Shub. I claim the following results:

 1. passed - Birthday Spacings
 2. FAILED - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks of 6x8 Matrices
 5. FAILED - Monkey Tests on 20-bit Words
 6. FAILED - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. FAILED - Minimum Distance Test
11. passed - Random Spheres Test
12. FAILED - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test


A sample log file can be found here, feel free to dispute any of the results. The file for diehard can be generated in the following manner:

print pack('N', r()) for 1..4194304


and then piping the output into a file. Minimum Distance looks like it might have passed, but if you run it multiple times it's always very close to 1.0, which indicates failure.



Details

In general, the Blum Blum Shub is a terrible PRNG, but it's performance can be improved by choosing a good modulus. The M I've chosen is 7027 &bull; 611207. Both of these prime factors, p and q, have modular residue 3 (mod 4), and gcd(&phi;(p-1), &phi;(q-1)) = 2, which is as low as it can be.

Although these are the only criteria listed on the wiki page, it doesn't seem to be enough. Almost all of the modulo I tried failed every test. But there's a handful that will pass some of the tests, and the one I've chosen seems to be exceptionally good, for whatever reason.

As a final note, Test 5 on its own seems to be a fairly good indicator of how good the PRNG is. If it doesn't almost pass Test 5, it will fail the rest of them spectacularly.



BONUS: Perl 62 / 14 &approx; 4.43

$t=$^T;sub r{$t|=(($s=$s/2|$t%2&lt;&lt;31)^($t/=2))&lt;&lt;31for 1..37;$t}


Just for geekery, this is a 32-bit version of the PRNG used in the original Tetris for NES. Amazingly, it passes 14 of the 15 tests!

 1. passed - Birthday Spacings
 2. passed - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks for 6x8 Matrices
 5. passed - Monkey Tests on 20-bit Words
 6. passed - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. passed - Minimum Distance Test
11. passed - Random Spheres Test
12. passed - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test


Sample log file can before here.

Admittedly, the 1..37 bit isn't an exact transcription. In the orginal version, the entropy routine is updated 60 times per second, and then queried at random intervals, largely dependent on user input. For anyone who cares to disassemble the ROM, the entropy routine begins at 0xAB47.

Python-style pseudo-code:

carry = entropy_1 &amp; 1
entropy_1 &gt;&gt;= 1
entropy_2 = (entropy_2 &gt;&gt; 1) | (carry &lt;&lt; 31)
carry = (entropy_1 &amp; 1) ^ (entropy_2 &amp; 1)
entropy_1 |= carry &lt;&lt; 31