"Фибоначчиевое" сложение

В наш "компьютерный век" каждый школьник знает следующую таблицу "двоичного" сложения:

Таблица 1.
0+0=0
0+1=1
1+0=1
1+1=1 0

Заметим, что последняя стока Табл.1 задает правило формирования переноса при "двоичном" сложении одноименных "двоичных" разрядов (1 + 1 = 10). Эта строка отражает следующее тождество для "двоичных" чисел:

2k + 2k = 2k+1.

Подобно "двоичной" системе счисления "вывод" правила "фибоначчиевого" сложения начинается с анализа следующей суммы:

Fk + Fk,(1)

где

Fk = Fk-1 + Fk-2;(2)
F1 = F2 = 1.(3)

Принимая во внимание выражения (2), (3), мы можем представить сумму (1) в следующем виде:

Fk + Fk = Fk + Fk-1 + Fk-2;(4)
Fk + Fk = Fk+1 + Fk-2.(5)

Из (4), (5) вытекает следующая таблица "фибоначчиевого" сложения двух двоичных разрядов ak + bk с одним и тем же индексом k:

Таблица 2.
0+0=   0
0+1=   1
1+0=   1
1+1=   1 1 1 (a)
1+1=1 0 0 1 (b)
    В чем состоит особенность Табл. 2 в сравнении с Табл. 1? Мы видим, что три первые строки сравниваемых таблиц совпадают. Последние две строки Табл. 2 дают правило формирования переносов при "фибоначчиевом" сложении двоичных разрядов ak + bk = 1 + 1, которое имеет следующие особенности:
  1. При "фибоначчиевом" сложении 1 + 1 возникает перенос двух двоичных 1 из k-го разряда в следующие два разряда.
  2. Существует два метода формирования переносов при "фибоначчиевом" сложении. Для метода (a) двоичная 1 записывается в k-й разряд промежуточной суммы и возникает две единицы переноса в соседние младшие разряды, а именно - в (k - 1)-й и (k - 2)-й разряды. Метод (b) предполагает другое правило "фибоначчиевого" сложения двоичных разрядов 1 + 1. Двоичная цифра 0 записывается в k-й разряд промежуточной суммы и возникают два единичных переноса в соседние разряды, первый - в (k + 1)-й и второй - в (k - 2)-й разряды.
    "Фибоначчиевое" сложение многоразрядных чисел в коде Фибоначчи реализуется в соответствии с Табл. 2. Однако должны быть выполнены следующие правила:
  1. Перед "фибоначчиевым" сложением суммируемые "фибоначчиевые" представления приводятся к "минимальной" форме.
  2. В соответствии с Табл. 2 формируются многоразрядная промежуточная сумма и многоразрядный перенос.
  3. Многоразрядная промежуточная сумма приводится к "минимальной" форме и затем складывается с многоразрядным переносом.
  4. Процесс сложения продолжается в соответствии с правилами 2, 3 до получения нулевого переноса. Последняя промежуточная сумма, приведенная к "минимальной" форме, и есть результат сложения.
    Однако при "фибоначчиевом" сложении многоразрядных чисел необходимо выполнять следующее правило:
  1. Пусть мы имеем двоичные 1 в k-х разрядах суммируемых чисел, представленных в "минимальной" форме. Из свойства "минимальной" формы вытекает, двоичные цифры (k + 1)-го и (k - 1)-го разрядов обоих суммируемых "фибоначчиевых" представлений заведомо равны 0. Ясно, что для этого случая промежуточная сумма, возникающая при сложении (k + 1)-х и (k - 1)-х разрядов, заведомо равна 0. Это означает, что мы можем записать один из единичных переносов при сложении k-х разрядов (1 + 1) сразу же в (k - 1)-й разряд (метод (a) "фибоначчиевого" сложения) или в (k + 1)-й разряд (метод (b) "фибоначчиевого" сложения) промежуточной суммы.

Продемонстрируем рассмотренные выше правила "фибоначчиевого" сложения на следующем примере.

Пример 1. Сложить два числа 31 = 1 0 0 1 1 0 1 1 и 22 = 0 1 0 1 1 0 1 0, представленные в коде Фибоначчи.

Первый шаг состоит в приведении кодовых изображений к минимальной форме:

31 = 1 0 0 1 1 0 1 1 = 1 0 1 0 0 1 0 0,
22 = 0 1 0 1 1 0 1 0 = 0 1 1 0 0 0 1 0 = 1 0 0 0 0 0 1 0.

Второй шаг состоит в формировании многоразрядной промежуточной суммы S1 и многоразрядного переноса C1 в соответствии с методом (a) Табл. 1

31 = 1 0 1 0 0 1 0 0
+
22 = 1 0 0 0 0 0 1 0
---------------------
S1 = 1 1 1 0 0 1 1 0
C1 = 0 0 1 0 0 0 0 0

Заметим, что в этом случае ситуация 1 + 1 возникает для старших разрядов "фибоначчиевых" представлений. Эти разряды и возникающие при этом преобразования разрядов в промежуточной сумме S1 и промежуточном переносе C1 подчеркнуты.

Третий шаг состоит в приведении промежуточной суммы S1 к "минимальной" форме:

S1 = 0 1 1 1 0 0 1 1 0 = 1 0 0 1 0 1 0 0 0.

Четвертый шаг состоит в сложении S1 и C1:

S1 = 1 0 0 1 0 1 0 0 0
+
C1 = 0 0 0 1 0 0 0 0 0
-----------------------
S2 = 1 0 0 1 1 1 0 0 0
C2 = 0 0 0 0 0 1 0 0 0

Разряды 1 + 1 и возникающие в результате их сложения преобразования разрядов в S2 и C2 подчеркнуты.

Пятый шаг состоит в приведении промежуточной суммы S2 к "минимальной" форме:

S2 = 1 0 0 1 1 1 0 0 0 = 1 0 1 0 0 1 0 0 0.

Шестой шаг состоит в "фибоначчиевом" сложении S2 и C2:

S2 = 1 0 1 0 0 1 0 0 0
+
C2 = 0 0 0 0 0 1 0 0 0
-----------------------
S3 = 1 0 1 0 0 1 1 0 0
C3 = 0 0 0 0 0 0 0 1 0

Седьмой шаг есть приведение промежуточной суммы S3 к "минимальной" форме:

S3 = 1 0 1 0 0 1 1 0 0 = 1 0 1 0 1 0 0 0 0.

Восьмой шаг состоит в "фибоначчиевом" сложении S3 и C3:

S3 = 1 0 1 0 1 0 0 0 0
+
C3 = 0 0 0 0 0 0 0 1 0
-----------------------
S4 = 1 0 1 0 1 0 0 1 0
C4 = 0 0 0 0 0 0 0 0 0

"Фибоначчевое" сложение закончено, поскольку на восьмом шаге возникает 0-й перенос.

Хотя процедура "фибоначчиевого" сложения кажется сложной и утомительной, но это только на первый взгляд. После приобретения некоторого опыта эта процедура кажется не такой уж сложной! Мы приглашаем вас проделать некоторые примеры "фибоначчиевого" сложения. А сейчас мы переходим к другим арифметическим операциям, в частности к "фибоначчиевому" вычитанию. Следуйте за нами!