# Orbits, trajectories and that damned carry bit

A project log for Pisano-carry Checksum algorithm

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

The last log Orbital mechanics tried to map the structure of the orbits and found very interesting data, but the mapping program was obviously missing important clues. So far I have uncovered two orbits and a long trajectory leading to the first largest orbit but the carry information was missed and this could change the understanding of the orbital structure. But it is so far very promising, even more than I thought when starting this project.

I am preparing an exhaustive map of the state space but before that, I try to solve small issues with the more reduced version where only orbits that cross X=1 are considered. One critical omission was the value of C because this increases the collision rate and might destroy the available orbital structure.

...

Indeed, the new program gives a very different picture now !

```Starting with X=1 & Y=0 & C=0..........
Orbit #1 closed after 2147516415 iterations at X=1 & Y=0 & C=0 with 32812 intersections

New Sequence starting at X=1, Y=0, C=1
Trajectory #2 joins orbit #1 after 90583 iterations at X=1 & Y=51330 & C=1 with 1 intersections

New Sequence starting at X=1, Y=1, C=1..........
Orbit #3 closed after 2147516415 iterations at X=1 & Y=1 & C=1 with 32725 intersections

New Sequence starting at X=1, Y=2, C=0
Trajectory #4 joins orbit #3 after 32288 iterations at X=1 & Y=26112 & C=1 with 1 intersections

New Sequence starting at X=1, Y=3, C=0
Trajectory #5 joins orbit #3 after 21312 iterations at X=1 & Y=36202 & C=1 with 1 intersections

New Sequence starting at X=1, Y=4, C=0
Trajectory #6 joins orbit #3 after 86477 iterations at X=1 & Y=30443 & C=1 with 1 intersections

New Sequence starting at X=1, Y=5, C=0
Trajectory #7 joins orbit #3 after 53541 iterations at X=1 & Y=4110 & C=1 with 1 intersections

New Sequence starting at X=1, Y=6, C=0
Trajectory #8 joins orbit #3 after 36980 iterations at X=1 & Y=56761 & C=1 with 1 intersections

New Sequence starting at X=1, Y=7, C=0
Trajectory #9 joins orbit #3 after 32806 iterations at X=1 & Y=29148 & C=1 with 1 intersections

New Sequence starting at X=1, Y=8, C=0
Trajectory #10 joins orbit #1 after 29669 iterations at X=1 & Y=31687 & C=1 with 1 intersections

New Sequence starting at X=1, Y=9, C=0
Trajectory #11 joins orbit #1 after 139150 iterations at X=1 & Y=5486 & C=1 with 1 intersections

...

New Sequence starting at X=1, Y=5618, C=0
Trajectory #5620 joins orbit #1 after 84903 iterations at X=1 & Y=31107 & C=1 with 1 intersections

...
```

I had to stop after 6K trajectories were found (the display method is particularly inappropriate with so many lines) but we can already see this:

There are 2 huge distinct orbits (each 2.1G states but different number of intersections with X=1) and many trajectories that lead to either of them (it seems random but you never know at this point) and the carry really matters ! (should it be discarded in the signature ?)

I'll need to map the WHOLE state space because the above program certainly re-calculates many partial trajectories. However the demonstration of the existence of 2 huge orbits reinforces my confidence in the integrity of this checksum!

____________________________________________

I'm now using plain C to map the whole thing. I have chosen to use one byte per state because I don't know how many orbits there are but I already know the two main ones, which I tested on my i7 laptop. I was expecting the random pattern to really thrash the cache and TLB, and I was not disappointed : a simple linear write access of 8GB takes 0.42s but randomly accessing 4.2G bytes takes 6K times longer !

```[FiboSum]\$ gcc -g -Wall orbits_fs16c2.c -O2 -o orbits && /usr/bin/time ./orbits
found orbit 1 at 1,0,0 after 2147516415d iterations
found orbit 2 at 1,1,1 after 2147516415d iterations

The end.
256.56user 2.33system 4:20.48elapsed 99%CPU (0avgtext+0avgdata 8389960maxresident)k
0inputs+0outputs (0major+2097213minor)pagefaults 0swaps
```

So it took 4:20 min to confirm the size and behaviour of the two main orbits.

I'd like to try to make it faster with the use of HugeTLB but this seems to be... a big hassle under plain Linux. And with 4MB L3 cache, it's a lost battle anyway before it started. Memory accesses should be paralleled, to exploit DRAM access capabilities... but that would save what, one minute, for several hours of code ?

## Discussions 