Напечатать документ Послать нам письмо Сохранить документ Форумы сайта Вернуться к предыдущей
АКАДЕМИЯ ТРИНИТАРИЗМА На главную страницу
Институт Золотого Сечения - Под знаком "Золотого Сечения"

А.П. Стахов
Под знаком «Золотого Сечения»:
Исповедь сына студбатовца.
Глава 6. Драматическая история «компьютеров Фибоначчи»
6.1. История создания «фибоначчиевой» арифметики
Oб авторе
Мой вызов компьютерной технике

Как я рассказал выше, «алгоритмическая теория измерения» с большим интересом была воспринята научной общественностью, особенно специалистами в области метрологии, которые восприняли «алгоритмическую теорию измерения» как новое направление в «теоретической метрологии». Что касается специалистов в области аналого-цифровых преобразователей и вычислительной техники, то восприятие новых алгоритмов аналого-цифрового преобразования и вытекающих из них новых способов позиционного представления чисел было неоднозначным. Никто не отрицал оригинальности полученных результатов. Но когда дело доходило до практической реализации новых алгоритмов аналого-цифрового преобразования, то возникал вопрос: кому нужны аналого-цифровые преобразователи, на выходе которых информация представляется в форме, недоступной для восприятия современными «двоичными» компьютерами. Именно этот естественный вопрос и стал побудительной причиной для разработки машинной арифметики в новых кодах. Раз современные компьютеры не воспринимают информацию в новых кодах, то компьютерную технику просто надо переделать, то есть создать компьютеры, выполняющие операции в новых кодах. Таков был мой «вызов» компьютерной технике, поставленный мною перед собой сразу после защиты докторской диссертации в 1972 году.

Началом реализации «грандиозной», как мне тогда казалось, программы по исследованию новых компьютерных арифметик, вытекающих из «алгоритмической теории измерения», стали р-коды Фибоначчи, представляющие собой следующий позиционный способ представления натуральных чисел:
N = anFp(n) + an-1Fp(n-1) +... + aiFp(i) +... + a1Fp(1), (1)

где aiО {0, 1} – двоичная цифра i-го разряда позиционного представления (51); n – число двоичных разрядов позиционного представления (51); Fp(i) – вес i-го разряда, то есть р-число Фибоначчи, задаваемое рекуррентным соотношением (24), (25).

Представление Цекендорфа

Когда в конце 60-х годов мы с Игорем Витенько открыли «фибоначчиевые» алгоритмы измерения и затем я дал интерпретацию этих алгоритмов в виде формулы (1), то есть ввел понятие р-кода Фибоначчи, я не знал тогда, что у меня есть предшественник. Им оказался бельгийский врач и большой любитель математики Эдуард Цекендорф. Многие специалисты в области теории чисел знают так называемые суммы Цекендорфа, но мало кто знает о человеке, чьим именем названы эти суммы. Эдуард Цекендорф родился в Льеже, Бельгия, в 1901 г. В 1925 г. он закончил медицинский факультет Льежского университета и стал офицером бельгийской армии. В 1930 он также получил лицензию в области зубной хирургии.

Эдуард Цекендорф (1901-1983)

Математика была большим увлечением Цекендорфа. Несмотря на то, что Цекендорф не был профессиональным математиком, его математические работы в области чисел Фибоначчи высоко оцениваются математиками-фибоначчистами. В частности, Фибоначчи-Ассоциация признает его выдающимся математиком-фибоначчистом 20-го века. В 1939 г., то есть в год моего рождения, Цекендорф опубликовал статью, в которой были представлено исследование следующего способа представления натуральных чисел:
N = an Fn + an-1 Fn-1 +... + ai Fi +... + a1F1, (2)

где aiО {0, 1} – двоичная цифра i-го разряда представления; n – разрядность представления; Fi – число Фибоначчи, задаваемое с помощью рекуррентной формулы Фибоначчи:
Fi = Fi-1 + Fi-2; (3)
F1 = F2 = 1. (4)

Цифровая двоичная запись представления Цекендорфа имеет вид:
N = an an-1... ai... a1, (5)

где ai О {0,1} – бит i-го разряда представления (2).

Представление натуральных чисел в виде (2) называется кодом Цекендорфа, при этом имеется в виду прежде всего его цифровая запись (5), которая является двоичным представлением суммы (2). Таким образом, задолго до меня представление натуральных чисел с помощью чисел Фибоначчи было предложено Эдуардом Цекендорфом. Однако р-коды Фибоначчи, введенные мною, являются обобщением кода Цекендорфа (5) и включают его в качестве частного случая (р=1).

Эдуард Цекендорф был первым, кто обратил внимание на «избыточность» представления (2). Оно выражается в свойстве «многозначности» представления одного и того же натурального N в коде (2). Рассмотрим, например, представление в коде Цекендорфа числа Фибоначчи 34.

