Close

Some theory

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDESYann Guidon / YGDES 05/02/2021 at 13:540 Comments

This computer is still searching for the loop length for the w26 and w27 configuration but it only goes as far as 7,5% of the expected range in 3 days & half. At 2% per day, we'll still be there in a month and half... Which leaves some time to think about the theory.

First, let's have a look at OEIS and refine the search because we have new data:

While looking at https://oeis.org/search?q=2,3,4,10,16 I can exclude the sequences that contain 17 to 25. One curious find is A293632 :

Least integer k such that k/Fibonacci(n) >= 3/4 : 1, 1, 2, 3, 4, 6, 10, 16, 26, 42, 67, 108, 175

The Fibonacci word is mentioned but I have no idea what this sequence means or if it is actually relevant. However several sequences with the same prefix have the number 26 so I'm hopeful that the current computation will provide a positive result. But it will be too long... Something else must be done while my laptop endlessly churns numbers. So let's go to the basics.

In the log 18. Structure and extrapolations, I mentioned obvious geometric/topologic features. For example in the w4 version :

The upper half is almost identical to the lower half, because they correspond to the result of the same operation. There is a shift because to get to the lower part with C=1, X has an extra +1.

Then we also have this complementarity, with a central symmetry, within one square/half:

(Here I have cropped the top-most line to make it more obvious and get an odd number of lines)

So in the best/desired case, once get have one coordinate for one orbit, we also have the corresponding point for the other orbit at the opposite from the centre.

The above picture is taken from the upper square, where we see that the upper-right triangle contains the diagonal, which explains why we find another power of two in the length of the orbits.

                        orbit
Width     states       length    ratio(%)    decomposition
2             32            9     28.125     2^3 +  2^1 -1
3            128           35     27.34      2^5 +  2^2 -1
4            512          135     26.36      2^7 +  2^3 -1
10       2097152       524799     25.02     2^19 +  2^9 -1
16    8589934592   2147516415     25.0003   2^31 + 2^15 -1

For a width w, the orbits has 2^(2w-1) + 2^(w-1) -1 states, the middle term is the diagonal line and the -1 is the stuck point.

When it is multiplied  by two, to account for the two complementary orbits, the formula is 2^(2w) + 2^w -2 and this is coherent with the diagram where the diagonal (with only trajectories that lead to the orbits) is removed:

And we find another central symmetry, coming from the already existing symmetry within a square and the copy/shift of the lower triangle.

This duality (in the "ideal case") works because the 2^w range behaves like a "ring" where 0 is equivalent to 2^w -1. How/why, I don't know, and I have no idea why the carry makes the orbits fill the space, and only for specific values of w, while this does not happen in the classic Pisano periods (where the main orbit fills only 3w/2 states).

 
-o-O-0-O-o-
 

There is another crucial question : does every point have an antecedent/predecessor ? If there is a definitive positive answer, then all versions must have orbits. This is also very important because the answer will also tell if the function has funnels, per Bob Jenkins' definition (go read his article if you don't know it already !).

We already know that each point has only one successor, given by the very definition of the sequence:

X' = X + Y (mod 2^w)
Y' = X

So, given X' and Y', we can deduce the antecedent:

X = Y'
Y = X' - Y' (mod 2^w)

In the example below, we see a geometric construction that finds the antecedent of (20,6) through some projections:

Because X goes into Y in the following iteration, there is not much choice in the antecedent. This is a very precious because from there, we can deduce a few useful things !

 
-o-O-0-O-o-
 

For example, let's look at the a point on the diagonal line, with coordinates (n,n).

We can easily compute the coordinates of the next points on the orbit:

(n,n) => (2n,n) => (3n,2n)=> (5n,3n)=> (8n,5n)=> (13n,8n)...

OK you have seen that this is a scaled Fibonacci sequence, with a factor of n. So we can conclude that any point on the diagonal will generate its own scaled sequence until it hits the X limit.

But there is better yet ! What if we apply the formula in reverse to see what happens before the point lands on the diagonal line ?

 (n,n) <= (n,0) <= (0,-n) <= (-n, n) <= (n, -2n) <= (-2n,3n) <= (3n,-5n) <= ...

Look ! We have the Fibonacci in reverse ! And with alternating signs. But I'm sure it's already been studied somewhere.

And it's not as simple because in the current situation, not only are operations performed module 2^w, but also any carry/overflow will increment the sum.
So now we must get the real formula that includes the carry...

 
-o-O-0-O-o-
 

.
.

Discussions