I frequently run my genetic programming software with different parameters, seeing what it will find. When asked to find a pseudo-random number generator under some given constraints, it is fairly good at finding a solution. The solution it finds is typically chaotic, though, with an unverifiable period. That’s not very useful practically, as the chaotic nature means that some seeds may have very short times before they start repeating. Take, for example, the generator below, produced by a short simulation:

RMU S2,51,954523823516132654;
XSR S2,13;
XOR OP,S2;

Translated into C# (where there is a class-level “state” variable), this is

public ulong NextRandom()
{
    state = BitOperations.RotateLeft(state, 51);
    state = state * 954523823516132654;
    state = state ^ (state >> 13);
    return state;
}

Recall that ^ is the XOR operator in C#. People keep asking me if that’s a “raise to a power” operator.

This generator passes some randomness tests at a million numbers generated, and can probably be tuned to pass some fairly strong tests if some of the parameters are changed. Unfortunately, it mutates the state in a fairly chaotic way, and I’m unaware of a way to determine what the shortest possible period is. There might be some seed value of state for which it repeats after 16 values, or a billion. Without guarantees about period, it’s impractical to use.

However, recently I ran the genetic simulation with a constraint of not using multiplication, and it found the solution below.

ADD S2,S1;
ROR S2,1;
SUB S1,12076313562642528635;
XOR OP,S2;

Translated into C# (this time with two class-level state variables), this is

public ulong NextRandom()
{
    state2 = state2 + state1;
    state2 = BitOperations.RotateRight(state2, 1);
    state1 = state1 - 12076313562642528635;
    return state2;
}

This generator is interesting because state1 changes from iteration to iteration by subtracting an odd number, and thus state1 will go through every possible ulong before repeating. I have no idea what the actual period of state2, and thus the whole generator is, but it is atleast the period of state1, which is 2^64. This is interesting because it is a rare case where I can prove a lower bound on the period by inspection, and the generator actually passes some decent tests of randomness. The generator is also remarkably simple, using only a single add, subtract, and rotate, so it should be competitive speedwise with some of the existing cutting edge PRNG’s.

I have tested this generator on a given seed to 100 billion numbers, using the GCD test, the gorilla test with word lengths 7 and 17, and the linear serial correllation test, and it passed all of the tests. I think the rotate constant it found was actually 4, not 1. I tested it at 1 in an attempt to see if that weakened it, but it apparently is quite strong at those parameters. I haven’t yet tuned any of the parameters, but it is remarkably simple. State1 is what Marsaglia called a Weyl sequence. Not very random. State2 is an accumulator that gets rotated between accumulations. Apparently that’s a fairly decent way to randomize things.