"Фибоначчиевое" вычитание

Как известно, "двоичное" вычитание является арифметической операцией более сложной, чем "двоичное" сложение. Существует два варианта "двоичного" вычитания: (1) "прямое" вычитание; (2) вычитание, основанное на применении специального кодирования отрицательных чисел ("инверсный" и "дополнительный" коды).

Метод "прямого" вычитания основан на следующем свойстве "двоичных" чисел:

2n+k - 2n = 2n+k-1 + 2n+k-2 + ... + 2n.(1)

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

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

Запишем следующее тождество для чисел Фибоначчи:

Fn+k - Fn = Fn+k-2 + Fn+k-3 + ... + Fn-1.(2)

Мы видим, что тождество (2) подобно тождеству (1). Тогда, используя тождество (2), мы можем "сконструировать" следующую таблицу "фибоначчиевого" вычитания:

Таблица 2.
0-0=   0
1-1=   0
1-0=   0 1 1
1 0-1=   0 1
1 0 0-1=   1 1
1 0 0 0-1=1 1 1
    "Прямое" вычитание многоразрядных "фибоначчиевых" кодовых комбинаций А и В осуществляется согласно следующим правилам:
  1. Кодовые комбинации приводятся к "минимальной" форме.
  2. Кодовые комбинации, приведенные к "минимальной" форме, сравниваются по величине и затем меньшее число вычитается из большего в соответствии с Табл.2.

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

Книга А.П.Стахова 'Введение в алгоритмическую теорию измерения' (1977г.)Книга А.П.Стахова 'Коды золотой пропорции' (1984 г.)