Close
0%
0%

Pisano-carry Checksum algorithm

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

Similar projects worth following
Another purely additive, non-cryptographic, fast and minimalistic checksum.

Aimed at being a 32-bit checksum for very low resources,
- very small, using only XOR and ADD,
- without the flaws of Adler32 and Fletcher, yet the same size and complexity,
- almost as good as CRC32, which it may replace when the memory footprint is critical,
- very easy to implement in digital circuits or microcontrollers with 16-bit accumulators,
- suitable for the detection of trivial corruption in network packets or files.

Disclaimer: This is a linear, reversible checksum so it's not appropriate for cryptography or hash tables. This is not even the fastest checksum ever.
But it's still quite good.

The most common application uses 2×16 bits. The 2×8 bits version doesn't work, and 2×32 bits seems untestable for now.

If you wonder why, just click and read the log.

The original algo/project name was "Fibonacci checksum" but it later appeared that it was not the most accurate choice because Pisano (the real name of Fibonacci) is the name associated to the perodicity of the sequence under modulo.

 
-o-O-0-O-o-
 

In 2012, Piano Magic released their album "Life Has Not Finished with Me Yet". One song contains a weird repeating pattern...

Glen Johnson's lyrics are often cryptic and more evocative than objective, but any geek's mind would cling on this mantra at the end:

Add X to Y and Y to X

This is really weird but... Why ? What's the point in this obscure "song" with no precise theme or clear subject ? And what does it do ? This last question is the most easily answered : just follow the damned algorithm.

C'est parti...

X=1, Y=0
Y+=X => 0+1=1
X+=Y => 1+1=2
Y+=X => 1+2=3
X+=Y => 2+3=5
Y+=X => 3+5=8
X+=Y => 5+8=13
X+=Y => 8+13=21
Y+=X => 13+21=34
X+=Y => 21+34=55
...

No need to go further, most of you should have recognised http://oeis.org/A000045, the famous Fibonacci sequence.

This gave me a compelling idea to modify the old Fletcher & Adler algorithms, keeping their very low footprint and minimalistic computational complexity. Both of these well known algos use a pair of values and have a similar structure. The trick is that rearranging the data dependency graph provides the equivalent of a minimalistic polynomial checksum, because the result is fed back on itself, in a more robust way than Fletcher's algo.

At first glance, this new checksum loop's body becomes something like :

Y += ( X ^ datum[i  ] );
X += ( Y ^ datum[i+1] );
i+=2;

This loop body is totally trivial to unroll. As trivial is the design of the corresponding digital circuit. This early version seemed to contain the whole checksum entropy in the last computed value but now X and Y are part of the signature. And the really important enhancement is the use of the carry!

For superscalar 32 bits CPUs, the following code seems to work well though the missing carry hardware (and/or lack of language support) requires more instructions to emulate:

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

In this worst case, without support of a carry flag, that's 5 basic operations (not counting memory loads) that fit in 4 registers and 3 cycles, to process 2 bytes. Not too bad. I'll let you deal with alignment. But is it really safe or safer ?

The following logs will show how the idea evolves and the performance increases, through discussions about carry wrap-around, register widths, scheduling, avalanche, parallelism, orbits, structure, black holes...

 
-o-O-0-O-o-
 

Logs:
1. The variable
2. Datapath
3. Adler32 weakness
4. Easy circuit
5. Periodicity
6. A promising 32-bit checksum
7. Progress
8. Why
9. Orbital mechanics
10. Orbits, trajectories and that damned carry bit
11. Two hairy orbits
12. How to deal with black holes
13. Anteriority
14. Moonlighting as a PRNG
15. A new name
16. More orbits !
17. First image
18. Structure and extrapolations
19. Even more orbits !
20. Start and stop
21. Some theory
22. Some more theory
23. Even more theory.
24. A little enhancement
.

 
-o-O-0-O-o-
 

Ironically, this structure reminds me a LOT of a 2-tap LFSR. So a more "powerful" version would use a Mersenne LFSR-inspired structure, with additional registers : Z, W, V... In several 2005 articles, I have explored "Mersenne Twisters" with 3 and 4 taps but even that would be overkill for such a basic application where throughput is the only point. The only effect would be to delay the feedback and reduce the growth factor from φ=1.6something down to maybe 1.3. The most important point is that ALL input bits must have an effect that lasts until the end of the checksum loop, or else errors can easily creep in (and this is where Adler is better than Fletcher).

 
-o-O-0-O-o-
 