34

21

13

8

5

3

2

1

1

34 =

1

0

0

0

0

0

0

0

0

34 =

0

1

1

0

0

0

0

0

0

34 =

0

1

0

1

1

0

0

0

0

34 =

0

1

0

1

0

1

1

0

0

34 =

0

1

0

1

0

1

0

1

1


Все рассмотренные в таблице двоичные кодовые комбинации являются представлениями одного и того же натурального числа 34. При этом каждая последующая кодовая комбинация получается из предыдущей путем выполнения в ней специфической операции над тройкой соседних битов типа 100, которая заменяется на тройку битов 011. Такое преобразование (100 ® 011) я назвал «сверткой». Заметим, что операция «свертки» основывается на фундаментальном соотношении (3), связывающим веса соседних разрядов в коде (2), и поэтому выполнение этой операции в исходном кодовом представлении не изменяет изображаемого кодом числа. В коде Цекендорфа (2) можно выполнить операцию, обратную «свертке (011 ® 100); такую операцию я назвал «разверткой. Заметим, что операция «развертки», как и операция «свертки» не изменяют изображаемого кодом числа. Эти две операции были положены мною в качестве основных операций арифметики Фибоначчи. Если теперь выполнить над представлением Цекендорфа все возможные операции «свертки», то мы придем к особому представлению, называемому «минимальной формой»; ее характерная особенность состоит в том, что в ней двух 1 рядом не встречается. Если же в кодовой комбинации выполнить все возможные операции «развертки», то мы придем к представлению, называемому «максимальной формой»; в ней двух 0 рядом не встречается.

Связь с генетическим кодом

Позже я обнаружил любопытные закономерности, связывающие код Фибоначчи (вернее, код Цекендорфа) генетическим кодом. Для установления этих закономерностей рассмотрим 6-разрядный код Цекендорфа (2), в котором весами разрядов являются числа Фибоначчи 1, 1, 2, 3, 5, 8.
N = a6ґ 8 + a5ґ 5 + a4ґ 3 + a3ґ 2 + a2ґ 1 + a1ґ 1. (6)

Отметим следующие неожиданные аналогии между шестиразрядным кодом (6) и триплетным кодированием наследственной информации:

  1. Первая аналогия. Шестиразрядный двоичный код Фибоначчи использует для представления чисел 26 = 64 двоичных кодовых комбинаций от 000000 до 111111, что совпадает с числом триплетов генетического кода 43 = 64.
  2. Вторая аналогия. С помощью 6-разрядного кода Фибоначчи можно закодировать 21 целое число, начиная с числа 0, которое изображается с помощью 6-разрядной двоичной комбинации: 00000, и заканчивая максимальным числом 20, которое изображается с помощью 6-разрядной кодовой комбинации 111111. Заметим, что, используя триплетное кодирование, в генетическом коде также представляется 21 объект, включая 20 аминокислот и один дополнительный объект, стоп-кодон, несущий в себе информацию об окончании белкового синтеза.
  3. Третья аналогия. Как упоминалось, основной особенностью кода Цекендорфа (2) является множественность представления чисел. За исключением минимального числа 0 и максимального числа 20, которые имеют в коде Фибоначчи единственные представления (соответственно 000000 и 111111), все остальные числа от 1 до 19 имеют в коде Фибоначчи множественное представление, то есть используют не меньше двух кодовых представлений. Следует отметить, что в генетическом коде также используется свойство множественности представления, которое называется «вырожденностью» генетического кодирования.

Таким образом, между 6-разрядным кодом Цекендорфа и генетическим кодом, основанном на триплетном представлении аминокислот, существуют весьма интересные аналогии, которые среди остальных способов избыточного кодирования выделяют код Фибоначчи в особый способ кодирования, изучение которого может способствовать раскрытию особенностей генетического кодирования. Можно высказать предположение, что подобные аналогии могут стать весьма полезными при решении проблемы создания био-компьютеров, основанных на ДНК.

Первые шаги в создании арифметики Фибоначчи

Цекендорф, однако, не пытался создавать «арифметику Фибоначчи». Его она просто не интересовала. А меня интересовала именно «машинная арифметика Фибоначчи», на основе которой можно было бы разработать «компьютеры Фибоначчи».

Арифметика Фибоначчи была разработана мною в Таганроге, где я работал в тот период на должности зав. кафедрой информационно-измерительной техники Таганрогского радиотехнического института. Наиболее сложным было придумать правило «фибоначчиевого» сложения. При его разработке я использовал следующую аналогию. Как известно, при выполнении операции сложения над двумя классическими двоичными представлениями, мы используем следующее тождество для двоичных чисел:
2n +2n = 2n+1. (7)

