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

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.

## Discussions

## Become a Hackaday.io Member

Create an account to leave a comment. Already have an account? Log In.