Фибоначчиева система счисления

Фибоначчиева система счисления — позиционная система счисления для целых чисел на основе чисел Фибоначчи F₂=1, F₃=2, F₄=3, F₅=5, F₆=8 и т.д.

Представление натуральных чисел

Число	Запись в ФСС	Код Фибоначчи
0	0……0
F2=1	1	11
F3=2	10	011
F4=3	100	0011
4	101	1011
F5=5	1000	00011
6	1001	10011
7	1010	01011
F6=8	10000	000011
…
Fn-1	101010…	…0101011
Fn	10……00	00……011
Fn+1	10……01	10……011

Любому неотрицательному целому числу $a = 0,\ 1,\ 2,\dots$ можно единственным образом представить через последовательность битов …ε_k…ε₄ε₃ε₂: $a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1$, причём последовательность {ε_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: $\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)$. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

В основе лежит теорема Цеккендорфа — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.

Доказательство существования легко провести по индукции. Любое целое число $a\ge 1$ попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого $n\ge 2$ верно неравенство: $F_n \le a < F_{n+1}$. Таким образом, $a = F_n + a'$, где $a'=a-F_n\$, так что разложение числа $a'$ уже не будет содержать слагаемого $F_{n-1}$.

Использование в теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу).

Обобщение на действительные числа

Похожее устройство имеет позиционная система счисления для действительных чисел, основанием которой служит золотое сечение $\varphi = (1 + \sqrt{5})/2$ — иррациональное число. Оказывается, что любое действительное число a из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения: $$a = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\ \varepsilon_k = 0,1\ ,$$ где {ε_k} обладает тем же свойством отсутствия соседних единиц. Из этого нетрудно видеть, что любое неотрицательное действительное число допускает разложение: $$a = \sum_{k=N-1}^{-\infty} \varepsilon_k \varphi^k\,,$$ где N таково, что $a < \varphi^N$. Разумеется, следует считать что $\varepsilon_k = 0$ для $k \ge N$.

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца ${\mathbb Z}+\varphi{\mathbb Z}$) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.

Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств: $$F_k = F_{k-1} + F_{k-2}\,,\ \varphi^k = \varphi^{k-1} + \varphi^{k-2}\,,$$ позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется. Шаблон:Section-stub

Фибоначчиево «произведение»

Для целых чисел $a = \sum_k \varepsilon_k F_k\$ и $b = \sum_l \zeta_l F_l\$ можно определить «произведение» $$a\circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l},$$ формула для которого аналогична формуле умножения двоичных чисел.

Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой: $$a\circ b = 3 a b - a [\varphi^{-2}(b+1)] - b [\varphi^{-2}(a+1)]\ ,$$где […] — целая часть.

Эта операция обладает ассоциативностью. Можно видеть, что формула «произведения» соответствует настоящему перемножению выражений вида $a = \sum_k \varepsilon_k \varphi^k\,,k=2, 3\dots$.

Впервые на ассоциативность этой операции обратил внимание Дональд Кнут. Следует отметить, что другое «произведение» $\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},$ отличающееся лишь сдвигом на два разряда, уже не будет ассоциативно, поскольку… Шаблон:Section-stub

Источники

• «Коды Фибоначчи», факультет информационных технологий и программирования ИТМО
• «Код Фибоначчи» на Викизнании