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

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

Число	Запись в ФСС	Код Фибоначчи

0	`0`……`0`
F₂=1	`1`	`11`
F₃=2	`10`	`011`
F₄=3	`100`	`0011`
4	`101`	`1011`
F₅=5	`1000`	`00011`
6	`1001`	`10011`
7	`1010`	`01011`
F₆=8	`10000`	`000011`
…
F_n − 1	`101010`…	…`0101011`
F_n	`10`……`00`	`00`……`011`
F_n + 1	`10`……`01`	`10`……`011`

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

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

Обоснование

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

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

Юпана

Юпана

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

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

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

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

ε₂ε₃…ε_n1,

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

Арифметика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Эдуард Цекендорф (неопр.) (недоступная ссылка). Дата обращения: 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Эдуард Цекендорф (неопр.) (недоступная ссылка). Дата обращения: 27 января 2010. Архивировано 6 мая 2017 года.

[2] Antonio Aimi, Nicolino De Pasquale. Andean Calculators (неопр.). Дата обращения: 12 декабря 2009.

[3] Система счисления на основе золотого сечения

[4] последовательность A101330 в OEIS (англ.), Теорема Цекендорфа

[5] Notes on the Fibonacci circle and arroba products (англ.)

[6] D. E. Knuth. Fibonacci multiplication (неопр.) // Applied Mathematics Letters. — 1988. — Т. 1, № 1. — С. 57—60. — doi:10.1016/0893-9659(88)90176-0.