Going further on the path explained in log 27. What is it ?, I'm exploring the question of addition.

The Pisano-Carry state space has the operation "next" and "previous" state but addition is not natural, or more precisely it does not correspond to something we already know. Getting the "successor" is not strictly equivalent to adding 1, because there is no such "number" in this object: states are coordinates and have 2 elements (and half). We already know addition between integers, between complex numbers, between numbers in a Galois field (such a N^m or polynomials over Z²)... But here it's something different.

Another idea is that if you can compute "next", you can also compute "next next" and so on... This could maybe speed up the search/exploration of orbits but would that be faster than individual steps ? And how would we know that the intermediary steps would (or would not) visit a given state ?

Let's go back to the code's definition of one step:

t = X + Y + C;    Y = X ^ data;
C = t >> 16;      X = t & 0xFFFF;

In a more mundane way, this could be written as:

#define SIZE (1 << WIDTH)
t = X + Y + C;
Y = X;
C = t / SIZE;
X = t mod SIZE;

Computing 2 steps though is not so easy because X and Y are swapped all the time:

#define SIZE (1 << WIDTH)
t  = X + Y + C;
Y1 = X;
C1 = t / SIZE;
X1 = t % SIZE;

u  = X1 + Y1 + C1;
Y2 = X1;
C2 = u / SIZE;
X2 = u % SIZE;

The div/mod operations don't make the sequence easy to simplify but, as in the Adler32 advanced version, there should be a way to perform it at the very end of the sequence only. If this is true, then the general algorithm could be sped up further...

(To be continued...)