While Fibonacci sequences are very well known, their truncated versions are not characterised so I did a pair of simple test pages using JS :

test_wrap64K.html.txt

test_wrap256.html.txt

Save, rename and run the files, because I got surprising results.

First : the sequence length is exactly 50% longer than the modulo size !

This is great news because I feared the sequence would end up in a tight loop but instead, it means I don't need to add carry propagation to the LSB ! Though it's interesting to see if that would increase the cycle length.

However, 50% cycle extension is little compared to the doubled storage size and squared code space : 768 codes only are used among the 65536 available if 2 bytes are used. Of course, here I test only one init vector, but input data will of course change the "orbits" of the sequences.

What this all means is that a 2-bytes checksum will be OK up to 368 bytes, because if they are all 0s, the result would be indistinguishable. 4 bytes (total) will be OK up to 98304 (×2) bytes to checksum.

I have also looked at the wrapping frequency and distribution : in average, every other operation creates a wrap, so it's balanced. Locally, some patterns could emerge though.

Note:

When initialised with X=1 & Y=0, the first wraparound/saturation occurs after

• 12 cycles for 8-bits
• 24 cycles for 16 bits

we can suspect the wraparound occurs at around 48 cycles for the 32 bits version, which is not far from the previously calculated value of 45.

Another result :

For the 8-bits version, wrapping the carry out to the next carry in has a detrimental effect : the period decreases to 115 cycles. This is in fact awesome news because the algorithm can be kept simple.

However, for the 16-bits version, including the carry system brings the orbit to a length of 2G cycles ! This is almost as good as CRC32 ! See test_wrap64K.carry.html.txt

.

TODO:

• examine the orbits of the cycles
• check with other init vectors if the resulting cycles are shorter or longer.

Stay tuna'ed.