What is Base Fibonacci?

Base Fibonacci, or BF, refers to the idea of using the Fibonacci sequence as a base for writing numbers. This is possible because of the following theorem:

Zeckendorf's Theorem
Any non-negative integer can be written uniquely as a sum of distinct, non-consecutive Fibonacci numbers.

For a proof, see Michael Penn's video above, or the Wikipedia article on Zeckendorf's Theorem.

Here are some examples:

4 = 3 + 1 = F₃ + F₁
5 = F₄
6 = F₅ + F₁
7 = 5 + 2 = F₄ + F₂
12 = 8 + 3 + 1 = F₅ + F₃ + F₁

Here I'm indexing the Fibonacci numbers so that F₀ = 1, F₁ = 1.

We can also represent these as binary numbers where the weights of the bits are Fibonacci numbers.

Converting to and from Base Fibonacci

Converting a BF representation of a number to an ordinary base such as binary or decimal is straightforward. We just have to add up the weights associated with the 1 bits. For example,

gives 21 + 5 + 2 = 28.

To convert the other way, we can proceed as follows. Given a number n, find the largest Fibonnaci number F_i less than or equal to n, and add it to the result. Then subtract F_i from n, and continue in the same way until the remainder is zero.

For example, let n = 51. The largest Fibonacci number not greater than 51 is 34, leaving 17. The next largest is 13, leaving 4, then 3 leaving 1, then 1 leaving 0. So the result is

Arithmetic in Base Fibonacci

The existence of BF raises some interesting questions. Are there efficient algorithms for performing arithmetic on BF representations of numbers? Could a computer be designed that works entirely in BF? Let's find out!

Addition

Adding ordinary binary numbers is easily done bit-by-bit using the following table:

Can we make a similar table for BF addition?

It's not immediately obvious what should go in the bottom right entry. But we can get a clue from the following observation:

So when we add two corresponding 1 bits in a pair of BF numbers, not only do we get an upwards carry to the left, we also get a downwards carry two places to the right. That means the BF addition table looks like this:

How can we make use of this to add multi-bit numbers? Let's look at an example:

What we've done here is worked right to left, treating the upward carries (the superscripts) as in a normal binary addition, and stashing the downward carries away for later in the last row. We're not worrying about creating consecutive 1 bits at this stage, we'll fix that later.

Now we need to add on the downward carries:

That results in more downward carries that we will need to add on. We also have a bit of a problem, because we've generated a carry beyond the rightmost bit! To figure out what to do with it, we can extend the sequence of weights to the right using the fact that F_n-1 = F_n+1 - F_n:

Since the weight of the F₀ position is 1, we can move the overhanging carry into the F₁ position.

We get a carry in the F_-1 position, but it has weight 0, so we can ignore it. We just need to add the remaining downward carry.

There are no carries left now, but we're not quite finished. If we want the result in a canonical BF representation, we need to normalise it to eliminate consecutive 1 bits. We'll talk about that shortly, but first a few observations about the process we used for addition.

We had to perform multiple iterations to deal with all the downwards carries, because adding carries created more carries. You might wonder whether there is an upper bound on the number of iterations required. There must be, because the result can only get bigger as carries are added on, so eventually we must get to the final result. However, the maximum number of iterations is at least proportional to the number of bits being added. Consider the following example:

Clearly this pattern can continue indefinitely. If we take the unit of work to be the addition of two bits, this algorithm appears to be O(n²) in the word size. It would be more satisfying if we could find an algorithm that was O(n) in the word size, which would be more in line with ordinary binary arithmetic. We will come back to this problem later.

Normalisation

To normalise a BF representation, we need to find pairs of consecutive 1 bits and replace them by 100. It will be easiest to work from left to right, because at each stage the leftmost 11 will always have a 0 before it for the extra 1 to go into. We could work in a different order and get the same result, but then in some cases we would have to deal with propagating carries.

Let's try this on the result from Example 1.

Replacing the first 11 with 100 gives

Replacing the second 11 gives

Now we have another 11 to replace, and so forth for a few more steps.

Now we have our final result:

This is what we expect, since we started with 82 + 28 = 110.

Optimising normalisation

We can streamline the normalisation process a little by making use of  the following observations:

1. A sequence of bits not containing 11 that extends to the end of the number will remain as-is.
2. A sequence of bits not containing 11 that ends in 00 will remain as as-is, except possibly for the last bit.
3. A sequence of alternating 1s and 0s ending in 11 will be replaced with 100...00, where the number of 0s is equal to the length of the original sequence, except possibly for the last bit.

Because in cases 2 and 3 the replacement sequence ends in 00, a carry from normalising the rest of the number can at most change the final 0 to a 1. So we can normalise a number in a single pass by looking for the above patterns and treating them in chunks. Using the previous example again:

We identify three spans of interest, two of which require replacement.

Merging these together gives the same result as before:

Representing Negative Numbers

The next thing we want to be able to do is subtraction, and that raises the question of how to represent negative numbers in BF. If we can do that, then we can subtract by negating and adding.

