Алгоритм сложения целых чисел в ФСС

Перед сложением суммируемые фибоначчиевые числа приводятся к минимальной форме. Поразрядное сложение выполняется справа налево.

Будем использовать следующие обозначения:

S — промежуточная сумма;

R — многоразрядный перенос.

1. Выполним поразрядное сложение чисел в соответствии с табл. 6.

2. Промежуточная сумма S приводится к минимальной форме.

3. Если полученный многоразрядный перенос R равен 0, то переход на п. 6.

4. Выполняется сложение S + R, в результате которого формируется новое значение S и R.

5. Переход на п. 2.

Промежуточная сумма S, приведенная к минимальной форме, и есть результат сложения. Конец алгоритма.

Пример. Требуется сложить два числа a = 10101 _{fi b} и b = 1001 „ в ФСС.

В нашем примере числа уже записаны в минимальной форме, две единицы стоят только в первом разряде, поэтому многоразрядный перенос равен 0. В соответствии с табл. 6 получим:

+ 1001

S=11110

Результат приведем к минимальной форме, для этого дважды выполним операцию свертки: 11 110 => 100 11 0 => 101000.

Проверим себя, переведем исходные слагаемые и полученный результат в десятичную систему счисления:

85321 5321 1385321

a = 10101 = 12; b = 1001 = 6, S = 101000= 18.

Пример. Сложим десятичные числа A = 20₁₀ и B = 20₁₀ в фибоначчиевой системе счисления. Сначала запишем числа в ФСС в минимальной форме: A = B = 20₁₀ = 101010.

Операция сложения будет выполняться в несколько шагов. В этом примере две единицы стоят во втором, четвертом и шестом разрядах, но при сложении на первом шаге перенос будет возникать только для четвертого и шестого разрядов (см. табл. 6).

1)

+ 101010

S=101101

R=011110

Получили промежуточную сумму S = 101101 и многоразрядный перенос R = 011110.

2) Приведем S к минимальной форме: 101101 => 110001 => 1000001.

3) Вычислим S+R

+ 11110

S=1011111

Получили промежуточную сумму S=1011111 1011111 и нулевой многоразрядный перенос.

4) Запишем S в минимальной форме: 10 11 111 => 1100 11 1 => 11 01001 => 10001001.

Проверим себя:

34 21 13 8 5 3 2 1

1 0 0 0 1 0 0 1 = 34 + 5 + 1 = 40.

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

6.1. Реализация операции сложения в ФСС через базовые операции

Покажем, что через базовые операции { S, R, M, P } можно реализовать фибоначчиево сложение ячеек А и В. В основе этой реализации лежит идея перебрасывания единиц из k -го разряда ячейки А в k -й разряд ячейки В, если там был 0. При этом на каждом шаге сумма модифицированных ячеек остается прежней. Алгоритм заканчивается, когда ячейка А становится равной 0, в этом случае искомая сумма накоплена в ячейке В.

В качестве примера просуммируем два числа: A ₀ = 10100100 = 50₁₀ и B ₀ = 1010100 = 32₁₀

1-й шаг	Выполним операцию перемещения: (А 1, В 1) = М(А 0, В 0)	A0 = 010100100 | | B0 = 001010100 A1 = 000000100 B1 = 011110100
2-й шаг	Выполним все возможные операции развертки над А1: А2 = R(A 1)	A2 = 000000011
3-й шаг	Выполним все возможные свертки над В: B2= S(B 1)	B2 = 101000100
4-й шаг	Выполним операцию перемещения: (А 3, В 3) = M(A 2, B 2)	A2 = 000000011 || B2 = 101000100 A3 = 000000000 B3 = 101000111
5-й шаг	Приведем В 3 к минимальной форме, выполнив операцию свертки: В 4 = S(В 3)	B3 = 101001001

Проверим себя: В ₄ = 101001001 = 55 + 21 + 5 + 1 = 82₁₀.

Можно показать, что операции вычитания, умножения и деления также реализуются через базовые операции. Таким образом, через базовые операции { S, R, M, P } можно выразить любую логическую и любую арифметическую операцию. И, следовательно, мы можем проектировать Фибоначчи-процессор на основе базовых микроопераций.

Какое преимущество будет иметь такой фибоначчи-процессор в сравнении с классическими компьютерами, основанными на классической двоичной системе счисления?

Ответ на этот вопрос состоит в том, что такой процессор обладает возможностью контроля ошибок, которые могут возникнуть в процессоре под влиянием различных внешних и внутренних факторов [5].

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

Теоретические основы данного направления представляют несомненный интерес и могут стать источником новых идей не только в компьютерной области. Современные математики проявляют большой интерес к “фибоначчиеву” направлению. В 1963 г. группа американских математиков, возглавляемая Вернером Хоггаттом, организовала математическую фибоначчи-ассоциацию, которая выпускает журнал “The Fibonacci Quarterly” и ежегодно с 1984 г. проводит международную конференцию “Fibonacci Numbers and Their Applications”.