Fibonacci addition

In our "Computer Age" every pupil knows the following table of the "binary" addition:

Table 1.
0+0=0
0+1=1
1+0=1
1+1=1 0

Note that the last row of Table 1 gives the rule of the carry formation at the "binary" addition of the single "binary" digits (1 + 1 = 10).

Also note that the last row of this table reflects the following identity of the "binary" numbers:

2k + 2k = 2k+1.

Like to the "binary" number system the "deduction" of the Fibonacci addition rule begins with the analysis of the sum:

Fk + Fk,(1)

where

Fk = Fk-1 + Fk-2;(2)
F1 = F2 = 1.(3)

Taking into consideration the expressions (2), (3) we can represent the sum (1) as the following:

Fk + Fk = Fk + Fk-1 + Fk-2;(4)
Fk + Fk = Fk+1 + Fk-2.(5)

It follows from (4), (5) the next table for Fibonacci addition of two binary digits ak + bk with the same index k:

Table 2.
0+0=   0
0+1=   1
1+0=   1
1+1=   1 1 1 (a)
1+1=1 0 0 1 (b)
    Of what is a peculiarity of Table 2 in comparison to Table 1? We can see that the first three rows of Table 1 and Table 2 coincide. The last two rows give the rule of the carry formation at the Fibonacci addition of the binary digits ak + bk = 1 + 1:
  1. At the Fibonacci addition of 1 + 1 there arise the carry of two binary 1's from the k-th digit to the neighboring two digits.
  2. There exist two methods of the carry formation. For the method (a) the binary 1 is written to the k-th digit of the intermediate sum and there arise two binary 1 to the next two lower digits namely to the (k - 1)-th and (k - 2)-th ones. The method (b) assumes the another rule of the Fibonacci addition of binary digits 1 + 1. The binary 0 is written to the k-th digit of the intermediate sum and there arise two binary 1 to the next two digits, the first one to the (k + 1)-th digit and the second one to the (k - 2)-th digit.
    The addition of the multi-digit numbers in the Fibonacci code is performed in accordance with Table 2. However one must be fulfilled the following rules:
  1. Before the Fibonacci addition the summable Fibonacci code representations are reduced to the minimal form.
  2. In accordance with Table 2 the multi-digit intermediate sum and the multi-digit carry are formed.
  3. The multi-digit intermediate sum is reduced to the minimal form and then is added with the multi-digit carry.
  4. The addition process lasts in accordance with the rules 2, 3 until the obtaining the 0-carry. The last intermediate sum reduced to the minimal form is the addition result.
    For the Fibonacci addition it is necessary to fulfill the following addition rule:
  1. Suppose we have two binary 1's in the k-th digits of the summable numbers represented in the minimal form. It follows from the minimal form property that the binary numerals of the (k + 1)-th and (k - 1)-th digits of the both of the summable Fibonacci code representations are equal to 0 exactly. It is clear that for this case the intermediate sums arising at the addition of the (k + 1)-th and (k - 1)-th digits of the both summable numbers are equal to 0 exactly. It means that we can write one of the carries from the k-th digits (1 + 1) at once in the (k - 1)-th digit of the intermediate sum (the (a)-method of the Fibonacci addition) or (k + 1)-th digit of the intermediate sum (the (b)-method of the Fibonacci addition).

Let's demonstrate the above-considered addition rules by the following example.

Example 1. Add the numbers of 31 = 1 0 0 1 1 0 1 1 and 22 = 0 1 0 1 1 0 1 0 represented in the Fibonacci code.

The first step is reducing the numbers to the minimal form:

31 = 1 0 0 1 1 0 1 1 = 1 0 1 0 0 1 0 0,
22 = 0 1 0 1 1 0 1 0 = 0 1 1 0 0 0 1 0 = 1 0 0 0 0 0 1 0.

The second step is the formation of the multi-digit intermediate sum S1 and the multi-digit carry C1 in accordance with the method (a) of Table 1

31 = 1 0 1 0 0 1 0 0
+
22 = 1 0 0 0 0 0 1 0
---------------------
S1 = 1 1 1 0 0 1 1 0
C1 = 0 0 1 0 0 0 0 0

Note that in this case the situation of 1 + 1 arises for the higher Fibonacci digits. These digits and the arising from them digit transformations in the intermediate sum S1 and the multi-digit carry C1 are underlined.

The third step is reducing the intermediate sum S1 to the minimal form:

S1 = 0 1 1 1 0 0 1 1 0 = 1 0 0 1 0 1 0 0 0.

The fourth step is the addition of S1 and C1:

S1 = 1 0 0 1 0 1 0 0 0
+
C1 = 0 0 0 1 0 0 0 0 0
-----------------------
S2 = 1 0 0 1 1 1 0 0 0
C2 = 0 0 0 0 0 1 0 0 0

The digits of 1 + 1 and the arising from them transformations in S2 and C2 are underlined.

The fifth step is reducing the intermediate sum S2 to the minimal form:

S2 = 1 0 0 1 1 1 0 0 0 = 1 0 1 0 0 1 0 0 0.

The sixth step is the Fibonacci addition of S2 and C2:

S2 = 1 0 1 0 0 1 0 0 0
+
C2 = 0 0 0 0 0 1 0 0 0
-----------------------
S3 = 1 0 1 0 0 1 1 0 0
C3 = 0 0 0 0 0 0 0 1 0

The seventh step is reducing the intermediate sum S3 to the minimal form:

S3 = 1 0 1 0 0 1 1 0 0 = 1 0 1 0 1 0 0 0 0.

The eighth step is the Fibonacci addition of S3 and C3:

S3 = 1 0 1 0 1 0 0 0 0
+
C3 = 0 0 0 0 0 0 0 1 0
-----------------------
S4 = 1 0 1 0 1 0 0 1 0
C4 = 0 0 0 0 0 0 0 0 0

The addition is over because there arises the 0- carry C4 at the eighth step.

Although the procedure of the Fibonacci addition seems complicated and tiring but it is only at the first glance. After acquisition of some experience this procedure finds itself not such yet complicated! We welcome you to do some examples of the Fibonacci addition! And now we pass to the next arithmetical operation, the Fibonacci subtraction. Follow us!