Close

Orbital mechanics

A project log for Pisano-carry Checksum algorithm

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

Yann Guidon / YGDESYann Guidon / YGDES 04/17/2021 at 15:510 Comments

The Fibonacci sequence is very well known for centuries.

It properties under modulo are less studied (well, huh, I retract that, thank you Wikipedia). With circular carry even less...

I haven't looked at the literature yet and it's about time I do ! But you know the saying: if you don't know, just invent... So this log will try to take a look at the available facts that I gleaned from my latest explorations with FiboSum16x2.html.txt (you know the song: "download it, rename it, open it and wait a bit")

But first, a definition :

Orbit

This is the set of values taken by the generator during its cyclic sequence. Because it is cyclic, it can be defined by any of its values, though preferably the lowest ones. Successive values may be non consecutive. Without the carry, this is also called the "Pisano period".

If it is open ended, it's a trajectory. I also like to use "arc" but it's too late now and I'll try to keep a coherent vocabulary.

And I must say that at first, the generator has seriously puzzled me : The orbit going through X=1,Y=0 has a period of 2³¹+2¹⁵-1. OK so that would mean we would have :

But the orbit 40,11 has the same size as the main orbit ! The pigeonhole principle says "NO" !

And today, I realised that my model was incomplete : the whole state contains the carry as well so the full state space has 2³³ bits ! And the state space needs 3 values X,Y,C.

The question now is to map the whole state space, all 8 billion states. How many orbits are there ? Are there dead ends to lead to 0,0,0 ? Are there trajectories that lead to an orbit ?

If it was a 2²⁰ state space, it would be easy to just calculate it and store it, even visualise it, but 2³³ is on the practical limit. One bit per used state requires 1GB and doing anything more will push a 32-bits system to the wall. Fortunately, I have a 64-bits system with 16GB and we can also use some of the mathematical properties of the Fibonacci modulo generator to infer some points and reduce the search space.

The critical property here is the reversibility: it means that for any "state" X,Y,C, we can find a precise precursor (when given enough information) or a set of possible precursors (given incomplete information).

Oh and Wikipedia tells us:

Thus the study of Pisano periods may be reduced to that
of Pisano periods of prime powers q = p^k, for k ≥ 1. 

and

With the exception of π(2) = 3, the Pisano period π(n) is always even.

Even better,

This 3n/2 period is coherent with my measurements and this explains my results with test_wrap256.html.txt and test_wrap64K.html.txt.

Note however that I also count the number of times when the value "wraps around" and this is very close to the period divided by 2.

Each time the value wraps around, the sequence is also incremented by one (in the carry version), which "bumps up" the orbit to a new shifted sequence. But when the previous value is also taken into account, the carry version becomes like a 2-states system (and the carry adds another bit of entropy).

Now I have to code a tool to map these orbits.

...

So I made Orbits_FS16x2.html.txt which helps me find if 2 states belong to the same orbit and I get weird results. If we fix X=1 and C=0, I get no intersection for several values of Y, hence many orbits. So now I must develop a better and more automated orbit seeker. The numbers don't seem to add up correctly. Should I count C in the orbit ? (Considering that it is usually not used in the final signature, I'd say no but this would crop the whole mental picture)

...

So I made a new JS program which gave this result :

Starting with X=1 & Y=0 & C=0..........
Orbit #1 closed after 2147516415 iterations with 32812 intersections
New orbit starting at X=1, Y=2....
Orbit #2 closed after 809682798 iterations with 12336 intersections
New orbit starting at X=1, Y=3......
Orbit #3 closed after 1254653434 iterations with 19067 intersections
New orbit starting at X=1, Y=17
Orbit #4 closed after 43341641 iterations with 714 intersections
New orbit starting at X=1, Y=22
Orbit #5 closed after 12802266 iterations with 195 intersections
New orbit starting at X=1, Y=73
Orbit #6 closed after 23574436 iterations with 360 intersections
New orbit starting at X=1, Y=430
Orbit #7 closed after 647180 iterations with 12 intersections
New orbit starting at X=1, Y=781
Orbit #8 closed after 2711837 iterations with 36 intersections
New orbit starting at X=1, Y=8927
Orbit #9 closed after 68885 iterations with 3 intersections
New orbit starting at X=1, Y=36202
Orbit #10 closed after 12626 iterations with 1 intersections

