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

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

Число	Запись в Шаблон:Comment	Код Фибоначчи
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$ можно единственным образом представить последовательностью битов …ε_k…ε₄ε₃ε₂ (${\epsilon }_k\in \{0,1\}$) так, что $a=\sum _k{\epsilon }_k{F}_k$, причём последовательность {ε_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: $\mathrm{\forall }k\ge 2:({\epsilon }_k=1)\Rightarrow ({\epsilon }_{k+1}=0)$. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

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

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

Использование

Юпана

Юпана

Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен.

В теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1,Шаблон:Nbsp2,Шаблон:Nbsp3…), использующий последовательности битов. Поскольку комбинацияШаблон:Nbsp11 запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.

Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё разШаблон:Nbsp1 (см. таблицу). То есть, кодовая последовательность имеет вид:

ε₂ε₃…ε_n1,

где n — номер самого старшего разряда с единицей.

Арифметика

Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.

В фибоначчиевой системе счисления дело обстоит сложнее:

• Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε₁ и ε₀ следует помнить, что F₁=1=F₂ и F₀=0.
• Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.

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

Число	Представление через степениШаблон:Nbsp$\phi$
1	1
2	10,01
3	100,01
4	101,01
5	1000,1001
6	1010,0001
7	10000,0001
8	10001,0001
9	10010,0101
10	10100,0101
11	10101,0101
12	100000,101001
13	100010,001001
14	100100,001001

Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению $\phi =(1+\sqrt{5})/2$.

Любое вещественное число Шаблон:Math из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:

$x=\sum _{k=-1}^{-\mathrm{\infty }}{\epsilon }_k{\phi }^k,{\epsilon }_k\in \{0,1\}$

где $\left\{{\epsilon }_k\right\}$ обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением Шаблон:Math с ${\phi }^{-1}$ — золотым сечением отрезка [0,1], вычитанием ${\phi }^{-1}$ (если ${\epsilon }_k=1$) и умножением на $\phi$. Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:

$a=\sum _{k=N-1}^{-\mathrm{\infty }}{\epsilon }_k{\phi }^k,$

где Шаблон:Math таково, что $a<{\phi }^N$. При этом ${\epsilon }_k=0$ для всех $k⩾N$.

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

Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:

$F_k=F_{k-1}+F_{k-2}$

${\phi }^k={\phi }^{k-1}+{\phi }^{k-2}$

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

Правила сложения аналогичны показанным выше с той поправкой, что перенос в сторону младших разрядов распространяется без ограничения. В данной системе счисления можно производить и умножение.

Фибоначчиево умножение

Для целых чисел $a=\sum _k{\epsilon }_k{F}_k$ и $b=\sum _l{\zeta }_l{F}_l$ можно определить «умножение»

$a\circ b=\sum _{k,l}{\epsilon }_k{\zeta }_l{F}_{k+l},$

которое аналогично умножению чисел в двоичной системе счисления.

Эта операция не является настоящим умножением чисел, и выражается формулой:

$a\circ b=3ab-a\lfloor (b+1){\phi }^{-2}\rfloor -b\lfloor (a+1){\phi }^{-2}\rfloor ,$

где $\lfloor \cdot \rfloor$ — целая часть, $\phi =\frac{1+\sqrt{5}}{2}$ — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут. Другое «произведение» $\sum _{k,l}{\epsilon }_k{\zeta }_l{F}_{k+l-2},$ отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

Литература

• Шаблон:Книга

• Шаблон:Статья

• Стахов А., Слученкова А., Щербаков И. Код да Винчи и ряды Фибоначчи. СПБ. Издательство: Питер, 2006. 320 с. ISBN 5-469-01369-3
• Стахов А. П. Алгоритмическая теория измерения: новый подход к теории позиционных систем счисления и компьютерной арифметике// Журнал «Управляющие машины и системы», 1994, No 4-5.
• Стахов А. П. Компьютеры Фибоначчи и новая теория кодирования: история, теория, перспективы// Электронный журнал Таганрогского радиотехнического университета «Перспективные информационные технологии и интеллектуальные системы», № 2 (18), 2004// http://pitis.tsure.ru/files18/p5.pdf.