- #1

- 20

- 0

So instead of representing numbers in a binary way I need to represent them as sums of fibonacci numbers where i-th number indicates whether that fibonacci number is part of the sum.

For example string 101110 represents the number f6+f4+f3+f3+f2 = 14.

What I need to do is come up with an algorithm to increment such fibonacci counter.

I found these solutions on the internet http://lcbb.epfl.ch/algs10/ex2-sol.pdf but I'm not even able to wrap my head around that at the moment.

If I go baby steps and count from 0 upwards

853211 (these are just fib. numbers to help with my short attention span)

0 000000

1 000001

2 000011 - last two flits are 01, we change them to 11

3 000101 - change last two to 01 and report carry 1

4 000111 - last two flits are 01, simply change to 11

5 001001 - last two flits are 11, change to 01, carry 1 to the 3rd position and then one more forward cause the 3rd one is 1

The result is 4 instead of 5 so I messed it up somewhere.