Коды Фибоначчи

Одним из наиболее неожиданных результатов "алгоритмической теории измерения" являются "фибоначчиевые" алгоритмы измерения. Эти алгоритмы имеют следующую числовую интерпретацию:

N = anFp(n) + an-1Fp(n - 1) + ... + aiFp(i) + ... + a1Fp(1),(1)

где ai Î {0, 1} - двоичная цифра i-го разряда кода (1); n - разрядность кода (1); Fp(i) - вес -го разряда, вычисляемый в соответствии со следующим рекуррентным соотношением:

Fp(i) = Fp(i - 1) + Fp(i - p - 1) with i > p + 1;(2)
Fp(1) = Fp(2) = ... = Fp(p + 1) = 1.(3)

Позиционное представление натурального числа N в виде (1) называется р-кодом Фибоначчи числа N. Сокращенная запись суммы (1) имеет следующий вид:

N = an an-1 ... a1.(4)

Заметим, что понятие p-кода Фибоначчи включает в себя бесконечное число различных методов позиционного представления, потому что каждое p "порождает" свой собственный p-код Фибоначчи (p = 0, 1, 2, 3, ...).

Пусть p = 0. Для этого случая 0-числа Фибоначчи F0(i) совпадают с "двоичными" числами, то есть

F0(i) = 2i-1.

Представление (1) для этого случая принимает следующую хорошо известную форму:

N = an2n-1 + an-12n-2 + ... + ai2i-1 + ... + a120.(5)

Пусть p = ¥. В этом случае p-числа Фибоначчи равны 1, то есть мы имеем для любого i:

Fp(i) = 1.

Тогда представление (1) принимает следующий вид:

(6)

Таким образом p-коды Фибоначчи являются весьма широким обобщением "двоичного" кода (5) и включают его в качестве частного случая, соответствующего p = 0. С другой стороны, p-коды Фибоначчи включают в себя так называемый "унитарный" код (6), соответствующий другому крайнему значению p = ¥.

Но как получить "фибоначчиевое" представление некоторого натурального числа, например числа 30. Для этого запишем числа Фибоначчи в обратном порядке:

34, 21, 13, 8, 5, 3, 2, 1, 1.

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

 342113853211
30010100010

Сравним число 30 с числом Фибоначчи 34; так как 30 < 34, мы записываем 0 во второй строке и втором столбце таблицы. Затем мы сравниваем число 30 со следующим числом Фибоначчи 21. Так как 30 ³ 21, мы записываем 1 во второй строке под числом 21. После этого мы образуем разность 30 - 21 = 9 и затем сравниваем число 9 со следующими числами Фибоначчи 13, 8, ..., 2, 1, 1. В результате этой процедуры мы получаем следующее "фибоначчиевое" представление числа 30:

30 = 0 1 0 1 0 0 0 1 0.

Это позиционное представление есть ни что иное, как сокращенная запись следующей суммы:

30 = 21 + 8 + 1.

Таким образом, "алгоритмическая теория измерения" привела нас к небольшому математическому открытию в области теории систем счисления. Мы получили обобщение "двоичной" системы счисления! Благодаря этому открытию мы теперь знаем, что существует бесконечное число "двоичных" позиционных представлений, которые задаются некоторой общей формулой (1)! И классическая "двоичная" система счисления (5) является всего лишь частным случаем "фибоначчиевого" представления (1).

Но "двоичная" система счисления (5) является основой современных компьютеров! Но тогда возникает вопрос: если мы будем использовать "фибоначчиевые" представления (1) в компьютерах, то возможно мы сможем прийти к новым компьютерам, Фибоначчи-компьютерам, как новой идеи в развитии компьютерной техники? И мы расскажем о развитии этой весьма интересной идеи на следующих страницах нашего Музея. Следуйте за нами!