Fibonacci addition In our "Computer Age" every pupil knows the following table of the "binary" addition:
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: 2 Like to the "binary" number system the "deduction" of the Fibonacci addition rule begins with the analysis of the sum:
where
Taking into consideration the expressions (2), (3) we can represent the sum (1) as the following:
It follows from (4), (5) the next table for Fibonacci addition of two binary digits
- 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. - 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.
a_{k} + b_{k} = 1 + 1:
- Before the Fibonacci addition the summable Fibonacci code representations are reduced to the minimal form.
- In accordance with Table 2 the multi-digit intermediate sum and the multi-digit carry are formed.
- The multi-digit intermediate sum is reduced to the minimal form and then is added with the multi-digit carry.
- 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.
- 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.
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
0 = 1 0 0 1 0 1 0 0 0.0 1 1
The digits of 1 + 1 and the arising from them transformations in
The addition is over because there arises the 0- carry 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! |