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