Total: 4295011518 states scanned and 10 orbits found

Note : the total orbit lengths add up to more than 2^32, because the carry adds one more state bit. The excess is 44222, which is not a power of 2, so I suspect that more orbits lurk, which don't cross the X=1 line. I don't even test the C=0 condition so more orbits may exist and have been missed.

For a checksum, it is not a real flaw if the period is not maximal. The shortest orbit has a length of 12626, which is not too bad, barely 1/8 the length of the version without carry and one chance in 340K to fall into this. Other potentially lurking orbits require more tests to be uncovered but that requires at least 1GB RAM.

The sorted orbit lengths:

2147516415 = 10000000 00000000 01111111 11111111 = 2^32 + 2^15 - 1
1254653434 = 01001010 11001000 01111101 11111010
 809682798 = 00110000 01000010 11000111 01101110 
  43341641 = 00000010 10010101 01010111 01001001 
  23574436 = 00000001 01100111 10110111 10100100 
  12802266 = 00000000 11000011 01011000 11011010 
   2711837 = 00000000 00101001 01100001 00011101
    647180 = 00000000 00001001 11100000 00001100
     68885 = 00000000 00000001 00001101 00010101
     12626 = 00000000 00000000 00110001 01010010

The first pattern looks "binary" but the next ones much less. Maybe I should look up Google... aaaannnd nothing.

This does not look as robust as a properly implemented CRC32 but it's still much better than Adler32.

Furthermore, an advantage over CRC32 is that the added carry state ensures that when the sum loops back to 0, the carry will never let the state degenerate down to 0, because the next sum MUST be at least 1, even if Y=0xFFFF. Once again, the carry saves the day!

...

Update:

I might have mistaken orbits for trajectories... I must update the program.

...

Update :

A little change of the code can now discern between orbits and trajectories. The result is amazing :

Starting with X=1 & Y=0 & C=0..........
Orbit #1 closed after 2147516415 iterations with 32812 intersections
New orbit starting at X=1, Y=2....
Orbit #2 closed after 809682798 iterations with 12336 intersections
New orbit starting at X=1, Y=3......
Trajectory #3 joins orbit #1 after 1254653434 iterations with 19067 intersections
New orbit starting at X=1, Y=17
Trajectory #4 joins orbit #3 after 43341641 iterations with 714 intersections
New orbit starting at X=1, Y=22
Trajectory #5 joins orbit #4 after 12802266 iterations with 195 intersections
New orbit starting at X=1, Y=73
Trajectory #6 joins orbit #5 after 23574436 iterations with 360 intersections
New orbit starting at X=1, Y=430
Trajectory #7 joins orbit #6 after 647180 iterations with 12 intersections
New orbit starting at X=1, Y=781
Trajectory #8 joins orbit #7 after 2711837 iterations with 36 intersections
New orbit starting at X=1, Y=8927
Trajectory #9 joins orbit #8 after 68885 iterations with 3 intersections
New orbit starting at X=1, Y=36202
Trajectory #10 joins orbit #9 after 12626 iterations with 1 intersections 

This means that what I thought were independent orbits are in fact trajectories and all of them (so far) end up in the main, largest orbit !

There is a long chain of trajectories going to others, and the last one (Trajectory #9) goes through 1337812305 states before entering the main orbit. So a "safe" init value would be X=1, Y=36202. But what about C ? I can't say yet because the C parameter is not taken into account and I suspect it hides more structure.

Suite au prochain log.

Discussions