Из тождества (7) вытекает широко известное правило формирования переноса единицы при сложении двух значащих разрядов 1+1: необходимо сформировать перенос единицы в старший, то есть (n+1)-й разряд, а в n-м разряде промежуточной суммы записать цифру 0. Это правило в настоящее время знает каждый школьник. Отсюда вытекает хорошо известная нам таблица сложения в двоичной системе счисления.

+

0

1

0

0

1

1

1

10


А как найти «правило переносов» при сложении чисел, представленных в коде Цекендорфа (2)? Очевидно, что мы должны проанализировать сумму двух чисел Фибоначчи:
Fn + Fn = Fn + Fn-1 + Fn-2 = Fn+1 + Fn-2. (8)

Как следует из (8), сумму Fn + Fn можно представить двумя способами: (а) как сумму трех чисел Фибоначчи Fn + Fn-1 + Fn-2 или (б) как сумму двух чисел Фибоначчи Fn+1 + Fn-2.

Первый вариант дает следующее «правило переносов» в коде Цекендорфа: при сложении двух значащих разрядов 1+1 в n-м разряде необходимо записать 1 в n-й разряд промежуточной суммы и сформировать единичные переносы в (n-1)-й и (n-2)-й разряды. Второе правило сложения, основанное на представлении суммы Fn + Fn в виде Fn+1 + Fn-2, гласит следующее: при сложении значащих разрядов 1+1 в n-м разряде необходимо записать 0 в n-й разряд промежуточной суммы и сформировать единичные переносы в (n+1)-й и (n-2)-й разряды. Заметим, что и в первом и во втором случае при «фибоначчиевом» сложении возникает два переноса из n-го разряда. Из проведенных рассуждений вытекает следующая таблица сложения в коде Цекендорфа.

+

0

1

0

0

1

1

1

111
1001

Однако, при сложении многоразрядных чисел такое правило формирования переноса может привести к тому, что в один и тот же разряд могут возникнуть два единичных переноса, то есть может произойти «наложение» переносов, что существенно усложняет процесс сложения. Мучительные размышления над разрешением этой проблемы привели меня к неожиданно простому решению. Идея пришла во сне в одну из душных ночей лета 1974 года. Я проснулся, разбудил жену, и она стала первым слушателем «арифметики Фибоначчи». Суть «фибоначчиевого» сложения состояла в том, что «фибоначчиевые» коды слагаемых чисел и все промежуточные суммы перед каждым шагом сложения должны приводиться к «минимальной форме». А поскольку в «минимальной форме» двух единиц рядом не встречается, то один из переносов из n-го разряда в ближайший, то есть (n+1)-й или (n-1)-й разряды, всегда может быть помещен в соответствующий разряд промежуточный суммы, и тогда при сложении необходимо запоминать только один перенос в (n-2)-й разряд. Незамедлительно вслед за этим возникла идея вычитания «фибоначчиевых» кодов с использованием понятий «обратного» и «дополнительного» кодов, что, однако, имеет свои особенности в коде Цекендорфа. Результаты разработки новой компьютерной арифметики был изложены мною в статье «Избыточные двоичные позиционные системы счисления», опубликованной в 1974 г. в одном из научных сборников Таганрогского радиотехнического института. Этой статье и суждено было стать первой в мире публикацией по арифметике Фибоначчи. Однако способы умножения и деления «фибоначчиевых» кодов, описанные в моей первой статье по арифметике Фибоначчи, все же оказались довольно сложными для технической реализации, и я продолжал поиск более эффективных алгоритмов выполнения арифметических операций.

Египетский метод удвоения

В этот период я серьезно увлекся историей математики. И однажды в одном из букинистических магазинов г. Москвы я купил замечательную книгу О. Нейгебауера «Лекции по истории античных математических наук». Том 1. Догреческая математика (Москва-Ленинград, 1937 г.). И когда я дошел до египетской математики, то я просто был ошарашен «гениальными» методами умножения и деления, которые использовали древнеегипетские математики. У древних египтян отсутствовала таблица умножения, и они сводили умножение (а также деление) к сложению с помощью хитроумной процедуры, основанной на «методе удвоения».

Для того, чтобы умножить, например, число 35 на 12, египетский математик поступал следующим образом. Он составлял таблицу. В первом столбце таблицы помещались двоичные числа 2k (k=0, 1, 3, …), во втором столбце первое число являлось одним из сомножителей (в данном случае 35), а каждое последующее число равнялось удвоенному предыдущему.

1

35

2

70

/4

140

®

140

/8

280

®

280

420


Затем наклонной чертой отмечались те двоичные числа первого столбца, сумма которых равна второму сомножителю (12=8+4). Результат умножения получался путем сложения чисел второго столбца, соответствующих числам левого столбца.

