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_{2} 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.*

*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.

## Discussions

## Become a Hackaday.io Member

Create an account to leave a comment. Already have an account? Log In.