3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ This reads like you're asking us to help you do your exercise. Rather than asking us how to do the exercise, can you edit your post to ask about some concept that you don't understand? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. The potential function method is well-described in standard textbooks and other online resources; have you studied them carefully? That might be your next step. $\endgroup$ – D.W. Feb 29 '16 at 22:24
  • $\begingroup$ Well, I understand what a potential function is, like I said in the first paragraph I just have trouble defining a good one for this problem. I just need some sort of hint on how to incorporate the properties of the increment operation to fit a potential function that offsets the actual cost. Like I observed, each increment is gonna change some x amount of consecutive Fibonacci numbers, so I don't really know how to define a potential function that would decrease in relationship to that. $\endgroup$ – pinoyboy Feb 29 '16 at 23:07
  • $\begingroup$ The analysis probably proceeds exactly like the binary counter example you have probably seen in class. $\endgroup$ – Raphael Mar 1 '16 at 7:56
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.