Фибонччи и компьютеры

Когда мы рассказывали о Фибоначчи, мы подчеркивали, что в своей знаменитой книге "Liber Abaci", опубликованной в 1202 г., он предложил и решил много новых комбинаторных задач. Наиболее известной из них является "задача о размножении кроликов", при решении которой он и пришел к знаменитой числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., прославившей его имя и ставшей объектом интенсивных математических исследований Фибоначчи Ассоциации

Следующая задача, рассмотренная Фибоначчи, называется "задачей о выборе наилучшей системы гирь для взвешивания на рычажных весах". Она также называется "задачей о гирях" или "задачей о взвешивании". История этой задачи такова. Из сочинений Фибоначчи она перекочевала в сочинения еще одного знаменитого итальянского математика Луки Пачиоли, который был "другом и советником Леонардо да Винчи". Лука Пачиоли поместил ее в свою книгу "Summa de Arithmetica, Geomeytria, Proprtioni et Proportionalita", которую он опубликовал в 1494 г. Эта книга по праву считается математической энциклопедией эпохи Возрождения.

В русской историко-математической литературе "задача о гирях" известна также под названием "задачи Баше-Менделеева". О Баше де Мизириаке мы уже рассказывали. Но кто такой Менделеев? Неужели знаменитый русский химик Дмитрий Менделеев, автор Периодического закона. Да, это именно так. Но почему русский химик вдруг заинтересовался "задачей о гирях"? Ответ на этот вопрос дает ознакомление с некоторыми малоизвестными фактами из жизни гениального русского ученого.

Во время происходивших в 1890 г. студенческих волнений в Петербургском университете Менделеев, который в тот период работал профессором этого университета, выступил на защиту студентов и в качестве протеста подал прошение об отставке с должности профессора университета. В 1892 г. Менделеев был назначен ученым хранителем Депо образцовых гирь и весов, которое по инициативе Менделеева в 1893 г. было преобразовано в Главную палату мер и весов России. Ее директором Менделеев оставался до конца жизни. Таким образом, заключительный этап жизни великого ученого (с 1992 г. и до 1907 г.) был связан с развитием измерительного дела и именно в этот период он заинтересовался "задачей о гирях". Под его непосредственным влиянием было выполнены исследования по этой проблеме и было доказано, что оптимальной является троичная система гирь.

Но теперь обратимся к новейшей истории современных компьютеров. В начале 60-х годов 20-го столетия на стыке измерительной и компьютерной техники возникла новая область - техника аналого-цифрового и цифро-аналогового преобразования информации. Основная задача этой техники состояла в создании устройств, обеспечивающих автоматическое преобразование информации из аналоговой, непрерывной формы в дискретную, цифровую форму. Такие устройства получили название непрерывно-дискретных, или аналого-цифровых преобразователей. Таким образом, основным назначением этих устройств является обеспечение связи компьютеров с объектами, в которых информация представлена в непрерывной, аналоговой форме.

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

В кандидатской диссертации Стахова, защищенной в 1966 г., а затем в докторской диссертации "Синтез оптимальных алгоритмов аналого-цифрового преобразования", защищенной в 1972 г., и были изложены результаты новой математической теории аналого-цифрового преобразования, получившей в дальнейшем название "алгоритмической теории измерения".

В 1957 г. американский математик Джордж Бергман ввел в рассмотрение позиционную систему специального типа, названную им "системой счислением с иррациональным основанием" или "Тау-системой". Хотя статья Бергмана содержала результат принципиального значения для теории систем счисления и современной компьютерной науки, однако в то период она просто не была замечена ни математиками, ни инженерами. Более того. И сам автор статьи Джордж Бергман не понял значения своего открытия для дальнейшего развития теории систем счисления и зарождающейся компьютерной техники. В заключение своей статьи он написал:

"Я не знаю никакого полезного приложения для систем счисления, подобных этой, как умственных упражнения и приятного времяпровождения, хотя эта система счисления может быть полезной для алгебраической теории чисел". Более чем 40 лет прошло с открытия Бергмана и, согласно "математической традиции", настало время по достоинству оценить математическое открытие Бергмана.

Удивительные свойства системы счисления Бергмана

Математическое выражение для системы счисления Бергмана имеет следующий вид:

г де A - некоторое действительное число и a_i - двоичные цифры, 0 или 1, i = 0, ±1, ±2, ±3, tⁱ - вес i-й цифры в системе счисления (1), t - основание системы счисления (1).

На первый взгляд, не существует никакой особенности в выражении (1) по сравнению с известными позиционными системами счисления, но это только на первый взгляд. Главная особенность состоит в том, что Бергман использовал иррациональное число

( "золотая пропорция") в качестве основания своей системы счисления (1), названной им "тау-системой".

Рассмотрим "тау-систему" с вычислительной точки зрения. Ее основание t определяет все необычные свойства системы счисления (1). Мы знаем из предыдущих страниц Музея, что "золотая пропорция" обладает следующим свойством:

t^n = t^n-1 + t^n-2.

(2)

Рассмотрим представления чисел в "тау-системе" (1). Ясно, что сокращенная запись числа A в "тау-системе" (1) имеет следующий вид:

A = anan-1 ... a1a0, a-1a-2 ... a-m.

