Фибоначчиева система счисления
Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=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 |
Представление натуральных чисел
Любое неотрицательное целое число [math]\displaystyle{ a }[/math] можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 ([math]\displaystyle{ \varepsilon_k \in \{ 0,1\} }[/math]) так, что [math]\displaystyle{ a = \sum_k \varepsilon_k F_k }[/math], причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: [math]\displaystyle{ \forall k\ge 2\colon (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0) }[/math]. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Обоснование
В основе лежит теорема Цекендорфа[1] — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора попарно различных чисел Фибоначчи с индексами, большими единицы, не содержащего пар соседних чисел Фибоначчи.
Доказательство существования легко провести по индукции. Любое целое число [math]\displaystyle{ a\ge 1 }[/math] попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого [math]\displaystyle{ n\ge 2 }[/math] верно неравенство: [math]\displaystyle{ F_n \le a \lt F_{n+1} }[/math]. Таким образом, [math]\displaystyle{ a = F_n + a' }[/math], где [math]\displaystyle{ a'=a-F_n\ \lt \ F_{n-1} }[/math], так что разложение числа [math]\displaystyle{ a' }[/math] уже не будет содержать слагаемого [math]\displaystyle{ F_{n-1} }[/math].
Использование
Юпана
Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен[2].
В теории информации
На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.
Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:
- ε2ε3…εn1,
где n — номер самого старшего разряда с единицей.
Арифметика
Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.
В фибоначчиевой системе счисления дело обстоит сложнее:
- Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=0.
- Во-вторых, требуется избавляться от соседних единиц: 011 = 100. Правило для раскрытия двоек является следствием этого равенства: 0200 = 0100 + 0011 = 0111 = 1001.
 | Этот раздел не завершён. |
Обобщение на вещественные числа
| Число | Представление через степени [math]\displaystyle{ \varphi }[/math] |
|---|---|
| 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 |
Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению [math]\displaystyle{ \varphi = (1 + \sqrt{5})/2 }[/math].
Любое вещественное число x из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:
- [math]\displaystyle{ x = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\qquad \varepsilon_k \in \{0,1\} }[/math]
где [math]\displaystyle{ \left\{ \varepsilon_k \right\} }[/math] обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с [math]\displaystyle{ \varphi^{-1} }[/math] — золотым сечением отрезка [0,1], вычитанием [math]\displaystyle{ \varphi^{-1} }[/math] (если [math]\displaystyle{ \varepsilon_k = 1 }[/math]) и умножением на [math]\displaystyle{ \varphi }[/math]. Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:
- [math]\displaystyle{ a = \sum_{k=N-1}^{-\infty} \varepsilon_k \varphi^k\,, }[/math]
где N таково, что [math]\displaystyle{ a \lt \varphi^N }[/math]. Разумеется, следует считать, что [math]\displaystyle{ \varepsilon_k = 0 }[/math] для всех [math]\displaystyle{ k \geqslant N }[/math].
Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца [math]\displaystyle{ {\mathbb Z}+\varphi{\mathbb Z} }[/math]) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[3]
Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
- [math]\displaystyle{ F_k = F_{k-1} + F_{k-2} }[/math]
- [math]\displaystyle{ \varphi^k = \varphi^{k-1} + \varphi^{k-2} }[/math]
позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.
Правила сложения аналогичны показанным выше с той поправкой, что перенос в сторону младших разрядов распространяется без ограничения. В данной системе счисления можно производить и умножение.
Фибоначчиево умножение
Для целых чисел [math]\displaystyle{ a = \sum_k \varepsilon_k F_k\ }[/math] и [math]\displaystyle{ b = \sum_l \zeta_l F_l\ }[/math] можно определить «умножение»[4]
- [math]\displaystyle{ a \circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l}, }[/math]
которое аналогично умножению чисел в двоичной системе счисления.
Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой:[5]
- [math]\displaystyle{ a\circ b = 3 a b - a \lfloor(b+1)\varphi^{-2}\rfloor - b \lfloor(a+1)\varphi^{-2}\rfloor, }[/math]
где [math]\displaystyle{ \lfloor\cdot\rfloor }[/math] — целая часть, [math]\displaystyle{ \varphi=\frac{1+\sqrt{5}}{2} }[/math] — золотое сечение.
Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут[6]. Другое «произведение» [math]\displaystyle{ \sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2}, }[/math] отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.
| Этот раздел не завершён. |
Примечания
- ↑ Эдуард Цекендорф (недоступная ссылка). Дата обращения: 27 января 2010. Архивировано 6 мая 2017 года.
- ↑ Antonio Aimi, Nicolino De Pasquale. Andean Calculators. Дата обращения: 12 декабря 2009.
- ↑ Система счисления на основе золотого сечения
- ↑ последовательность A101330 в OEIS (англ.), Теорема Цекендорфа
- ↑ Notes on the Fibonacci circle and arroba products (англ.)
- ↑ D. E. Knuth. Fibonacci multiplication (неопр.) // Applied Mathematics Letters. — 1988. — Т. 1, № 1. — С. 57—60. — doi:10.1016/0893-9659(88)90176-0.
Литература
- Воробьёв Н. Н. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
- Система счисления Фибоначчи, реализация на C++. — 2014. Архивировано 16 октября 2014 года.
- Стахов А., Слученкова А., Щербаков И. Код да Винчи и ряды Фибоначчи. СПБ. Издательство: Питер, 2006. 320 с. ISBN: 5-469-01369-3
- Стахов А.П. Алгоритмическая теория измерения: новый подход к теории позиционных систем счисления и компьютерной арифметике// Журнал «Управляющие машины и системы», 1994, No 4-5.
- Стахов А.П. Компьютеры Фибоначчи и новая теория кодирования: история, теория, перспективы// Электронный журнал Таганрогского радиотехнического университета «Перспективные информационные технологии и интеллектуальные системы», № 2 (18), 2004// http://pitis.tsure.ru/files18/p5.pdf.