Fibonacci division And now we demonstrate the procedure of the Fibonacci division. But we begin since the division procedure used by Egyptians. Let's suppose we need to divide the number of 481 by the number of 13. The division is performed in the following way. At the first stage the table consisting of three columns, namely the left (L), middle (M) and right (R) columns, is composed: The first stage
The binary numbers of the kind 2^{k} (k = 0, 1, 2, ...) are arranged in the L-column. The M-column consists of the numbers of the kind 13 ´ 2^{k} formed from the divisor 13 by means of the "doubling". After every "doubling" we compare the corresponding numbers of the M-column with the number of 481 (R-column). This process lasts until the finding the M-number, which is bigger than the corresponding R-number (832 > 481). After that we subtract the preceding M-number of 416 from the R-number of 481 (481 - 416 = 65) and mark with the sign / the L-number corresponding to the M-number of 416. The second stage consists of the repetition of the first stage for the remainder of 65 obtained at the first stage, i.e.
The third stage is the repetition of the first stage for the remainder of 13 obtained at the second stage, i.e.
Let's select now all the L-numbers marked with the sign / . Their sum is the result of the division, i.e. 32 + 4 + 1 = 37. The Egyptian "doubling" method of the division is the basis of the Fibonacci division method. Let's demonstrate the latter by the following example. Let's divide the number of 481 by the number of 13 in the Fibonacci number system. The Fibonacci division of these numbers consists of two stages. The first stage
The second stage
We can see that the division result is the sum of the marked L-numbers, i.e. 34 + 3 = 37. It seems to be incredible but the algorithms of the Fibonacci multiplication and division following from the Egyptian "doubling" methods were realized in the form of the Fibonacci multiplication and division devices. And then these devices were recognized as the pioneering inventions in USSR and other countries! |