Основные операции над "фибоначчиевыми" представлениями

Раньше, когда мы рассмотрели "алгоритмическую теорию измерения", мы ввели понятие р-кодов Фибоначчи и показали, что эти коды являются обобщением понятия классического двоичного кода.

Очень важно использовать аналогию между классической двоичной системой и р-кодами Фибоначчи при создании "фибоначчиевой" арифметики. И поэтому мы будем использовать следующий метод для вывода арифметических правил "фибоначчиевой" арифметики. Сначала мы анализируем соответствующее правило для классической двоичной арифметики и затем мы "выводим" подобное правило для "фибоначчиевой" арифметики.

Мы начнем с самого простого "фибоначчиевого" представления, использующего классические числа Фибоначчи 1, 2, 3, 5, 8, 13, ... в качестве "весов" двоичных разрядов, то есть:

N = anFn + an-1Fn-1 + ... + aiFi + ... + a1F1(1)

Сначала мы рассмотрим ряд отличительных и очень важных операций "фибоначчиевой" арифметики, которые выполняются над "фибоначчиевыми" представлениями.

Главными операциями "фибоначчиевой" арифметики являются операции "свертки" и "развертки". Они основываются на основном рекуррентном соотношении Фибоначчи, связывающем "веса" фибоначчиевых разрядов в представлении (1):

Fi = Fi-1 + Fi-2,(2)
F1 = F2 = 1.(3)
    Это соотношение имеет следующую кодовую интерпретацию:
  1. "свертка": 011 ® 100;
  2. "развертка": 100 ® 011.

Это означает, что если мы можем выделить в "фибоначчиевом" представлении натурального числа N некоторую кодовую комбинацию 011 (или 100), то мы можем заменить ее на кодовую комбинацию 100 (или 011) без изменения изображаемого этим представлением числа.

Важными понятиями "фибоначчиевого" представления являются понятия "минимальной" и "максимальной" формы. Если мы выполним в некотором "фибоначчиевом" представлении все возможные операции "свертки", то мы придем к "минимальной" форме. Например,

0111011 0111 = 1001101001 = 1010001010 ("минимальная" форма).

В указанном выше примере все "свертки", последовательно выполняемые в "фоначчиевом" представлении, подчеркнуты.

В указанном примере правое кодовое представление является "минимальной" формой. Важное свойство "минимальной" формы состоит в том, что две двоичные единицы рядом в ней не встречаются.

Если теперь мы выполним в некотором "фибоначчиевом" представлении все возможные операции "развертки", то мы придем к "максимальной" форме. Например,

1000000 = 0110000 = 0101100 = 0101011 ("максимальная" форма).

В указанном выше примере все "развертки", последовательно выполняемые в "фибоначчиевом" представлении, подчеркнуты.

В указанном примере правое кодовое представление является "максимальной" формой. Важное свойство "максимальной" формы состоит в том, что два двоичных нуля рядом в ней не встречаются.

Напомним, что выполнение "сверток" и "разверток" в "фибоначчиевом" представлении, которое представляет некоторое натуральное число N, не изменяет числа N, изображаемого этим представлением.

А теперь мы продемонстрируем приложение этих основных операций "фибоначчиевой" арифметики для реализации простейших арифметических операций - "счет" и "вычитание" единиц. Эти арифметические операции определяют функционирование "фибоначчиевых" счетчиков.

Рассмотрим функционирование "фибоначчиевого" счетчика "суммирующего" типа:

0 = 000000 + 1
1 = 000001 = 000010 + 1
2 = 000011 = 000100 + 1
3 = 000101 = 000110 = 001000 + 1
4 = 001001 = 001010 + 1
5 = 001011 = 001100 = 010000 + 1
6 = 010001 = 010010 = 010010 + 1
7 = 010011 = 010100 + 1
8 = 010101 = 010110 = 011000 = 100000 + 1 и т.д.

Из этого примера мы видим, что функционирование "суммирующего" счетчика сводится к операции "свертки".

Рассмотрим теперь функционирование "фибоначчиевого" счетчика "вычитающего" типа:

5 = 10000 = 01100 = 01011 - 1
4 = 01010 = 01001 = 00111 -1
3 = 00110 = 00101 - 1
2 = 00100 = 00011 - 1
1 = 00010 = 00001 - 1
0 = 00000

Из этого примера мы видим, что функционирование "вычитающего" счетчика сводится к операции "развертки".

Сравнение "фибоначчиевых" чисел. Как известно, сравнение классических "двоичных" чисел, то есть чисел, представленных в двоичной системе счисления, осуществляется очень просто. Мы должны просмотреть сравниваемые кодовые комбинации A и B поразрядно, начиная со старшего разряда, до получения несовпадающих разрядов ak и bk. Если ak = 1 и bk = 0, это означает, что A > B.

Для "фибоначчиевых" кодовых комбинаций A и B процедура сравнения полностью совпадает с процедурой сравнения "двоичных" чисел. Однако до сравнения "фибоначчиевые" кодовые комбинации A и B должны быть приведены к "минимальной" форме.

В качестве примера сравним "фибоначчиевые" кодовые комбинации A = 01110110 и B = 01111001. Первый шаг состоит приведении "фибоначчиевых" представлений A и B к "минимальной" форме:

A = 01110110 = 10011000 = 10100000
B = 01111001 = 10011010 = 10100010

Сравнение "минимальных" форм A и B дает следующий результат: B > A.

Заметим, что впервые "фибоначчиева" арифметика изложена в статье А.П. Стахова "Избыточные позиционные системы счисления", опубликованной в научном сборнике "Однородные цифровые вычислительные и интегрирующие структуры" (Таганрогский радиотехнический институт, 1974 г.)

Научный сборник 'Однородные цифровые вычислительные и интегрирующие структуры' (Таганрогский радиотехнический институт, 1974 г.)Cтатья А.П. Стахова 'Избыточные позиционные системы счисления'

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

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

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