(3)

Мы можем видеть, что сокращенная запись числа A представляет собой двоичную кодовую комбинацию, разделенную запятой на две части, левую часть a_na_n-1 ... a₁a₀, соответствующую "весам": tⁿ, t^n-1, ..., t¹, t⁰ = 1, и правую часть a_-1a_-2 ... a_-m, соответствующую "весам": t ^-1, t ^-2, ..., t ^-m. Заметим, что "веса" tⁱ (i =0, ±1, ±2, ±3, ...) задаются математической формулой (2).

Например, рассмотрим двоичную кодовую комбинацию 100101. Ясно, что она представляет собой следующее действительное число:

A = 100101 = t^5 + t^2 + t^0.

(4)

Используя формулу Бине, мы можем поучить, что число A, задаваемое выражением (4), равно:

Я сно, что основание "тау-системы" представляется в ней традиционным образом, то есть:

Н о из нашего предыдущего опыта мы знаем, что невозможно представить иррациональное число с использованием конечного числа цифр. Именно поэтому возможность представления некоторых иррациональных чисел (степеней "золотой пропорции" и их сумм) с использованием конечной совокупности двоичных цифр есть первый неожиданный результат "тау-системы", который противоречит нашим традиционным представлениям о системах счисления.

Возникает вопрос о представлении натуральных чисел в "тау-системе". Для этого рассмотрим еще раз фундаментальное тождество (2). На кодовом уровне оно имеет следующую кодовую интерпретацию:

100 = 011.

(5)

Как мы можем использовать кодовое преобразование (5)? Для этого мы рассмотрим "золотую" кодовую комбинацию 100101, которая представляет число (4). Если мы используем преобразование (7) к старшим трем разрядам "золотой" кодовой комбинации" 100101, мы получим новое "золотое" представление числа (4), а именно:

A = t⁵ + t² + t⁰ = 100101 = 011101 = t⁴ + t³ + t² + t⁰.

Заметим, что в этом случае степень "золотой пропорции" t⁵ заменятся на сумму двух предыдущих степеней t⁴ + t³ в соответствии с фундаментальным соотношением (2). Заметим также, что это не изменяет число (4). На кодовом уровне такое преобразование представляет собой следующее:

100 ® 011.

(6)

Это кодовое преобразование называется "разверткой". Обратное преобразование

011 ® 100.

(7)

называется "сверткой".

Таким образом, числа имеют многозначное представление в "тау-системе". Это - второй неожиданный результат, вытекающий из рассмотрения "тау-системы". Используя введенные выше преобразования "свертки" и "развертки", мы можем получить два крайних "золотых" представления одного и того же числа в "тау-системе". Например, рассмотрим кодовую комбинацию 0111111. Если мы выполним в ней все возможные "свертки" (7), то мы получим первое крайнее "золотое" представление, называемое "минимальной формой":

0111111 = 1001111 = 1010011 = 1010100 ("минимальная форма").

Заметим, что в "минимальной форме" двух единиц рядом не встречается.

Рассмотрим теперь "золотую" кодовую комбинацию 100000, которая представляет иррациональное число

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

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

Заметим, что в "максимальной форме" двух нулей рядом не встречается.

Покажем теперь, как можно получить все "золотые" представления натуральных чисел, используя операции "свертки" и "развертки". Начнем с числа 1. Оно может быть представлено через "золотую пропорцию" следующим способом:

1 = t⁰.

Но используя "тау-систему" (1), мы можем представить число t⁰ = 1 следующим образом:

1 = t^0 = 1,00.

(8)

Заметим, что в "золотом" представлении 1,00 запятая отделяет 0-й разряд от разрядов с отрицательными индексами.

Затем, используя "развертку", мы можем представить число (8) следующим образом:

t^0 = 1,00 = 0,11 = t^-1 + t^-2.

(9)

А теперь добавим бит 1 в 0-й разряд "золотого" представления 0,11. В результате мы получим "золотое" представление числа 2:

2 = 1,11.

(10)

Применяя операцию "свертки" к старшим разрядам "золотого" представления (10), мы получаем новое "золотое" представление ("минимальную форму") числа 2:

2 = 10,01 = t¹ + t ^-2.

Добавляя бит 1 в 0-1 разряд "золотого" представления числа 2, мы получаем "золотое" представление" числа 3:

3 = 11,01.

Применяя операцию "свертки" к старшим разрядам "золотого" представления числа 3, мы получаем новое "золотое" представление ("минимальную форму") числа 3:

2 = 100,01 = t² + t ^-2.

"Золотые" представления чисел 4 и 5 имеют следующий вид:

4 = 101,01 = t² + t⁰ + t ^-2; 5 = 1000,1001 = t³ + t ^-1 + t ^-4.

Продолжая этот процесс, можно получить "золотые" представления всех натуральных чисел в "тау-системе". Это означает, что любое натуральное число может быть всегда представлено в виде конечной суммы степеней золотой пропорции! Это утверждение представляет собой наиболее неожиданный результат, вытекающий из рассмотрения "тау-системы".

Основное преимущество кодов Фибоначчи и кодов золотой пропорции для практических применений состоит в их «естественной» избыточности, которая может использована для целей контроля числовых преобразований.