Algorithms for arithmetic in Fibonacci and golden ratio representations

In this article we investigate some alternative ways of representing integers and performing arithmetic operations directly on these representations. We start from observation of Edouard Zeckendorf that leads to a representation using sums of non-adjacent Fibonacci numbers. Later we show connections of this representation to a positional numeral system with irrational base of golden ratio.

Fibonacci representation

Fibonacci numbers are defined as follows:

$F_0 = 0, \quad F_1 = 1, \quad F_i = F_{i-1} + F_{i-2} \ \ \ \text{for}\ \ i \geq 2,$

thus forming an infinite sequence $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55\ldots$ Any natural number can be represented as a sum of distinct Fibonacci numbers, e.g.

$12 = 5 + 3 + 2 + 1 + 1 = F_5 + F_4 + F_3 + F_2 + F_1 =$

$\phantom{00}=8 + 3 + 1 = F_6 + F_4 + F_2$

Edouard Zeckendorf noticed that under certain conditions this representation is unique. First, we are not allowed use $F_0$ nor $F_1$ (the former is equal to $0$ anyway, and the latter is equal to $F_2$, so we would have to chose one of them). Second, we cannot use any adjacent numbers, so from any two adjacent $F_i$ and $F_{i+1}$ at most one can be used.

We can encode which Fibonacci numbers were taken using a binary string. Suppose that we limit ourselves to Fibonacci numbers smaller than $F_{k+2}$. Then we can encode it as a binary string $a_{k-1} \ldots a_1 a_0$ of length $k$. If there is no adjacent $1$s in this string, it uniquely represents number

$a_{k-1} \cdot F_{k+1} + \ldots + a_1 \cdot F_3 + a_0 \cdot F_2.$

It is easy to see that there are exactly $F_{k+2}$ such strings. The proof is easily done by induction: for $k=1$ we have two strings ($0$ and $1$), and for $k=2$ we have three ($00$, $01$, and $10$; string $11$ is invalid, since it contains adjacent $1$s). That corresponds to $F_3 = 2$ and $F_4 = 3$. For $k\geq 3$ we investigate most significant bit $a_{k-1}$: either it is $0$, and then string $a_{k-2} \ldots a_1 a_0$ of length $k-1$ can be chosen arbitrarily (resulting in $F_{k+1}$ possibilities), or $a_{k-1}=1$, and then $a_{k-2}=0$ and string $a_{k-3} \ldots a_1 a_0$ can be chosen arbitrarily (resulting in $F_k$ possibilities). Thus we have in total $F_{k+1} + F_k = F_{k+2}$ possibilities, which concludes the proof.

Following the same argument, we show that each $k$-bit string represent different natural number smaller than $F_{k+2}$. For $k\leq 2$ it is easy to check. For $k\geq 3$ numbers beginning with $a_{k-1}=0$ are distinct and smaller than $F_{k+1}$ and numbers beginning with $a_{k-1}=1$ are $F_{k+1} + x$, where $x$ are distinct and smaller than $F_k$, thus these numbers are in range from $F_{k+1}$ (inclusive) and $F_{k+1}+F_k = F_{k+2}$ (exclusive).

This way we have proved Zeckendorf's theorem: using $k$-bit string we can represent all integers from $0$ to $F_{k+2}-1$.

Basic arithmetic

In modern computers we represent integers using binary representation (positional notation with a base of $2$). One of its advantages is quite straightforward implementation of basic arithmetic operations. But this is not the only way – there are many possible numeral systems (including these with bases greater than $2$, or even negative, irrational or imaginary; or redundant binary representations).

Thus, inspired by Zeckendorf's observation, we could imagine a computer that stores integers in Fibonacci representation. (This representation could have some advantages, e.g. think that it would improve sturdiness of punch cards, should such computer use them: no adjacent $1$s means no adjacent holes). That leads to a question: how to perform basic arithmetic operations using this representation?

One possible way to deal with this question is to devise algorithms for conversion between Fibonacci representation and binary representation. Then to perform an operation in Fibonacci representation, we first convert arguments to binary, then perform the operation in binary, and finally convert the result back to Fibonacci representation. However, we do not know efficient algorithms for conversion (that is faster than $O(k^2)$ for $k$-bit numbers), so we need to perform operations directly on Fibonacci representation.

Incrementation

Let's start with incrementation by one. We have a $k$-bit number $a_{k-1} \ldots a_1 a_0$ representing $x$ and we want to obtain number $c_k c_{k-1} \ldots c_1 c_0$ representing $x+1$. This representation has additional bit $c_k$, called carry (or overflow) flag, since if $x=F_{k+2}-1$, then $x+1=F_{k}$ is not representable by a $k$-bit number.

To do the operation it suffices to do the following transformation $a_1a_0 \to c_1c_0$ on the two least significant bits:

$00. \to 01. \qquad 01. \to 10. \qquad 10. \to 11.$

and leave the remaining bits unchanged.

