Fibonacci multiplication

We begin from an analogy between the "binary" and Fibonacci arithmetics. Let's suppose that we need to multiply two numbers A and B represented in the classical "binary" code. Representing the number of B in the n-digit binary code we can write the product P = A ´ B in the following form:

 P = A´bn2n-1 + A´bn-12n-2 + ... + A´bi2i-1 + ... + A´b120, (1)

where bi is the binary digits of the number of B. It follows from (1) that the binary multiplication is reduced to forming the partial products of the kind A´bi2i-1 and their addition.

The binary multiplication algorithm based on (1) has a long history and goes back in its origin to the Egyptian "doubling" method of multiplication.

As is well known that the Egyptian mathematicians did not know the table of multiplication and they used the following procedure for multiplication. Let's suppose it is necessary to multiply the number of 305 by the number of 41. The Egyptian mathematician forms the table consisting of two columns in the following way:

 L R /1 305 => 305 2 610 4 1 220 /8 2 440 => 2 440 16 4 880 /32 9 760 => 9 760 ------------------------------- 41 ´ 305 = 12 505.

Let's arrange now the binary numbers of the kind 2k (k = 0, 1, 2, ...) in the left column L of the table. The right column R consists of the numbers of the kind 305 ´ 2k formed out from the initial number of 305 by means of "doubling". Let's mark with the sign / those binary numbers of the L-column, which make up the second number 41 = 1 + 8 + 32 in the sum. The result of the multiplication is presented as the sum of the R-column numbers corresponding to the marked binary numbers of the L-column.

Note that decomposition of the number 41 in the form of the sum of the binary numbers of 2k gives the representation of the number of 41 in the classical binary number system, i.e.

41 = 1 0 1 0 0 1.

It is essential to emphasize that the "doubling" the number of 305 presented in the binary code is performed by its shift to the left by one digit. It follows from this consideration that the above-considered multiplication method based on the correlation (1) coincides in essence with the Egyptian multiplication method by means of the "doubling".

The analysis of the Egyptian multiplication method allows to suggest the following method of the Fibonacci multiplication.

Let's represent the number of B in the product P = A ´ B in the form of the Fibonacci code. Then the product P may be written in the following form:

 P = A´bnFn + A´bn-1Fn-1 + ... + A´biFi + ... + A´b1F1, (2)

where bi are the binary numerals of the Fibonacci representation of the number of Â; Fi (i = 1, 2, ..., n) are Fibonacci numbers.

It follows from the expression (2) that the Fibonacci multiplication is reduced to the addition of the partial products of the kind of A´biFi. The partial products A´biFi are formed from the initial number A by means of the following procedure, which underlies the Fibonacci multiplication.

Let's demonstrate this procedure for example of the numbers 41 ´ 305. With this in mind let's form the table consisted of the L- and R-columns:

 L R 1 305 1 305 /2 610 => 610 3 915 /5 1 525 => 1 525 8 2 440 13 3 965 21 6 405 /34 10 370 => 10 370 ------------------------------- 41 ´ 305 = 12 505.

We arrange the Fibonacci series 1, 1, 2, 3, 5, 8, ... in the L-column and mark with the sign / those Fibonacci numbers of the L-column, which make up the second number 41 = 2 + 5 + 34 in the sum. The R-numbers are the generalized Fibonacci numbers Gk with the initial terms G1 = G2 = 305. Summing the R-numbers corresponding to the marked L-numbers we get the result of the Fibonacci multiplication, that is:

41 ´ 305 = 610 + 1525 + 10370 = 12 505.

This case shows how it is useful to study history of mathematics for inquisitive researcher. It seems to be incredible but the solution of the Fibonacci multiplication can be found in Egyptian arithmetic!