Inspired by Random with your hands tied:
The goal of this challenge is to write a program that generates a pseudorandom bit stream, which is a string of 1s and 0s that appears to be purely random, but is actually generated in a deterministic way. Your program should output a string of 1 and 0s (with optional whitespace) and should pass the following requirements:
- Given unlimited time and memory, your program must continue to output a string of 1s and 0s forever
- Your program must output more than 1000 random bits in about one minute, on a reasonable machine. If this requirement is impossible, then I will lessen it.
- The string of bits can repeat, but the length of the repeating section must be more than 1000 bits.
- The string of bits must pass as many of the randomness tests (described below) as possible.
- The program must not take any input from any external sources or use any built-in rand()-like function.
- Because of the above requirement, the program must output the same exact string of bits each time that it is run.
Randomness Test #1
The string of pseudorandom bits must not include any obvious pattern upon visual inspection.
Randomness Test #2 (subject to change based on comments)
The string of bits must contain an equal distribution of 1s and 0s. To test this (and other things too), the stream of bits is broken into segments that are 3 bits long, such as
Out of all of these segments, 1/8 of them should have three 1s and no 0s, 3/8 of them should have two 1s and one 0, 3/8 of them should have one 1 and two 0s, and 1/8 of them should have no 1s and three 0s.
Randomness Test #3
A "run" is defined as a consecutive series of bits that all have the same value. The string
1001001110 has three runs of size 1 (
1..1.....0), two runs of size 2 (
.00.00....) and one run of size 3 (
......111.). Notice that runs do not overlap.
Out of a string of 1000 random bits, there should be about 250 runs of size 1, 125 runs of size 2, 62 runs of size 3, etc. In general, for run size R, there should be about
1000/(2**(R+1)) runs of that size.
Randomness Test #4
The first 840 bits are split into two halves of 420 bits each. Each bit on the first half is compared to the corresponding bit on the second half. The two bits should match about fifty percent of the time.
Here is the source code of a Perl program that performs tests 2 through 4. As of now, it requires that the string of bits not contain any whitespace.
Objective Winning Criterion Time!
The winner is the program that passes all of the 6 requirements and all of the randomness tests to the degree that it is indistinguishable from randomness. If multiple programs accomplish this, then the one that takes the longest amount of time to repeat will win. If multiple programs accomplish this, then I might have to find more randomness tests to act as tie-breakers.