Greedy algorithm for finding a negafibonacci representation of a number?

Question

According to Zeckendorf's theorem, every positive integer can be written in a unique way as the sum of non-consecutive distinct Fibonacci numbers. Such a decomposition can be found easily with a greedy algorithm consisting essentially in subtracting the largest Fibonacci number that fits and iterating, for example:

20 = 13 + 7 = 13 + 5 + 2

However, the theorem also implies that any integer (also <= 0) has a unique decomposition as a sum of distinct, non-consecutive negaFibonacci numbers, that is the sequence

0, 1, -1, 2, -3, 5, -8, ...

or F_(-n) = (-1)^(n+1) F_n. Some examples:

-4 = - 3 - 1

4 = 5 + 1

11 = 13 - 3 + 1

Is there a known easy algorithm for decomposing a given integer in this way?

Answer 1

There is a nice greedy algorithm you can use to represent numbers in negafibonacci.

The idea behind this algorithm is to split the integers into ranges delimited by pairs of even Fibonacci numbers (in the positive case) and odd Fibonacci numbers (in the negative case). Specifically, we'll split the positive numbers into the ranges

• F₀ + 1 to F₂, inclusive,
• F₂ + 1 to F₄, inclusive,
• F₄ + 1 to F₆, inclusive,
• F₆ + 1 to F₈, inclusive,
• F₈ + 1 to F₁₀, inclusive,
• ...
• F_2k + 1 to F_2k+2, inclusive,
• ...

We'll similarly split the n numbers into these ranges demarcated by negative Fibonacci numbers:

• -F₁ to -F₃ + 1, inclusive,
• -F₃ to -F₅ + 1, inclusive,
• -F₅ to -F₇ + 1, inclusive,
• -F₇ to -F₉ + 1, inclusive,
• ...
• -F_2k-1 to -F_2k+1 + 1, inclusive,
• ...

The greedy algorithm then proceeds as follows:

• If the number is positive, find the range [F_2k + 1, F_2k+2] containing n, add F_2k+1 to the representation, and subtract F_2k+1 from n.
• If the number is negative, find the range [-F_2k-1, -F_2k+1 + 1] containing n, add -F_2k to the representation, and add F_2k to the total.
• If the number is zero, you're done.

Let's do an example. Suppose I want to convert 27 into negafibonacci. I find that 21 + 1 ≤ 27 ≤ 55. This sandwiches the (odd-index) Fibonacci number 34, so I add 34 to the total and then try to convert 27 - 34 = -7 into negafibonacci.

Next, we notice that 5 + 1 ≤ 7 ≤ 13, so 7 is sandwiched in a range containing the (even-indexed) Fibonacci number 8. We therefore add -8 into the total and try to convert 1 to negafibonacci.

Now, we notice that 0 + 1 ≤ 1 ≤ 1, so 1 is sandwiched in a range containing the (odd-indexed) Fibonacci number 1. We therefore add 1 into the total and try to convert 0 to negafibonacci.

This leaves a total of 0, so we're done! And hey! 34 - 8 + 1 = 27.

Let's first argue correctness. First, notice that if we add in a positive Fibonacci number, it must be an odd-numbered Fibonacci number (since we pick something of the form F_2k+1), and if we add in a negative Fibonacci number, it must be a negative even-numbered Fibonacci number (since we pick something of the form -F_2k). So each number added in will have the proper sign.

Next, we'll prove termination. Look at the positive case first. If we find that we have a number in the range [F_2k + 1, F_2k+2], then we subtract out F_2k+1. The upper bound on the number is then F_2k+2 - F_2k+1 = F_2k, so the largest interval containing the remainder will fall in the range [F_2k-2 + 1, F_2k] and the highest Fibonacci number we could pull out would be F_2k-1. Therefore, we can't repeat the Fibonacci number we previously removed, and there will be a gap between the positive numbers pulled out.

The lower bound on the number is F_2k + 1 - F_2k+1 = -F_2k-1 + 1. That means that if the number is negative, the "highest" negative interval containing it would be [F_2k-1 + 1, F_2k-3], so the highest negative Fibonacci number we could pull out is F_2k-2. Therefore, we will pull out a lower-order Fibonacci number.

We can do similar math to show that pulling out a negative Fibonacci number shifts our window down one step.

To implement this efficiently, we can keep track of three consecutive Fibonacci numbers (F_k-1, F_k, F_k+1) and keep shifting it upward (or downward) until we find a range containing the number n. We can then pull out our (possibly negative) Fibonacci number and then shift the window back toward 0 until we're done. Overall, this will run in time O(log n).