The main operations of the Fibonacci arithmetic

Earlier when we considered the "algorithmic measurement theory" we introduced the concept of the p-Fibonacci codes and showed that they are the generalization of the classical binary code concept.

It is very important to use an analogy between the classical binary number system and the p-Fibonacci codes when we "design" the Fibonacci arithmetic. And we will use the following method for the proof of the arithmetical rules of the Fibonacci arithmetic. First we will analyze the corresponding rule for the classical binary arithmetic and then we will "deduce" the similar rule for the Fibonacci arithmetic.

However we begin from the simplest Fibonacci representation, which corresponds to the 1-Fibonacci code and uses the classical Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, ..., Fn as the "weights" of the Fibonacci representation:

N = anFn + an-1Fn-1 + ... + aiFi + ... + a1F1(1)

First of all we will consider a number of the distinctive and very important operations and concepts of the Fibonacci arithmetic.

The "convolution" and the "devolution" are the main operations of the Fibonacci arithmetic. They are based on the Fibonacci recurrent correlation connecting the Fibonacci "weights" in (1):

Fi = Fi-1 + Fi-2,(2)
F1 = F2 = 1.(3)
    They are the following code interpretations:
  1. The "convolution": 011 ® 100;
  2. The "devolution": 100 ® 011.

This means that if we have a possibility to fix some code combination 011 (or 100) in the Fibonacci code representation of natural number N we can replace it by the code combination 100 (or 011) without a change of number value.

The "minimal" and "maximal" forms of the Fibonacci code representations are important concepts of the Fibonacci arithmetic. If we carry out in some Fibonacci code representation all possible operations of the "convolution" we will come to the "minimal" form. For example,

0111011 0111 = 1001101001 = 1010001010 (the "minimal" form).

Here all the "convolutions" carried out in the Fibonacci code representations are underlined.

Here the right code representation is the "minimal" form. Its peculiarity consists of the fact that two binary 1's alongside do not meet.

If we carry out in some Fibonacci code representation all possible operations of the "devolution" we will come to the "maximal" form. For example,

1000000 = 0110000 = 0101100 = 0101011 (the "maximal" form).

Here all the "devolutions" carried out in the Fibonacci code representations are underlined.

Here the right code representation is the "maximal" form. Its peculiarity consists of the fact that two binary 0's alongside do not meet.

Let's remind that the realization of the "convolution" and "devolution" in the Fibonacci code representation, which represents some natural number N, does not change the number of N.

And now we demonstrate applications of these basic concepts of the Fibonacci arithmetic for realization of the simplest arithmetical operations, the count and subtraction of 1's. These arithmetical operations determine functioning the Fibonacci counters.

Let's consider the functioning the Fibonacci "summing" counter:

0 = 000000 + 1
1 = 000001 = 000010 + 1
2 = 000011 = 000100 + 1
3 = 000101 = 000110 = 001000 + 1
4 = 001001 = 001010 + 1
5 = 001011 = 001100 = 010000 + 1
6 = 010001 = 010010 = 010010 + 1
7 = 010011 = 010100 + 1
8 = 010101 = 010110 = 011000 = 100000 + 1 and so on.

We can see from the example that the functioning of the "summing" counter is reduced to the "convolution".

Let's consider now the functioning the Fibonacci "subtracting" counter:

5 = 10000 = 01100 = 01011 - 1
4 = 01010 = 01001 = 00111 -1
3 = 00110 = 00101 - 1
2 = 00100 = 00011 - 1
1 = 00010 = 00001 - 1
0 = 00000

We can see from the example that the functioning of the "subtracting" counter is reduced to the "devolution".

Comparison of the Fibonacci code combinations. As is well known the comparison of the classical "binary" codes is realized very simply. We should look of the compared code combinations A and B digit-by-digit starting since the higher digit until the detection of the distinct digits of ak and bk. If ak = 1 and bk = 0 this means that A > B.

The comparison procedure for the Fibonacci code combinations A and B is similar. However before the comparison the Fibonacci code combinations A and B should be reduced to the minimal form.

For example, to compare the Fibonacci code combinations A = 01110110 and B = 01111001. The first step is the reducing A and B to the minimal form:

A = 01110110 = 10011000 = 10100000
B = 01111001 = 10011010 = 10100010

The comparison of the A and B minimal forms shows that B > A.

Note that first the Fibonacci arithmetic is stated in Stakhov's article "The redundancy binary positional number systems" published in the Journal of the Taganrog Radio University "Homogeneous Digital Computers and Integrated Structures" (Taganrog, 1974).

The Journal of the Taganrog Radio University 'Homogeneous Digital Computers and Integrated Structures' (Taganrog, 1974)Stakhov's article 'The redundancy binary positional number systems'

Later this arithmetic was described in Stakhov's books "Introduction into Algorithmic Measurement Theory" (1977) and "Codes of Golden Proportion" (1984).

Stakhov's book 'Introduction into Algorithmic Measurement Theory' (1977)Stakhov's book 'Codes of Golden Proportion' (1984)

And we will tell about Fibonacci's operations of addition, subtraction, multiplication and division at the next pages of our Museum. Follow us!