Amortized analysis of base Fibonacci counter

Question

We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good potential function.

Suppose instead of powers of two, we represent integers as the sum of Fibonacci numbers. In other words, instead of an array of bits, we keep an array of fits, where the $i$th least significant fit indicates whether the sum includes the $i$th Fibonacci number $F_i$. For example, the fitstring 101110 represents the number F6 + F4 + F3 + F2 = 8 + 3 + 2 + 1 = 14.

a. Describe an algorithm for an increment operation.

b. Show that a sequence of $n$ operations is amortized $O(n)$ using the potential method.

c. Do the same thing above, but now add a decrement operation.

---

This is what I started out with:

The general rule is to never let two consecutive Fibonacci numbers exist in the counter at the same time. In other words, no two 1's can occur consecutively. This is because of the definition of Fibonnaci numbers, i.e. a number such as 011 can be replaced by 100.

In general, when incrementing, change the least significant bit that's a 0 to 1 (this is one of the two "1" representations that are the first two bits in the counter). Starting from the most significant bit, if some positions $i$ and $i-1$ have 1's, then change them to 0's and change position $i+1$ to a 1. Keep recursing until there are no more consecutive 1's.

Now we will use the potential method to show that the amortized cost of $n$ consecutive increment operations is $O(n)$.

We will define our potential method as follow: (this is one part I'm having trouble with)

I then made the following observation: Suppose the $i-th$ operation makes $x_i$ Fibonnaci conversions (changing consecutive 1's to 0's and changing the next significant bit to a 1). Then the actual cost is $1 + 3x_i$.

Any help is appreciated! Thanks!

Answer 1

As far as I know, there's no general method for designing a potential function, which makes sense when you consider that they can be used for different purposes. I've been trying on and off for 20 years, and to this day, I have no idea how Sleator and Tarjan came up with the function they used to prove the optimality (with respect to an arbitrary PDF) of splay trees.

Having said that, it often helps to work backwards. I'm going to show you what I mean for the algorithm for incrementing binary numbers. This should give you some ideas about how to proceed.

Let's start by simply checking the number of bit-flips required to increment numbers, starting with zero:

+--------------+---------+
| Bit sequence | # flips |
+--------------+---------+
|            1 |       1 |
|           10 |       2 |
|           11 |       1 |
|          100 |       3 |
|          101 |       1 |
|          110 |       2 |
|          111 |       1 |
|         1000 |       4 |
|         1001 |       1 |
|         1010 |       2 |
+--------------+---------+

So that's the ruler function, which you may recognise as being the solution to the Tower of Hanoi problem. It satisfies the recurrence:

$$a(2n) = 1$$ $$a(2n+1) = 1 + a(n)$$

But that's neither here nor there. What's interesting is that as you go on, the average number of flips per increment seems to trend towards 2; you can write a little program yourself to verify this, or you can note that half the increments flip one bit, a quarter flip two bits, and in general $\frac{1}{2^i}$ of them flip $i$ bits for $i>0$. Do the sum yourself.

So we need to design a potential function so that each increment "costs" two flips. If the increment only flips one bit, we want to put another flip in the bank, as it were, so we can withdraw it later. If the increment flips two bits, we want the potential function to be the same, and so on.

Recall that for an operation which transform the state $S_b$ into the state $S_e$:

$$T_{\hbox{amortised}}(S_b \rightarrow S_e) = T_{\hbox{actual}}(S_b \rightarrow S_e) + \Phi(S_e) - \Phi(S_b)$$

In our case, we want all increments to have their amortised time to be at most 2. So:

$$2 \ge T_{\hbox{actual}}(0 \rightarrow 1) + \Phi(1) - \Phi(0) = 1 + \Phi(1) - \Phi(0)$$ $$2 \ge T_{\hbox{actual}}(1 \rightarrow 10) + \Phi(10) - \Phi(1) = 2 + \Phi(10) - \Phi(1)$$ $$2 \ge T_{\hbox{actual}}(10 \rightarrow 11) + \Phi(11) - \Phi(10) = 1 + \Phi(11) - \Phi(10)$$

And so on. This gets us somewhere, because it gives us some bounds on what the potential function might be.

There are a number of potential functions which could satisfy these constraints. In this case, however, there's a straightforward optimal solution. Setting $\Phi(0) = 0$ and making the inequalities equalities gives us the potential function:

$$\Phi(0) = 0$$ $$\Phi(1) = 1$$ $$\Phi(10) = 1$$ $$\Phi(11) = 2$$ $$\Phi(100) = 1$$

There's no obvious pattern so far, but if you extend this on, you'll find that $\Phi(S)$ is the number of 1's in $S$ (i.e. the Hamming weight of $S$). This makes intuitive sense, when you think about it: Incrementing a zero takes only one flip, but incrementing a one takes more than one. So the number of ones in the string is a measure of how "hard" it will be to increment it in the future. It's a reasonable analogue of "potential energy".

Now that we've identified a candidate potential function, we can now work forward again to try to prove the result.