Fibonacci Codes

Fibonacci's measurement algorithms are one of the most unexpected results of the algorithmic measurement theory. These algorithms have the following numerical interpretation. They "generate" the following method of number representation:

 N = anFp(n) + an-1Fp(n - 1) + ... + aiFp(i) + ... + a1Fp(1), (1)

where ai Î {0, 1} is the binary numeral of the i-th digit of code (1); n is the digit number of code (1); Fp(i) is the i-th digit weight calculated in accordance with the recurrent correlation:

 Fp(i) = Fp(i - 1) + Fp(i - p - 1) with i > p + 1; (2) Fp(1) = Fp(2) = ... = Fp(p + 1) = 1. (3)

The positional representation of the natural number N in form (1) is called the p-Fibonacci code. The abridged notation of p-Fibonacci code (1) has the following form:

 N = an an-1 ... a1. (4)

Note that the concept of the p-Fibonacci code includes an infinite number of the different methods of the positional number representations because every p "generates" its own p-Fibonacci code (p = 0, 1, 2, 3, ...).

Let p = 0. For this case the 0-Fibonacci numbers F0(i) coincide with the binary numbers, i.e.

F0(i) = 2i-1.

The representation (1) for this case has the following well-known form:

 N = an2n-1 + an-12n-2 + ... + ai2i-1 + ... + a120. (5)

Let p = ¥. In this case each p-Fibonacci numbers equals to 1, i.e. we have for any arbitrary i

Fp(i) = 1.

Then the representation (1) takes the following form:

 (6)

Thus, the p-Fibonacci code is a very wide generalization of the binary code (5) and includes the latter as the extreme partial case for p = 0. On the other hand, the p-Fibonacci code includes in itself so-called "unitary" code (6) as the another extreme case for p = ¥.

But how we can get the Fibonacci representation of some natural number, for example, the number 30. To get the Fibonacci representation of 30 we have to write Fibonacci numbers in the opposite order:

34, 21, 13, 8, 5, 3, 2, 1, 1.

Then we should compare successfully number 30 with Fibonacci numbers starting since the biggest one. The Fibonacci code of 30 is demonstrated with help of the following table:

 34 21 13 8 5 3 2 1 1 30 0 1 0 1 0 0 0 1 0

Let's compare the number 30 with Fibonacci number 34; since 30 < 34 we write bit 0 to the second row and the second column of the table. Then we compare the number 30 with the next Fibonacci number 21. Since 30 ³ 21, we write of 1 to the second row and the third column of the table. After that we calculate the difference 30 - 21 = 9 and then compare the number 9 with the next Fibonacci numbers 13, 8, ..., 2, 1, 1. As result of this procedure we get the Fibonacci representation of the number 30:

30 = 0 1 0 1 0 0 0 1 0.

This positional representation is nothing as the abridged notation of the following sum:

30 = 21 + 8 + 1.

Thus, the algorithmic measurement theory brings us into small mathematical discovery in the field of number systems. We have got some generalization of the "binary" number system. Due this discovery we know now that there exist an infinite number of the "binary" positional representations, which are given with the general formula (1). And the classical "binary" number system (5) is the partial extreme case of the Fibonacci representation (1).

But the "binary" number system (5) is the basis of modern computers. There arises a question: if we use the Fibonacci representations (1) in computers possibly we can come to Fibonacci computers as a new idea in development of computers? And we will tell about development of this idea at the next pages of our Museum. Follow us!