Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Is code that requires internet connectivity allowed? (not gonna access any random function online, but maybe ping or the values of an api call) –  elssar Jan 25 '13 at 16:47
    
"This function must not call upon any libraries or other functions that were not also written as part of the program." That includes Internet connectivity functions. Your generation should be purely algorithmic. –  Joe Z. Jan 25 '13 at 17:27
    
The diehard suite expects input files of 10-11 MB. –  primo Jan 25 '13 at 18:44
    
Thanks. I'll change that. –  Joe Z. Jan 25 '13 at 18:47
add comment

4 Answers

up vote 9 down vote accepted

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
share|improve this answer
    
Yeah, I noticed that your algorithm "failed" the bitstream test, but actually had a few values below 0.999999. Still, your tests seem accurate. –  Joe Z. Jan 25 '13 at 22:56
    
There is one problem, though, and that is that numbers from 4294951589 to 4294967295 have no chance of occurring (although I suppose that is part of the reason it failed some of the Diehard tests). –  Joe Z. Jan 25 '13 at 23:20
1  
@JoeZeng yes, that is a problem. It's most evident in Test 5: the first run has 151k missing words, and the rest of them only have 143k missing. One solution would be to choose a modulus slightly larger than 2^32, and allow the values that are too large to wrap around to zero, but I wasn't able to find one that works well. If I do, I'll update the post. –  primo Jan 26 '13 at 7:15
add comment

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.)

share|improve this answer
    
Could you paste a log file? –  primo Jan 28 '13 at 18:42
    
Log here: codepad.org/ZWhoGe0t –  Keith Randall Jan 29 '13 at 18:43
1  
Stupid Windows. It was converting all occurances of \r and \n to \r\n, which obviously skews the results. A fix is to write the file directly using f = open('file.bin', 'wb') and f.write. –  primo Jan 30 '13 at 1:10
    
This new score undercuts the previous score, so is now the accepted answer. –  Joe Z. Feb 1 '13 at 3:24
    
This new score was undercut yet again, so I have changed the accepted answer. –  Joe Z. Feb 9 '13 at 17:01
add comment

Python, 41 / 15 = 2.73333

v=0
def R():global v;v=hash(`v`);return v

Kinda cheating using the built-in hash function, but it is built-in, so no more cheating than using other builtins, like len. On the flip side, it pains me to have to pay for the global v; statement...

Passes all the Diehard tests (I had a problem with test #2, it SEGVs on my OSX machine. For my score, I'm assuming it will pass).

Here's a driver to generate the 16MB file:

import sys
for i in xrange(1<<22):
  r=R()
  sys.stdout.write('%c%c%c%c'%(r&255, r>>8&255, r>>16&255, r>>24&255))
share|improve this answer
    
"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." I'm sorry, but that disqualifies your entry. –  Joe Z. Jan 27 '13 at 0:13
    
To be clear, "len" would also disqualify your entry. –  Joe Z. Jan 27 '13 at 0:15
    
Where do you draw the line? Is + a built-in function, and hence disqualified? –  Keith Randall Jan 27 '13 at 1:35
    
+ is an operator. By functions, I refer to things that, in most languages, would require a name of the function, then brackets to surround the arguments, such as f(x). –  Joe Z. Jan 27 '13 at 2:00
4  
But in lots of languages, operators and functions are identical. See + and __add__ in python, or operator overloading in c++. I know I'm kind of splitting hairs, so consider this example. In python can I create a map like this: {'a':5}? You'll probably say yes, but then consider that under the covers, hash('a') gets called when you do that. –  Keith Randall Jan 27 '13 at 3:57
show 4 more comments

Ruby, 32/15 = 2.1333

This is Keith Randall's solution, implemented in Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.