NoFix:

  • Endian (who uses Big Endian anyway today ?)
  • Alignment (align...
Read more »

orbit_resume.c

same as orbit_count.c but with command line options to resume the search at a given point.

x-csrc - 1.99 kB - 05/07/2021 at 06:03

Download

Pisano16x2.c

A simple function that computes the checksum of a buffer.

x-csrc - 815.00 bytes - 04/29/2021 at 01:21

Download

test_Pisano16x2.c

a dumb main() to verify that Pisano16x2.c works.

x-csrc - 469.00 bytes - 04/29/2021 at 01:21

Download

orbit_count.c

Measures the first orbit of the Pisano-Carry state space (the long way)

x-csrc - 1.28 kB - 04/27/2021 at 05:08

Download

orbits_anim.c

Generates one image for each step of computation. (updated version)

text/x-csrc - 4.92 kB - 04/26/2021 at 12:33

Download

View all 16 files

  • A little enhancement

    Yann Guidon / YGDES2 days ago 0 comments

    As we have already explored, a system with width=w will have

    • w bits for X
    • w bits for Y
    • 1 bit for C

    The whole state space is also divided into two groups :

    1. the orbits (2 ideally, of equal length)
    2. the trajectories, which lead to one orbit at the next step.

    The 1-step trajectories might irk some purists because they would be seen as a "funnel".

    In a way this is true because this makes the system non-reversible, as half of the alterations (from the user datastream) will make the state fall in the "diagonal" band of states that leads to the funnel. Switching orbit is not an issue since it is reversible.

    There is one solution though : we have already seen that the orbits always fall in a "triangle", where C=0 when X>Y and C=1 when X<Y. So the trick would be to adjust/correct C after Y is altered, so the state remains in either of the orbits. But where would this correction fall in this code ?

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

    In the cases I see, this will simply override, or overwrite, C. At first glance it seems to throw one bit of entropy away but if we consider the condition of C, it is not really lost since it depends on X and Y so if Y changes, C should too. So we could write

    C = sign(X-Y)

    But not anywhere, because 2 parallel operations are taking place simultaneously. However C is updated on the 2nd line and since it will be overwritten, that statement can be replaced and re-organised:

    t = X + Y + C;    Y = X ^ data; // ^ or +, as you like
    X = t & 0xFFFF;
    C = (((X-Y) >> 16) & 1

    I'm not sure yet if/how I can run the masking of X simultaneously with the comparison. x86 has comparison instructions that would greatly simplify the last line, which might be obscure to the compilers. Let's also try with:

    t = X + Y + C;    Y = X ^ data;
    X = t & 0xFFFF;
    C = (X<Y)?1:0

    That last line should be translated in two x86 opcodes. If carries are used in asm, just move things around:

    C = sign(X-Y);   // just a CMP
    t = X + Y + C;   // ADDC
    Y = X ^ data;    // XOR
    X = t & 0xFFFF;  // might be avoided in 16-bits mode
    

    This is obviously slower than the classic version, with 3 cycles, and must be verified as equivalent with the original code.

     
    -o-O-0-O-o-
     

    What are the costs and benefits ?

    • The immediate cost is the added subtraction that compares X and Y, slowing the computation down in the critical datapath.
    • Another cost is the loss of one diagonal line, since C is now explicitly computed but with a partial formula
    • The benefit is having a truly reversible computation and a potentially more solid error detection but this assertion must be tested and verified.

    In practice, the balance must be carefully chosen. So far, before this alternate version is thoroughly tested and compared, it seems that the original, simple version, is still the most attractive, at least for short or medium data streams. The "enhanced version" without the funnels must show a significantly increased robustness to justify the added speed cost.

    .

  • Even more theory.

    Yann Guidon / YGDES2 days ago 0 comments

    The last log 22. Some more theory examined the orbits of the systems with w=0, w=1 and w=2. Let's look at the orbits of w=3 now:

    This system has 2 orbits with 35 steps each and shows more complexity than the previous ones. The ranges are [0..7] now:

    Orbit 1
    Starting at 1,0,0
      1 - 1,1,0
      2 - 2,1,0
      3 - 3,2,0
      4 - 5,3,0
      5 - 0,5,1
      6 - 6,0,0
      7 - 6,6,0
      8 - 4,6,1
      9 - 3,4,1
     10 - 0,3,1
     11 - 4,0,0
     12 - 4,4,0
     13 - 0,4,1
     14 - 5,0,0
     15 - 5,5,0
     16 - 2,5,1
     17 - 0,2,1
     18 - 3,0,0
     19 - 3,3,0
     20 - 6,3,0
     21 - 1,6,1
     22 - 0,1,1
     23 - 2,0,0
     24 - 2,2,0
     25 - 4,2,0
     26 - 6,4,0
     27 - 2,6,1
     28 - 1,2,1
     29 - 4,1,0
     30 - 5,4,0
     31 - 1,5,1
     32 - 7,1,0
     33 - 0,7,1
     34 - 0,0,1
     35 - 1,0,0
    Orbit 2
    Starting from 7,0,0
      1 - 7,7,0
      2 - 6,7,1
      3 - 6,6,1
      4 - 5,6,1
      5 - 4,5,1
      6 - 2,4,1
      7 - 7,2,0
      8 - 1,7,1
      9 - 1,1,1
     10 - 3,1,0
     11 - 4,3,0
     12 - 7,4,0
     13 - 3,7,1
     14 - 3,3,1
     15 - 7,3,0
     16 - 2,7,1
     17 - 2,2,1
     18 - 5,2,0
     19 - 7,5,0
     20 - 4,7,1
     21 - 4,4,1
     22 - 1,4,1
     23 - 6,1,0
     24 - 7,6,0
     25 - 5,7,1
     26 - 5,5,1
     27 - 3,5,1
     28 - 1,3,1
     29 - 5,1,0
     30 - 6,5,0
     31 - 3,6,1
     32 - 2,3,1
     33 - 6,2,0
     34 - 0,6,1
     35 - 7,0,0

    This time, most of the points on the lower diagonal (n,n,0) are belong to orbit 1 and the others to orbit 2, but this feature is rather unique to this configuration.

    Furthermore I don't see a clear pattern to identify the middle of the orbit. With an odd number of steps, 35/2=17.5 falls between (0,2,1) and (3,0,0), which looks a lot like 2^(w-1)-1 but this looks like a fluke so far.

    .

  • Some more theory

    Yann Guidon / YGDES4 days ago 0 comments

    The last log is only scratching the surface and the redaction was interrupted so I resume here.

    Let's start with some more OEIS :

    • A216783: Number of maximal triangle-free graphs with n vertices.
      1, 2, 3, 4, 6, 10, 16, 31, 61, 147,...

    • A329695: Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HU and DH.
      1, 2, 2, 3, 4, 6, 10, 16, 28, 48, 85, 152,...

    I don't know if they are really related but somewhere, something should match and these are some of the least implausible. I have not found a matching underlying theory yet so I'm fishing for whatever can be found. The results of the next brute-force searches will tell us more and refine the fishing expedition.

    So a lot of responsibility remains on the shoulders of the brute-force search. And the "theory" could help reduce the strain. For example, the "backwards equation" can double the speed of the the exhaustive search for orbits !

    Consider this: if the orbit has a forward and a backwards direction, then both ways can be explored simultaneously and meet at the middle. This is not really a win when taken from the perspective of the total amount of computations. However the steps can be run in parallel !

    The computation is still very serial in nature (particularly because each step of both computations must be compared) but that's where Out Of Order Execution shines, because it can run several instructions in parallel and reorganise the execution flow at will. Indeed the pipeline will be better used than in the purely serial code that is currently running on my old dual-core i7. So I should focus on the backwards equation. The diagram below shows the principle, where both paths are one half shorter:

    But then, one more idea comes: What if we could determine the coordinate of the middle of the orbit in advance ? From there, it would be easier to only compute one half and meet at the quarter of the orbit, which would further half the computation effort.

    Then, from there, what keeps me from going further and bissecting the orbit further and further and... After all the orbit length is close to a power of two so it would be a good match. But this would work only if an ideal orbit exist, so what makes these orbits ideal in the first place ?

    There is another way to see it, not with the "top-down" approach but "bottom-up". Let's start with the simplest, smallest system and see how it evolves.

     
    -o-O-0-O-o-
     

    The case with width=0 only contains 2 stuck states so there is nothing much to learn there.

     
    -o-O-0-O-o-
     

    With width=1, we have 8 states with X and Y oscillating between 0 and 1.

    (1,0,0)=>(1,1,0)=>(0,1,1)=>(0,0,1)=>(1,0,0)

    Wait, what ? We have a 4-long orbit ? Anyway the binary sequence looks legit. If we exclude (0,0,0) and (1,1,1) the other orbit should be 2-long, right ?

    (1,0,1)=>(0,1,1)=>(0,0,1)=>(1,0,0)
    (0,1,0)=>(1,0,0)=>(1,1,0)=>(0,1,1)=>(0,0,1)=>(1,0,0)

    No, it falls on the "diagonal" and there is only one orbit, and the two trajectories enter the loop at a different place.

     
    -o-O-0-O-o-
     

    For width=2, there are 32 states, 2 orbits and X is modulo 4 (spans 0..3), 2 symmetrical orbits of length=9 and 2×6 trajectories.

    Let's look at both orbits in parallel:

    (1,0,0)=>(1,1,0)=>(2,1,0)=>(3,2,0)=>(1,3,1)=>(1,1,1)=>(3,1,0)=>(0,3,1)=>(0,0,1)=>(1,0,0)
    (2,0,0)=>(2,2,0)=>(0,2,1)=>(3,0,0)=>(3,3,0)=>(2,3,1)=>(2,2,1)=>(1,2,1)=>(0,1,1)=>(2,0,0)

    Neat ! Now let's rotate the 2nd orbit a little to start with (2,3,1):

    (2,3,1)=>(2,2,1)=>(1,2,1)=>(0,1,1)=>(2,0,0)=>(2,2,0)=>(0,2,1)=>(3,0,0)=>(3,3,0)=>(2,3,1)

    If you invert the carry ( 0<=>1 ) and the X and Y ( 0<=>3, 1<=>2 ) you find the same sequence as the first orbit ! This was not possible or true with width=1. QED.

     
    -o-O-0-O-o-
     

    What else can we learn from this ? Another noticeable feature is that going backwards in the orbit is possible, despite the carry. The last log 21. Some theory has deduced the antecedent from...

    Read more »

  • Some theory

    Yann Guidon / YGDES05/02/2021 at 13:54 0 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:

    • 2 is actually valid (I didn't bother checking before), I'll have to check with 1
    • All widths from 17 to 25 have been invalidated.

    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...

    Read more »

  • Start and stop

    Yann Guidon / YGDES04/28/2021 at 20:13 0 comments

    I have already explored all the "low hanging fruits" I have found but I'll need more time to come up with a proper perspective and theory. However, practical implementations have some coding constraints that I will address in this log.

    Let's have a look at this revised dependency graph, which I revised to consider the aspects covered here:

    I tried to minimise the total number of operations. This would probably be adapted for a hardware implementation, of course, but let's first design a first working software version.

    The first thing to consider is the last one, usually called the "Finish" step, where the final result is handled. Already, X, Y and C contain the whole state for the system but

    1. C is usually discarded, so should be better combined with the remaining bits
    2. X could be OK by itself but adding it to Y should increase the Hamming distance in the case of an alteration that hits the last word and/or the checksum.

    So the Finish contains a simple addition with carry in, and no carry out.

    • If you only require 16 bits of signature, this sum is all you need.
    • However if you desire 32 bits, you can concatenate X and Y.

    Going up from there, we have the loop body. The X-Y swap has been moved up but this doesn't change much here.

    Then we have the Start step where the variables are initialised. As we have learned, the carry must be set to a value that is coherent with Y, in order to prevent a "stuck state". So in fact, any value is OK except  { Y=FFFF, C=1} and { Y=0, C=0}. I have used 0x1234 to prove my point but you may choose another non-forbidden value.

    One input value is pre-loaded into X and the pointer can be pre-incremented in the loop to save one instruction and prevent an off-by-one access (and/or TLB lookup for a block that will not be used).

    From there, writing the code is quiet like a walk in the woods...

    #include <stdint.h>
    #include <inttypes.h>
    
    #define PISANO_WIDTH (16)
    #define SIZE  (1<<PISANO_WIDTH)
    #define MASK  (SIZE-1)
    
    uint32_t Pisano_Checksum(
      uint16_t *buffer,  // points to the data to scan
      int size           // number of 16-bit WORDS to scan
    ) {
      uint32_t
      // Start
        X = *buffer,
        Y = 0x1234, // anything except 0 or FFFF
        C = 1,
        t;
    
      // Loop
      while (size) {
        size--;
        buffer++;
    
        t = X + Y + C;   X = Y ^ *buffer;
        C = t >> PISANO_WIDTH;  Y = t & MASK;
      }
      // Finish
      return C+Y+(X << PISANO_WIDTH);
    }
    

    Aaaand that's it.

    I provided a tiny main() to verify the basics.

    gcc -Wall test_Pisano16x2.c -o test_pisano && ./test_pisano 
    Checksum: 8573B7DA

    What remains now to be done ?

  • Even more orbits !

    Yann Guidon / YGDES04/27/2021 at 05:11 0 comments

    With a new smaller program orbit_count.c, I try to check the length of the first orbit for widths larger than 16.

    Remember what we have found previously : for the configuration to be "good", the first orbit must have at least 2^(width*2 -1) different states, or > 25% of all possible states.

    The first 4 are disappointing:

    • 17 : 52.942.979 (0.6% of the 8.589.934.592 taht would be required to pass the test)
    • 18 : 172.662.654  (instead of 34.359.738.368 to pass, or 0.5%)
    • 19 : 171.681.219 (0.12%, much less than 137.438.953.472)
    • 20 : 317.330.936 (0.06%, barely a blip compared to 549.755.813.888)
    • 21 gets longer (4%) but is still far from 2199.023.255.552 :
      1m53s for 87.960.719.859 iterations

    22 and 23 might be interesting... I have no idea how long they'll run but it's good to have 4 cores on the laptop, so I can run 2 heavy tasks while writing this comfortably. However I can only run about 30G iterations per core per minute and w22 might run about 8800G (4h and half) and w23 about 35000G iterations (17h)...

     
    -o-O-0-O-o-
     

    Later :

    • 22 is approx. one half of the expected length (48.27% of 8.796.093.022.208):
      Orbit length: 4.246.390.747.269
      8353.49user 1.13system 2:19:54elapsed 99%CPU 
    • 23 failed half-way (almost precisely 50%) from 35.184.372.088.832
      Orbit length: 17.592.032.552.735
      30717.44user 4.18system 8:33:59elapsed 99%CPU
    • 24 didn't last long : 0,95% of 140.737.488.355.328
      Orbit length: 1.340.357.111.846
      4427.70user 0.05system 1:14:00elapsed 99%CPU
    • 25 disappointed too: 0.0015% !
      WIDTH = 25 bits, or about 562.949.953.421.312 iterations.
      Orbit length: 8.882.847.330.803
      17867.77user 3.16system 5:52:36elapsed 84%CPU
    • 26 is running, but I have no idea how much time it will take to try 2.251.799.813.685.248 iterations.
      6191m55s, Step 202.653.736.894.464 : X=60945700, Y=54013062, C=0 (9%)
      8224m44s, Step 270.686.018.863.104 : X=30001905, Y=43460744, C=1
      9578m24s, Step 316.109.592.985.600 : X=24653047, Y=21525614, C=0  (14%)
      10089m46s, Step 332121231065088 : X=39691475, Y=26670666, C=0
      ... 605320.20user 67.81system 230:16:09elapsed 73%CPU
      1226m08s Step 374.383.709.257.728 : X=56485448, Y=64077162, C=1  (16.6%)
      3416m13s  Step 447501232504832 : X=7984208, Y=8052197, C=1
    • 27 is running too, maybe it will stop before 9.007.199.254.740.992... That's 9 million billions.
      5948m55s, Step 195.094.594.453.504 : X=13025821, Y=12504916, C=0 (2,1%)
      7981m58s, Step 263.126.876.422.144 : X=85800334, Y=53796446, C=0
      9335m43s, Step 308.550.450.544.640 : X=132594465, Y=19377793, C=0 (3,4%)
      9847m10s, Step 324.493.369.147.392 : X=109974339, Y=52277567, C=0
       ... 590770.05user 61.77system 226:12:32elapsed 72%CPU
      1029m41s, Step 354.661.219.434.496 : X=70991304, Y=49909254, C=0  (3.9%)
      3115m51s  Step 414447164194816 : X=18026315, Y=45706791, C=1

     .

    Stay tuned. But so far I have not found another "good configuration". I'd love if Width=32 was good but for now there is no reasonable way to prove this except with the brute-force approach.

    20210507 : computations started on 20210427 and now I must reboot my computer. Fortunately I have saved here some checkpoint values but I have no program that accepts them. Sigh.

    ....

    OK it was  pretty straight-forward! I made orbit_resume.c  so I could resume the computations. Log on !

  • Structure and extrapolations

    Yann Guidon / YGDES04/27/2021 at 02:45 0 comments

    The last log 17. First image is a huge step forward because the 2D visualisation is not just cool-looking but also very information-rich. I will try to organise this new knowledge here, compare with what I knew or guesstimated before, and see where I can go from there.

    We have seen that depending on the width parameter, different behaviours appear and not all are desirable. I'll only focus on the "interesting" ones, with widths= 3, 4, 10, 16... And from the little I have seen, I'll consider that their respective structures are identical, or at least obey to the same heuristics.

    I expected something along the diagonal. There had to be something there to explain why the orbits had a 2^n + 2^m states, where m seemed related to n for various bit widths. Moreover, the very definition of the Fibonacci sequence says that Y gets the value of X after one step so X > Y, creating a sort of diagonal (with a slope of φ ?) ... But then, you have the wrap-around and carry, and when you keep swapping X and Y, you're simply oscillating around the diagonal line so some sort of symmetric structure had to happen.

    Now, let's look at one small scale "model" of the kind of version that interests us, here with WIDTH=4 hence a size of 16. The coordinates are a bit unusual but you'll get used to it, and it's more a practical choice than guided by a theoretical constraint.

    So you have a "raster scan" type of coordinates, with 2^WIDTH points horizontally, and 2^(WIDTH+1) vertically because the case of CARRY=1 must also be shown. The new 0 just appears in the middle of the rectangle, made of two squares...

    The colour red shows the states belonging to the first orbit (going through 1,0,0) and the colour green show the second orbit. The darker colours correspond to the real orbits, while the brighter ones in the middle are the beginning of trajectories that directly lead to the corresponding orbit.

    There are so many things to notice in this picture !

    • Let's start with the obvious: the upper square is almost identical to the top square, just invert the bright/dark. The only differences I notice are at the borders. Well, this had to be expected because the addition works the same for every number, but the carry will shift the result to the right by one position.
    • When "freewheeling", the orbits occupy the "dark corners" only. The upper-right one corresponds to X>=Y  (as happens during the first iterations of the Fibonacci sequence), while the lower-left one has X<=Y.
    • The diagonal states belong to the orbits, which explains why the orbit lengths contain an additional 2^X term. The -1 corresponds to the "stuck state" which, as we have already proved (and has been computed), can't be reached without a big nudge.
    • There is this striking central symmetry: For every state (X,Y+C*16), the state at (15-X, 31-(Y+C*16)) has the opposite colour ! Combined with the almost-identical translational copy of the squares, this is impressive and can help reduce storage space if more state mapping is required.
    • So the red and green states have the same structure, the same "cardinality" (size), being perfect opposite, but we must also mention that they are not "clumped" together, they mesh nicely and evenly. This is just crazy, how/why can this be so ideal ?

    From there, we can expect these heuristics to work for different widths, as observed in smaller versions, if we are looking for an "ideal" configuration:

    • The orbit going through 1,0,0 MUST contain more than 1/4th of the states of the space.
    • Similarly, you must be able to ride the complementary orbit with coordinates so that
      X1 + X2 = 15, Y1 + Y2 = 15, C1 + C2 =1
      So it's a complete parity rule: change one and you must change all the others (including colour).
      This second orbit inherits the properties of the first one, including its length.

    Given that the complementarity is expected in the ideal case, the first rule is enough to verify that one configuration is ideal. So there is no "mapping" to do,...

    Read more »

  • First image

    Yann Guidon / YGDES04/26/2021 at 01:05 4 comments

    I battled with the BMP header, alignment and other stupid things to finally get THIS :

    This is the map for the width of 10 bits, or 2Mi points. X axis is horizontal from left to right and Y axis from 0-top to max-bottom, with the carry=1 states on the lower half. Zoom and enjoy!

    I'll upload the code ASAP but I have yet to solve a few bugs. For example only the orbits seem visible and I don't see the trajectories, which amount to approx. 1/2 of the points.

    Meanwhile, this is a "clue" that the structure is "visually random", or at least nicely spread, and another encouragement to further the study.

    You can also observe the nice symmetry with the WIDTH=3 and WIDTH=4 maps, zoomed here for your convenience :

    I knew that there would be a sort of diagonal symmetry, among others, but you have to see it!

    .........................................................

    Update : solved the palette bug and now I get these pictures, for widths 3, 4, 6 and 10 :

    The diagonal bands are now apparent. I have chosen width=6 for the counter example, but the other widths show that all the shaded points in the corners will lead to the brighter colour in the diagonal band. There is also a very obvious central symmetry, which was to be expected from the additive nature of the algorithm. This could help half the memory requirements...

    The source code is there : orbits_bmp.c however there is still a bug where I can't see the "sticky states" that should appear in a different colour.

    And here as a bonus, the animated version ! Which destroys some of the assertions I have written above.

    Width=4

    Width=5:

    For larger ones, I am limited by the size allowed by the website... But you can make your own with the source code !

    .....

    Update:

    I solved that stuuuupid BMP bug ! So now the palette is "right" !

    Width=2

    Width=3

    Width=4

    Other sizes don't fit in this page, but you can create your own with this command line:

    gcc -g -Wall orbits_anim.c -O2 -DWIDTH=3 -o orbits_anim
    convert -scale 128x256 -delay 30 -loop 0 img03_00* anim03_256.gif

    That's it. I have updated the source code in the download section:
    orbits_anim.c

    Things should behave much better now !

  • More orbits !

    Yann Guidon / YGDES04/25/2021 at 03:07 3 comments

    It seems that the Pisano-Carry configuration needs more theoretical analysis and exploration. In fact, it needs a whole theory, because I can't find any. So I'm starting to map all the state spaces for register widths <= 16. I might find something interesting to help explore further...

    First, let's see the size of the primary orbits.

    Width     states       length    ratio(%)
    3            128           35     27.34
    4            512          135     26.36
    5           2048           84      0.41
    6           8192          693      8.45
    7          32768         1170      3.57
    8         131072          115      0.08
    9         524288         2600      0.49
    10       2097152       524799     25.02
    11       8388608      1046076     12.47
    12      33554432      2062103      6.14
    13     134217728       413028      0.3
    14     536870912     66448450     12.37
    15    2147483648       204484      0.001
    16    8589934592   2147516415     25.0003

    So it seems that the width of 16 bits is a magical value, a very very lucky one !

    Another good candidate would be the width 10, with one orbit that is 2¹⁹+2⁹-1.

    Less interesting candidates are 11 and 14.

    The rest looks not promising at all.

    It seems that the secondary orbits don't all start at the same index so let's further explore with orbits.c...

    Width     states   orbit lengths  orbits joins  2nd index
    3            128           2x 35     2     2x28      7,0,0
    4            512          2x 135     2    2x120      3,0,0
    5           2048         4,42,84    16
    6           8192          6x 693     6   673,670
    7          32768      10 to 1170    26
    8         131072             115  too many
    9         524288    130,200,2600   114
    10       2097152          524799     2   2x523776    3,0,0
    11       8388608  197 to 1046076     8
    12      33554432   29 to 2062103    14
    13     134217728  206514, 413028  too many
    14     536870912  50 to 66448450     8
    15    2147483648          204484   too many
    16    8589934592      2147516415     2               3,0,0

    So all the sizes do not behave like the others... Width 8 looks like a lost cause. 3, 4 and 10 look like scale models of the 16 version.

    Note : for ALL the cases so far, points outside of the existing orbits lead to another orbit, there is no "trajectory" longer than 1 step.

  • A new name

    Yann Guidon / YGDES04/24/2021 at 04:54 0 comments

    I have changed the name of the project and algorithm because it was potentially misleading or confusing. I first chose it based on the understanding and ideas at the time but they have radically evolved (which is the purpose of these logs, right ?)

    As noted before, the "Fibonacci checksum" systems I have found online simply calculate the Fibonacci sequence and obey to the Pisano period related to the word size. It "works" but is not very efficient because the whole state space is not reached. When I added the carry, it changed the whole thing and the algorithm goes from "passable" to "good".

    It makes sense that I renamed the algorithm so it is relevant, descriptive and unique.

View all 24 project logs

Enjoy this project?

Share

Discussions

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates