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

Число	Запись в ФСС
0	0 …… 0
F 2 =1	1	1 1
F 3 =2	10	01 1
F 4 =3	100	001 1
4	101	101 1
F 5 =5	1000	0001 1
6	1001	1001 1
7	1010	0101 1
F 6 =8	10000	00001 1
…
F n − 1	101010 …	… 010101 1
F n	10 …… 00	00 …… 01 1
F n + 1	10 …… 01	10 …… 01 1

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

Любое неотрицательное целое число ${\displaystyle a}$ можно единственным образом представить последовательностью битов …ε _k …ε ₄ ε ₃ ε ₂ ( ${\displaystyle \varepsilon _{k}\in \{0,1\}}$ ) так, что ${\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}}$ , причём последовательность {ε _k } содержит лишь конечное число единиц, и не имеет пар соседних единиц: ${\displaystyle \forall k\geq 2\colon (\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)}$ . За исключением последнего свойства, данное представление аналогично двоичной системе счисления .

Обоснование

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

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

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

Юпана

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

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

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

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

ε ₂ ε ₃ …ε _n 1 ,

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

Арифметика

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

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

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

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

Число	Представление через степени ${\displaystyle \varphi }$
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

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

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

${\displaystyle x=\sum _{k=-1}^{-\infty }\varepsilon _{k}\varphi ^{k},\qquad \varepsilon _{k}\in \{0,1\}}$

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

${\displaystyle a=\sum _{k=N-1}^{-\infty }\varepsilon _{k}\varphi ^{k}\,,}$

где N таково, что ${\displaystyle a<\varphi ^{N}}$ . Разумеется, следует считать, что ${\displaystyle \varepsilon _{k}=0}$ для всех ${\displaystyle k\geqslant N}$ .

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

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

${\displaystyle F_{k}=F_{k-1}+F_{k-2}}$

${\displaystyle \varphi ^{k}=\varphi ^{k-1}+\varphi ^{k-2}}$

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

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

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

Для целых чисел ${\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}\ }$ и ${\displaystyle b=\sum _{l}\zeta _{l}F_{l}\ }$ можно определить «умножение»

${\displaystyle a\circ b=\sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l},}$

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

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

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

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

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

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

Примечания

Литература

• Воробьёв Н. Н. . — Наука, 1978. — Т. 39. — ( Популярные лекции по математике ).

• . — 2014. 16 октября 2014 года.

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