"Фибоначчиевое" деление

А теперь мы продемонстрируем процедуру "фибоначчиевого" деления. И мы начнем с процедуры деления, предложенной древними египтянами. Предположим необходимо разделить число 481 на число 13. Деление осуществляется следующим образом. На первом этапе составляется таблица, состоящая из трех столбцов, левого (L), среднего (M) и правого (R), то есть:

LM R
113£481
226£481
452£481
8104£481
16208£481
/32416£481
64832>481
-----------------------------
 481 - 416=65

В столбце L записываются числа типа 2k (k = 0, 1, 2, ...). Столбец M состоит из чисел типа 13 ´ 2k , образующихся из делителя 13 путем "удвоения". После каждого "удвоения" мы сравниваем соответствующие числа столбца M с числом 481, записанным в столбец R. Этот процесс продолжается до тех пор, пока очередное число столбца M не станет больше числа, записанного в столбец R (832 > 481). После этого мы вычитаем предыдущее число 416 столбца M из числа 481, в результате чего получаем первый остаток от деления (481 - 416 = 65), и отмечаем знаком / число 32 столбца L, соответствующее числу 416.

Второй этап состоит в повторении первого этапа для остатка 65, полученного на первом этапе, то есть:

LM R
113£65
226£65
/452£65
8104>65
--------------------------
 65 - 52=13

Третий этап состоит в повторении первого этапа для остатка 13, полученного на втором этапе, то есть:

LM R
/113£13
226£13
--------------------------
 13 - 13=0

Выделим теперь все числа в столбцах L, отмеченных знаком /. Их сумма и есть результат деления, то есть:

32 + 4 + 1 = 37.

Египетский метод деления, основанный на принципе "удвоения", является основой для "фибоначчиевого" деления. Продемонстрируем "фибоначчиевый" метод деления на следующем примере. Пусть необходимо разделить число 481 на число 13 в "фибоначчиевой" системе счисления. Тогда "фибоначчиевое" деление состоит из следующих этапов.

Первый этап
LM R
113£481
113£481
226£481
339£481
565£481
8104£481
13169£481
21273£481
/34442£481
55715>481
-----------------------------
 481 - 442=39


Второй этап
LM R
113£39
113£39
226£39
339£39
565>39
---------------------------
 39 - 39=0

Мы видим, что результат деления равен сумме "отмеченных" чисел в столбцах L, то есть:

34 + 3 = 37.

Это звучит невероятно, но рассмотренные выше алгоритмы "фибоначчиевого" умножения и деления были затем реализованы в виде "фибоначчиевых" устройств умножения и деления, которые были признаны в СССР и других странах пионерными изобретениями!