Very soon after the first runs of the program that scans non-power-of-two (np2) PEAC spaces, a few things have become obvious and challenge my established understanding of the ... thing.

The source code at moduli_02.c scans from 65500 to 65700:

* 65528  2146992155  0
* 65536  2147516415  0    <= known result
* 65549  2148368474  0
* 65559  2149024019  0
* 65568  2149614095  0
* 65570  4299490468  -2149745234
* 65576  2150138675  0
* 65579  2150335409  0
* 65594  4302638428  -2151319214
* 65604  2151975209  0
* 65610  4304737708  -2152368854
* 65620  2153025009  0
* 65624  2153287499  0
* 65638  4308412680  -2154206340
* 65658  4311038620  -2155519310
* 65663  2155847615  0
* 65664  2155913279  0
* 65674  4313139948  -2156569974
* 65685  2157292454  0
* 65686  4314716280  -2157358140
* 65694  4315767328  -2157883664
 21 found

Do you know what that means ?

You can scramble or checksum 16-bit data with 32-bit registers with modulo=65570 and get a worst case period of double of 2147516415.

A rapid look at the logs show some non-random behaviour with the last digits:

• None of the maximal orbits come from moduli with 2 or 7 as the last digit. Why. Why...
• The moduli that give half-maximal orbits end with digits 0, 1, 3, 5, 6 and 9. The corresponding orbits have a length ending with the digits 0, 4, 5 and 9.
• The moduli that give perfect orbits end with digits 0, 4, 6 and 8. The corresponding orbits have a length ending with the digits 0 or 8.

Weird.

...

Seriously it feels like I opened a whole barrel of worms by scraping the bottom of a can of worms.

____________________________________________________________________________

From there it is possible to build an almost direct successor of Fletcher32 and Adler32, by using the prime factor 65579, which has a pair of orbits of length 2150335409. There are a few other nice moduli but 65579 is the first prime after 65536, which is nice.

Unfortunately there is no modulus that is both prime and perfect, because (as seen above) the perfect moduli end with digits 0, 4, 6 or 8, which are even and thus can't be prime.

Since 65579 is larger than 65536, it doesn't have some of the problems of Adler32 which uses 65521 (the largest prime less than 2^16). IMHO, it is better to have a half-perfect orbit and a prime number, than a non-prime with a longer orbit, because primes mix better.

This algorithm is pretty alluring and a very interesting alternative to the power-of-two PEAC, but the performance is lower in several aspects.

Furthermore there is another catch: how would you deal with a signature that is "a bit larger" than a power of two ? Add another bit and get almost 1/2 of the coding space unused ? Truncate and introduce a nasty bias ?

One application though would be with hash tables since we have so many possible moduli...

____________________________________________________________________________

Now, wait a minute !!!

Remember the w26 fiasco ? The computation that would not stop ?

Maybe, possibly, this would be because the real orbit was a perfect one ?

2^26=67108864 so it could make a perfect orbit though I don't see how my "smart" algorithm would catch that... How can I distinguish between a perfect and a maximal (half-perfect) orbit ?

Let's compare with other verified po2s:

2^2 = 4  => 9  

2^3 = 8  => 35   

2^4 = 16  => 135   

2^10 = 1024  =>  524799  

2^16 = 65536   => 2147516415 

These values seem to break the general trend noticed before, because the moduli end in 4, 6 or 8 but do not create a perfect orbit.