Note: this is a work in progress and some assertions can still be inaccurate, just stay tuned...

.

As I alluded at the end of the log I just realised...the new "formula" makes the algorithm's behaviour very easy, much more convenient to analyse.

The core of the computation (in the simple PRNG configuration) is as follows:

if (X >= modulo)
    X -= modulo-1;
T = X;  // no unrolling here so a temp reg is required
X += Y;
Y = T;

The order of the operations is critical, as it affects the range of the variables.

For example in the above code, X has a range of 0 to (2×modulo)-3 and Y goes from 0 to modulo-1. In this case, the values of X that exceed modulo correspond to the values where C=1 in the binary PEAC algorithm, and this state must be preserved across iterations. This is why the comparison and "incremented modulo" operation occur first, before the accumulation.

Already we can see how the "stuck points" appear.

The null point X=0,Y=0 is obviously going nowhere.

The opposite of the null point X=mod-1,Y=mod-1 will also give X=mod-1,Y=mod-1 because the same value is both added (by Y) and subtracted (by the modulo). This confirms that X should not reach 2×(mod-1) or it would get stuck. (I think there is a discrepancy here)

If we're hashing data (D) then the algorithm is modified a bit:

if (X >= modulo)
    X -= modulo-1;
if (Y >= modulo)
    Y -= modulo-1;
T = X;
X += Y;
Y = T+D;

The first half ensures that X and Y are in the range 0 to modulo-1.

The last two lines ensure that the new data is incorporated in the right order, in parallel, to prevent overflow.

Both halves could be swapped but I doubt this would be perfectly equivalent. Anyway when the mod is a power of two, the behaviour should be identical. It might even run slightly faster on modern OOO CPUs.

(tbc)