Анализ египетского метода умножения, основанного на «принципе удвоения», приводит нас к весьма неожиданному заключению. Используемое в первом столбце разложение целого числа по степеням двойки есть ни что иное, как его представление в двоичной системе счисления (12=1100). С другой стороны, если второй сомножитель 35 представить в двоичной системе счисления (35=100011), то используемое во втором столбце «удвоение» числа 35, осуществляемое на каждом шаге умножения, может быть осуществлено путем сдвига кода числа 35 на один разряд вправо (70=1000110, 140=110001100 и т. д.). Другими словами, рассмотренный выше египетский способ умножения путем «удвоения» по существу совпадает с основным алгоритмом умножения чисел в современных компьютерах!

Операция «удвоения» является основной и при делении целых чисел. Если, например, требовалось разделить число 30 на 6, то египетский вычислитель действовал следующим образом (см. таблицу).

/1

6Ј 30

6Ј 6

2

12Ј 30

12>6

/4

24Ј 30

8

48>30


В первый столбец записывались двоичные числа 2k (k=0, 1, 3, …), а в первой строке второго столбца записывался делитель 6 и каждое последующее число второго столбца затем удваивалось. На каждом шаге «удвоения» числа второго столбца сравнивались с делимым 30 до тех пор, пока очередное «удвоенное» число (в данном случае число 48 не оказывалось строго больше делимого: 48>30). После этого из делимого вычиталось «удвоенное» число предыдущего столбца (30-24=6), а в первом столбце отмечалось наклонной чертой «двоичное» число предыдущего столбца, то есть число 4. Затем с разностью (30-24=6) проделывалась та же процедура, что и во втором столбце, то есть делитель 6 и все «удвоенные» числа сравнивались с разностью 6 до тех пор, пока «удвоенное» число не оказывалось строго больше разности 6 (12>6). После отметки наклонной чертой числа 1 первого столбца и вычитания делителя 6 из разности 6 получалось число 0 (6-6=0) или число, меньшее делителя. На этом деление заканчивалось. Сумма «двоичных» чисел первого столбца, отмеченных наклонной чертой (4+1=5), и представляла собой результат деления.

Таким образом, нельзя не восхищаться гениальностью египетских математиков, которые много тысячелетий тому назад изобрели способы умножения и деления чисел, которые были использованы нами в современных компьютерах!

Методы умножения и деления чисел в арифметике Фибоначчи

Изучив древнеегипетские методы умножения и деления, я понял, что я нашел ключ для умножения и деления чисел в арифметике Фибоначчи. В качестве примера в таблице ниже рассмотрено умножение тех же чисел 35 на 12 в «фибоначчиевой» системе счисления.


1

35

¤ 1

35

®

35

2

70

¤ 3

105

®

105

5

175

¤ 8

280

®

280

12ґ 35

®

®

420


Заметим, что в первом столбце записаны числа Фибоначчи, а наклонной чертой в этом столбце отмечены те числа Фибоначчи, которые в сумме (1+3+8) равны первому сомножителю 12. В первой и второй строке второго столбца записывается второй сомножитель 35, а все последующие числа этого столбца формируются из числа 35 «по принципу Фибоначчи», то есть путем сложения двух предыдущих чисел. Если теперь из второго столбца выделить все числа (35, 105 и 280), соответствующие отмеченным числам первого столбца, то в сумме (480) они дадут значение искомого произведения 12ґ 35.

Любопытно отметить, что когда на основе рассмотренного выше алгоритма умножения было разработано «Устройство умножения в коде Фибоначчи» и на него было подана заявка на изобретение, то патентные ведомства всех стран, где это изобретение патентовалось, признали данное устройство «пионерным изобретением», то есть абсолютно новым устройством компьютерной техники, не имеющим аналога и прототипа! Этот пример показывает, как полезно иногда изучать историю математики, если, конечно, к этой истории подходить творчески.

Точно так же, использовав идею египетского метода деления, я пришел к методу деления чисел в арифметике Фибоначчи.

Вспоминаю, что примерно в 1975 или 1976 гг. я поделился своими результатами по разработке новой компьютерной арифметике с учеными кафедры истории математики Московского университета. И наибольший восторг у сотрудников кафедры вызвали именно методы «фибоначчиевого» умножения и деления, прообразом которых является египетский «метод удвоения».


А.П. Стахов, Под знаком «Золотого Сечения»: Исповедь сына студбатовца. Глава 6. Драматическая история «компьютеров Фибоначчи» 6.1. История создания «фибоначчиевой» арифметики // «Академия Тринитаризма», М., Эл № 77-6567, публ.13876, 11.10.2006

[Обсуждение на форуме «Наука»]

В начало документа

© Академия Тринитаризма
info@trinitas.ru