Random Number Generation

NOTE: This post is not being done written... I would like to include some images and have better explanations of what I actually did.

Random number generation is an interesting problem, because computers are fundementally not good at it. They are good at producing things that are the same every time, they are good at producing things that sould have consistent values. They are not good at producing things that are fundementally as inconsitent as possible.

This makes it an interesting problem to solve. On the first hand there can be random number generation that is beleiveable for a human. And then there is random number generation that is closer to truly random.

Measuring Randomness

Now of couse there are so many other things that a random number generator should have, and evaluating randomness is extremely hard. If you're looking to get nerdsniped I can highly recommend this Wikipedia article on randomness detection. It is short and provides many rabbit holes.

Before we can improve, we need to measure. What I though would be easy to implement and moderatly effective was:

1. Uniform distribution: each number appears roughly equally
2. Uniform deltas: the difference between consecutive numbers should also be uniform
3. No patterns: even the delta between every other number should be uniform

def evaluate(self, start, end, trials):
    occurances = [0 for i in range(start, end + 1)]
    delta = [0 for i in range(start, end + 1)]
    # ... count occurrences and deltas over many trials
    return occurances, delta, delta2

Attempt 1: Just Add One

The simplest possible "generator":

class RandomPlus1(Random):
    def gen_rand(self, x):
        return x + 1

This is deterministic and cycles through values. Terrible randomness, but predictable.

Attempt 2: Trig Functions

Sine introduces non-linearity:

class RandomSinShift(Random):
    def gen_rand(self, x):
        y = math.sin(to_int(b[2:]))
        z = (to_int(b[0:2]) << 4) + 1
        return to_int(to_bytes(z + z * y, 4))

Better, but still has patterns.

Attempt 3: XOR Bit Mixing

XOR operations shuffle bits around:

if (y ^ x > i ^ y):
    n[i] = n[i] ^ y
n[i] = 7 + n[i] ^ x

Chaotic, but hard to tune.

Attempt 4: Optimizing Generator Parameters

Instead of guessing constants, use optimization. RandomAddXor has two parameters: an addend and an XOR mask.

class RandomAddXor(Random):
    def gen_rand(self, x):
        b = int(x) & 0xFFFFFFFF
        b += self.a
        b = (b & 0xFFFFFFFF) ^ self.b
        return b

We use differential evolution to find a and b that minimize deviation from uniform distribution:

def objective_function(x):
    random = RandomAddXor(x[0], x[1])
    o, d, d2 = random.evaluate(start, end, trials)
    ro = sum([abs((1/len(o)) - x) for x in o])
    rd = sum([abs((1/len(d)) - x) for x in d])
    rd2 = sum([abs((1/len(d2)) - x) for x in d2])
    return float(ro + rd + rd2)

The optimizer searches for magic numbers that produce the flattest distributions within some given range. This was really where I started to have fun and see some interesting results.

The Baseline

For comparison, Python's built-in generator:

class RandomGiven(Random):
    def gen_rand(self, x):
        return int(RD.getrandbits(32))

This uses the Mersenne Twister, a well-studied algorithm with a period of 2^19937-1.

Conclusion

Simple operations like add and XOR can produce surprisingly decent pseudo-randomness when parameters are tuned. But for anything serious, use a proven algorithm.

You can find my code here.