Forget  about this log : it has a fatal flaw.

The idea is good but it breaks a range assertion.

____________________

Two recent logs Hashing with npo2 PEAC and wow. explore a generalised, non-power-of-two version of PEAC and the results are quite interesting, to say the least. But it's not done yet.

I made a quick-and-dirty scanner that contains this inner loop:

  do {
    C += X + Y;
    if (C >= modulo) { // This branch is going to totally mess with the branch predictor
      Y = C - modulo;
      C = 1;
    }
    else {
      Y = C;
      C = 0;
    }
    if ((Y == 1) && (X==0))
      return len+1;

    len+=2;

    C += X + Y;
    if (C >= modulo) {
      X = C - modulo;
      C = 1;
    }
    else {
      X = C;
      C = 0;
    }
  } while ((X != 1) || (Y != 0));
  return len;

The if / else part is pretty cumbersome but is a direct application of the original code.

But it is still "not right".

It took me too long to realise my mistake and it can be simplified quite significantly:

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

And that's all !

This is also where things become even more interesting: PEAC does NOT perform a normal modulo. In the original code, it was a normal modulo but setting C to 1 is like decrementing the modulus. The new code integrates this directly in the subtraction and thus drops one temporary value, C, but the algorithm is not strictly equivalent anymore: PEAC has a separate flag and tests should be performed at a different stage, since the +1 is applied at the same time as the modulo operation.

One solution is to consider C merged with X (or Y) between steps of the algorithm. The modulo is then performed before the accumulation.

// odd step
if (X >= modulo)
    X -= modulo-1;
Y += X;
// even step
if (Y >= modulo)
    Y -= modulo-1;
X += Y;

Could it be even simpler? I doubt.

This changes the criterion for the selection of the modulus, since what matters now is not the comparison/trigger, but the subtrahend. This is the value that should be a "dense prime" to promote/maximise mixing between the bits. This totally changes how I view the values that were scanned.

The closest maximal modulus to the ideal 2^(16.5)=92681 is 92688, which is even but the subtrahend is 92687=7×13241=0b10110101000001111 (not bad but could be better).

Below that, the closest even number is 92668, giving the subtrahend 92667=3×17×23×79=0b10110100111111011 which is better but would introduce more bias in the hashed values.

______________________________________________

On top of that, this new, purified version of the algorithm also makes its analysis way easier. The behaviour is much more explicit so hopefully, I'll progress on the theory side, including for the original PEAC... For example it's possible to get a simpler proof of the existence and conditions to reach the sticky states.

Stay tuned...