It's starting to look like a meme at this point. I don't want to leave one stone un-turned and I'm in the middle of a field of boulders. So let's go.

The PEAC algorithm performs a division, with remainder and dividend, by a power of two, so it's simply a mask&shift operation. So what if the divisor was not a power of two?

It sounds pretty useless at my level because it totally flushes the benefits of having a well rounded number and speed suffers with no practical advantage. However there could be a significant theoretical benefit.

The whole point is that a non-power-of-two modulo will provide much more granularity. The challenge so far is to discover an elusive formula for widths that provide "maximal orbits", but the use of a width artificially limits the data set from which we could deduce anything. The currently know values

2, 3, 4, 10, 16, 26

do not help much... But these are the log₂ of the modulo. So what if we used a proper modulo? The actual list would be

4, 8, 16, 1024, 65536, 67108864

and we haven't even tested a fraction of all the possible values, only those that have a practical application. There is much more to uncover by looking between the sampled values, and such a refined search could considerably increase our understanding of PEAC. At least, by running the scanner on way more moduli (and not widths), we could find hints, or even a formula, or a rule of thumb, or something...

There might not even be a need for super-complex or highly efficiently optimised programs. I can reuse older versions, not even bothering with multi-thread or parallel scanning. Scanning w16 takes a few seconds, and several scans can run in parallel. Scanning all the moduli up to 65535 will take a while though, mostly at the end. How many of them will have maximal orbits?

The inner loop would look like this:

uint64_t orbit(uint32_t modulo) {
  uint64_t len=0;
  uint32_t
    X = 1,
    Y = 0,
    C = 0;

  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)
      return len+1;

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

Of course, the length of the orbit should be (m²+m-2)/2.

______________________________________________________________

Well well well Ladies & Gentlemen...

moduli_01.c is here. I didn't know what to expect but...

It's pretty interesting.

.

Wow.

Not only do we have plenty of orbits with the expected length, but a good portion has double this length! That is: m²+m-2 !

I don't know what to make of it yet. I'll let the computer crunch the numbers for now.