This is relatively easy -- we can represent negative numbers in a way analogous to twos-complement in ordinary binary arithmetic.

It turns out that the maximum number representable in n Fibonacci bits is F_n+1 - 1. We can see this by noting that Zeckendorf's theorem ensures that F_n+1 - 1 is representable, and it clearly cannot contain any Fibonacci numbers greater than F_n. This means we can represent -x in n bits as as F_n+1 - x. We might call this the "Fibonacci complement" of x.

Negation

So to negate a number we need to find its Fibonacci complement. Let's look at an example.

Assuming we are working in 10 bits,  our goal is to subtract this from F₁₁:

We'll do this one bit at a time, starting at the left. We don't know how to subtract F₉ from 0, but we can rewrite F₁₁ as F₁₀ + F₉:

Now we can subtract F9, leaving

Before we can subtract F₆ we need to perform a few more replacement steps.

Now we have a bit in the F₆ position to subtract, leaving

Now we perform more replacements until we can subtract F₂.

The final result is

This is what we expect, since F₁₁ - 70 = 144 - 70 = 74.

Sign testing

The next question is, how do we tell whether a number is positive or negative?

To some extent, this is an arbitrary choice. We have a certain number of bit patterns, and we can choose to use some of them to represent positive numbers and some to represent negative numbers. But we would like to partition them as evenly as we can, so that the ranges of positive and negative numbers are more or less symmetrical.

With twos-complement binary arithmetic, this is easy -- using the leftmost bit as a sign bit gives 2^n-1 - 1 positive numbers and 2^n-1 negative numbers.

But if we do this with BF we get asymmetrical ranges. For example, in 10 bits the number of bit patterns that exclude F₁₀ is F₁₀ - 1 = 88, whereas the number that include F₁₀ is F₁₁ - 88 = 56. So we end up with more positive numbers than negative ones.

To get symmetrical ranges, we need to put the boundary between positive and negative at F_n+1 / 2. But what does this look like in BF, and is there an easy way to determine on which side of the boundary a given number lies?

It's not obvious at first how to calculate F_i / 2, but we can get a clue by rearranging and reindexing our formula above for 2F_i:

Using the same formula again to expand F_i-3 / 2,

This gives us a formula for F_i / 2 in as a sum of smaller Fibonacci numbers, plus a remainder term. Applying it recursively gives

and so forth.

If we want to complete this expansion, there are six terminating cases to consider:

1. F₁ / 2 = 1/2
2. F₂ / 2 = 2 / 2 = 1 = F₁
3. F₃ / 2 = 3 / 2 = 1 + 1/2 = F₁ + 1/2
4. F₄ / 2 = 5 / 2 = 2 + 1/2 = F₂ + 1/2
5. F₅ / 2 = 8 / 2 = 4 = 3 + 1 = F₃ + F₁
6. F₆ / 2 = 13 / 2 = 6 + 1/2 = 5 + 1 + 1/2 = F₄ + F₁ + 1/2

If we're truncating the result to an integer we can drop the remainders of 1/2, giving the following set of termination rules.

• F₁ --> 0
• F₂ --> F₁
• F₃ --> F₁
• F₄ --> F₂
• F₅ --> F₃ + F₁
• F₆ --> F₄ + F₁

We now have a complete procedure for expanding F_i / 2. Let's see what it looks like in terms of bit patterns. In the following table, an entry of ½ represents a bit that is yet to be divided by 2.

The pattern seems to be that the result starts with the bit two places down, and contains every third bit after that.

Let's look at the terminating conditions:

We can see that the "every third bit" pattern continues all the way to the end, except for cases 2 and 5. And even those cases are not all that special if we extend the table to include F₀:

It is now evident that the apparent special treatment of cases 2 and 5 can be seen as a result of replacing F₀ = 1 with F₁ = 1.

Right, so now we know how to calculate F_n+1 / 2, which will be our dividing line between positive and negative for n-bit numbers. Next we need to find a way to look at a number and tell whether it is bigger or smaller than this value. One way would be to simply add it to F_n+1 / 2 and see whether the result overflows, but maybe there is a less expensive way.

With a little thought, we can see that there is actually quite an easy way to compare any two BF numbers x and y. We simply have to compare them lexicographically from left to right. Let's take our negation example from before and test its sign using this method.

All the bits are equal until we reach F₃, where there is a 0 in x and a 1 in y, so x < y. According to our sign convention, then, 70 is positive when working in 10 bits.

As a sanity check, let's do the same thing for the negation of 70, which we calculated above to be 74.

Now the first difference is at F4, where x has a 1 and y has a 0, so x > y, meaning 74 should be considered negative.

A question that comes to mind is whether F_n+1/2 itself should be considered positive or negative. In twos-complement binary, 2^n-1 is considered to be the first negative number. We might as well adopt the same convention and regard F_n+1/2 as the first negative BF number. This also has the nice consequence that when F_n+1 is even, the non-zero numbers are divided equally into positive and negative -- in contrast to twos-complement binary, where there is always one more negative number than positive.