"Фибоначчиевое" умножение

При выводе правила "фибоначчиевого" умножения мы начнем из аналогии между "двоичной" и "фибоначчиевой" арифметиками. Пусть требуется умножить два числа A и B, представленные в классическом "двоичном" коде. Представляя число B в n-разрядном "двоичном" коде, мы можем записать произведение P = A ´ B в следующем виде:

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

где bi - "двоичные" цифры числа B. Из (1) вытекает, что "двоичное" умножение сводится к формированию частичных произведений типа A´bi2i-1 и их последующему сложению.

Алгоритм "двоичного" умножения, основанный на (1), имеет длительную историю и берет свое начало от египетского метода умножения путем "удвоения".

Как известно, египтяне не знали таблицы умножения и использовали следующую "аддитивную" процедуру для умножения. Предположим, что необходимо умножить число 305 на 41. Для этого египетский математик использовал таблицу следующего типа:

LR  
/1305=>305
2610  
41 220  
/82 440=>2 440
164 880  
/329 760=>9 760
-------------------------------
 41 ´ 305=12 505.

Разместим "двоичные" числа типа 2k (k = 0, 1, 2, ...) в левом столбце L. В столбец R запишем числа типа 305 ´ 2k , сформированные из исходного числа 305 путем "удвоения". Обозначим знаком / такие "двоичные" числа столбца L, которые в сумме образуют второй сомножитель: 41 = 1 + 8 + 32. Результат умножения представляется в виде суммы чисел столбца R, соответствующих "отмеченным" числам столбца L.

Заметим, что представление числа 41 в виде суммы "двоичных" чисел 2k дает представление числа 41 в классической "двоичной" системе счисления, то есть:

41 = 1 0 1 0 0 1.

Существенно подчеркнуть, что "удвоение" числа 305, представленного в виде двоичной кодовой комбинации, выполняется путем ее сдвига на один разряд влево. Отсюда вытекает, что рассмотренный выше метод умножения, основанный на (1), по существу совпадает с египетским методом умножения путем "удвоения".

Анализ египетского метода умножения позволяет по аналогии предложить следующий метод "фибоначчиевого" умножения.

Представим сомножитель B в произведении P = A ´ B в виде кода Фибоначчи. Тогда произведение P может быть записано в следующем виде:

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

где bi - двоичные цифры в "фибоначчиевом" представлении числа В; Fi (i = 1, 2, ..., n) - числа Фибоначчи.

Из выражения (2) вытекает, что "фибоначчиевое" умножение сводится к сложению частичных произведений типа A´biFi. Частичные произведения A´biFi формируются из исходного числа A путем следующей процедуры, которая лежит в основе "фибоначчиевого" умножения.

Продемонстрируем эту процедуру на примере умножения чисел 41 ´ 305. С этой целью составим таблицу следующего типа:

LR  
1305  
1305  
/2610=>610
3915  
/51 525=>1 525
82 440  
133 965  
216 405  
/3410 370=>10 370
-------------------------------
 41 ´ 305=12 505.

В столбец L записываются числа Фибоначчи 1, 1, 2, 3, 5, 8, ... и знаком / отмечаются те числа Фибоначчи, которые в сумме образуют один из сомножителей: 41 = 2 + 5 + 34. В столбец R записываются обобщенные числа Фибоначчи Gk с начальными членами G1 = G2 = 305. Суммируя числа столбца R, соответствующие "отмеченным" числам столбца L, мы получаем результат "фибоначчиевого" умножения:

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

Этот пример показывает, как полезно изучать историю математики для любознательных исследователей. Кажется удивительным, что решение проблемы "фибоначчиевого" умножения было найдено в египетской арифметике! Любопытно отметить, что "фибоначчиевый" умножитель, основанный на этом алгоритме, был признан изобретением пионерного характера!