Unfortunately, this could lead to a pair of adjacent $1$s. We need to fix the representation, and remove such a pair. We will use the most natural transformation, which is a direct consequence of Fibonacci recurrence, thus it does not change the value of the represented integer:

$011 \to 100$

If we use it on a pair of adjacent $1$s, it will remove this pair, possibly producing new pair of adjacent $1$s two position to the left. Thus we will just apply this transformation from right to left to subsequent triplets of bits. This way we get an algorithm of incrementing a $k$-bit integer, working in $O(k)$ time.

Addition

The more complicated would be adding to $a_{k-1} \ldots a_1 a_0$ a single Fibonacci number $F_j$. If $a_j = 0$, then we only need to increment $a_j$ and take care of possible adjacent $1$s that were created. If one pair was created, we just use the idea from incrementation algorithm. If a triplet $111$ was created, we use this idea to remove the rightmost pair.

If $a_j = 1$, then we temporarily increment $a_j$ to $2$. Now we need to remove this $2$, but fortunately, it must be surrounded from both sides by $0$s (or be the last digit from the right). Thus for $j\geq 2$ we can use one of the following transformations that don't change the value of number:

$0200 \to 0111 \to 1001 \qquad 0201 \to 0112 \to 1002$

The former removes $2$ completely, the latter moves it two positions to the right. We can represent these two transformations in short form, where $x \in \{0,1\}$ and $\bar{x} = x+1$:

$020x \to 100\bar{x}$

If $2$ arrives at the right end of the string, we can use another transformations (dot follows the least significant bit):

$020. \to 101. \qquad 02. \to 10.$

After that we end up with a string consisting of $0$s and $1$s, but there could be some adjacent pairs of $1$s. But there could be only two such pairs – one generated by the first application of general rule (in $a_{j+2}a_{j+1}$ if $a_{j+2}=1$), and one generated by the last application. The latter must be preceded by $00$, thus it will be easily removed using $011 \to 100$, and the former can be removed by recursive algorithm like in incrementation algorithm.

That gives us $O(k)$ algorithm for adding $F_j$. Therefore if we want to add two $k$-bit numbers $a_{k-1} \ldots a_1 a_0$ and $b_{k-1} \ldots b_1 b_0$, we can apply this algorithm $O(k)$ times (once for each $b_j=1$). That gives us $O(k^2)$ algorithm for addition two $k$-bit numbers in Fibonacci representation.

How to do it faster? We can follow the same idea: do some incrementation and then cleanup unwanted patterns. But now we can increment all bits at once, i.e. we add both numbers position-wise, obtaining $c_j = a_j + b_j$. The number $c_{k-1} \ldots c_1 c_0$ will contain digits from set $\{0,1,2\}$. This number could have two problems: it could contain any number of $2$s (but each $2$ must be surrounded by two $0$s), and any number of strides of adjacent $1$s of arbitrary length.

First we remove all $2$s, and ignore adjacent $1$s for a while. Note that $020x \to 100\bar{x}$ transformation is not enough, since $x$ could be equal to $2$, and then we end up with yet another digit of $\bar{x} = 3$. But it turns out that this wouldn't be a big problem, since we can easily remove it using following transformation:

$030x \to 021\bar{x} \to 110\bar{x}$

But we end up with another problem: since we can have adjacent $1$s, after making transition $0201 \to 1002$ we can end up with $2$ followed by $1$. Similarly, with multiple $2$s we can end up with $1$ followed by $2$ after making transition $0200 \to 1001$. Thus we introduce two additional transitions to remove such patterns:

$021x \to 110x \qquad 012x \to 101x$

Overall we have following list of transitions:

$020x \to 100\bar{x} \qquad 030x \to 110\bar{x} \qquad 021x \to 110x \qquad 012x \to 101x$

where $x\in\{0,1,2\}$ and $\bar{x}=x+1$. Again, we need some additional transformations for the right end of the string. But instead of hard-coding these cases, we can temporarily extend our representation with two bogus bits $c_{-1} = c_{-2} = 0$, and perform only general transformations. Since both of these are $0$s, we remove $2$ for sure, but perhaps one of these bogus bit became $1$. If it is $c_{-2}$, we can ignore it completely, since it corresponds to $F_0 = 0$.

After that phase we have a string consisting of $0$s and $1$s, but it can have arbitrarily long strides of adjacent $1$s. To fix it, we apply a sweep of transformation $011 \to 100$ twice. First from left to right, which is equivalent to making following transformations for $y\in\{0,1\}$:

$y01^{2s}0 \to y(10)^s00 \qquad y01^{2s+1}0 \to y(10)^s010$

After that groups of adjacent $1$s have length at most two. We can remove them by making another sweep from right to left. Also $c_0$ and $c_{-1}$ cannot be simultaneously equal to $1$, so we can just replace it by only $c_0$ equal to $1$ if one of these bits was equal to $1$.

This way we obtain algorithm for addition of two $k$-bit numbers in Fibonacci representation, working in time complexity of $O(k)$.

To be continued…