Build a random number generator that passes the Diehard tests
Perl 28 / 13 ≈ 2.15
sub r{$s^=~($s^=$s/7215)<<8}
log file here
Perl 29 / 13 ≈ 2.23
sub r{$s^=~($s^=$s<<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 • 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 ≈ 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 • 611207. Both of these prime factors, p and q, have modular residue 3 (mod 4), and gcd(φ(p-1), φ(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 ≈ 4.43
$t=$^T;sub r{$t|=(($s=$s/2|$t%2<<31)^($t/=2))<<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 & 1
entropy_1 >>= 1
entropy_2 = (entropy_2 >> 1) | (carry << 31)
carry = (entropy_1 & 1) ^ (entropy_2 & 1)
entropy_1 |= carry << 31
Python, 46 / 15 = 3.0666
v=3
def R():global v;v=v**3%(2**32-5);return v
Uses modular exponentiation to generate randomness. 2**32-5 is the largest prime less than 2^32. (Same deal with not being able to run test #2.)
Mathematica, 32 / 15 = 2.133
x=3;Mod[x=Mod[x^2,28!-67],2^32]&
A straightforward implementation of BBS.
Binary file generated with:
f = %; (* assigns anonymous function declared in the previous expression to f *)
Export["random.bin", Array[f, 2^22], "UnsignedInteger32"];
Summary of results:
1. BIRTHDAY SPACINGS TEST .684805
2. OVERLAPPING 5-PERMUTATION TEST .757608/.455899
3. BINARY RANK TEST .369264/.634256
4. BINARY RANK TEST .838396
5. THE BITSTREAM TEST (no summary p-value)
6. OPSO, OQSO and DNA (no summary p-value)
7. COUNT-THE-1's TEST .649382/.831761
8. COUNT-THE-1's TEST (no summary p-value)
9. PARKING LOT TEST .266079
10. MINIMUM DISTANCE TEST .493300
11. 3DSPHERES TEST .492809
12. SQEEZE .701241
13. OVERLAPPING SUMS test .274531
14. RUNS test .074944/.396186/.825835/.742302
15. CRAPS TEST .403090/.403088/.277389
Full random.bin here.
Full log file here.