Редактирование: Фибоначчиева система счисления

'''[[Фибоначчи]]ева система счисления''' — [[смешанная система счисления]] для [[целое число|целых чисел]] на основе [[числа Фибоначчи|чисел Фибоначчи]] F<sub>2</sub>=1, F<sub>3</sub>=2, F<sub>4</sub>=3, F<sub>5</sub>=5, F<sub>6</sub>=8 и т. д.
{| align=right class=standard style="margin-left: 20px"
 | colspan=3 |[[Файл:Zeckendorf representations.png|320px]]
 |-
 !Число
 !Запись<br />в {{comment|ФСС|Фибоначчиева система счисления}}
 ![[#В теории информации|Код<br />Фибоначчи]]
 |-
 | align=right |0
 | align=right |<tt>0</tt>……<tt>0</tt>
 | bgcolor=#999999 |&nbsp;
 |-
 | align=right |F<sub>2</sub>=1
 | align=right |<tt>1</tt>
 | align=left |<tt>1<font color=#B20080>1</font></tt>
 |-
 | align=right |F<sub>3</sub>=2
 | align=right |<tt>10</tt>
 | align=left |<tt>01<font color=#B20080>1</font></tt>
 |-
 | align=right |F<sub>4</sub>=3
 | align=right |<tt>100</tt>
 | align=left |<tt>001<font color=#B20080>1</font></tt>
 |-
 | align=right |4
 | align=right |<tt>101</tt>
 | align=left |<tt>101<font color=#B20080>1</font></tt>
 |-
 | align=right |F<sub>5</sub>=5
 | align=right |<tt>1000</tt>
 | align=left |<tt>0001<font color=#B20080>1</font></tt>
 |-
 | align=right |6
 | align=right |<tt>1001</tt>
 | align=left |<tt>1001<font color=#B20080>1</font></tt>
 |-
 | align=right |7
 | align=right |<tt>1010</tt>
 | align=left |<tt>0101<font color=#B20080>1</font></tt>
 |-
 | align=right |F<sub>6</sub>=8
 | align=right |<tt>10000</tt>
 | align=left |<tt>00001<font color=#B20080>1</font></tt>
 |-
 | colspan=3 align=center |…
 |-
 |F<sub>n</sub>&nbsp;−&nbsp;1
 |<tt>&nbsp;101010</tt>…
 | align=right |…<tt>010101<font color=#B20080>1</font>&nbsp;</tt>
 |-
 |F<sub>n</sub>
 |<tt>10</tt>……<tt>00</tt>
 | align=right |<tt>00</tt>……<tt>01<font color=#B20080>1</font></tt>
 |-
 |F<sub>n</sub>&nbsp;+&nbsp;1
 |<tt>10</tt>……<tt>01</tt>
 | align=right |<tt>10</tt>……<tt>01<font color=#B20080>1</font></tt>
 |}

== Представление натуральных чисел ==
Любое неотрицательное целое число <math>a</math> можно единственным образом представить последовательностью [[бит]]ов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub> (<math>\varepsilon_k \in \{ 0,1\}</math>) так, что <math>a = \sum_k \varepsilon_k F_k</math>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>.
За исключением последнего свойства, данное представление аналогично [[двоичная система счисления|двоичной системе счисления]].

=== Обоснование ===
В основе лежит ''теорема [[Цекендорф, Эдуард|Цекендорфа]]''<ref>[http://www.goldenmuseum.com/1601Mathematics_rus.html Эдуард Цекендорф]</ref> — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора чисел Фибоначчи с индексами больше единицы, не содержащего пар соседних чисел Фибоначчи.

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

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

==== Юпана ====
[[Файл:Yupana 1.GIF|thumb|Юпана]]
Предполагают, что некоторые разновидности [[Юпана|юпаны]] ([[абак]]а [[инки|инков]]) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен<ref>{{cite web|author=Antonio Aimi, Nicolino De Pasquale|url=http://web.archive.org/web/*/http://www.quipus.it/english/Andean%20Calculators.pdf|title=Andean Calculators|accessdate=2009-12-12}}</ref>.

==== В теории информации ====
На основе фибоначчиевой системы счисления строится ''код (кодирование) Фибоначчи'' — [[универсальный код]] для натуральных чисел (1,{{nbsp|1}}2,{{nbsp|1}}3…), использующий последовательности [[бит]]ов. Поскольку комбинация{{nbsp|1}}<tt>11</tt> запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.

Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз{{nbsp|1}}<tt>1</tt> (см. таблицу). То есть, кодовая последовательность имеет вид:
: ε<sub>2</sub>ε<sub>3</sub>…ε<sub>''n''</sub><font color=#B20080>1</font>,
где ''n'' — номер самого старшего разряда с единицей.

=== Арифметика ===
Сложение чисел в [[позиционная система счисления|позиционных системах счисления]] выполняется с использованием [[перенос (арифметика)|переноса]], позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: <span style="background-color: rgb(255,255,51)">01</span> + <span style="background-color: rgb(255,255,51)">01</span> = <span style="background-color: rgb(255,255,51)">0<font color=red>2</font></span> = <span style="background-color: rgb(255,255,51)">10</span>.

В фибоначчиевой системе счисления дело обстоит сложнее:
* Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: <span style="background-color: rgb(102,255,51)">0<font color=red>2</font>00</span> = <span style="background-color: rgb(102,255,51)">1001</span>. При переносе в отсутствующие разряды ε<sub>1</sub> и ε<sub>0</sub> следует помнить, что F<sub>1</sub>=1=F<sub>2</sub> и F<sub>0</sub>=0.
* Во-вторых, требуется избавляться от соседних единиц: <span style="background-color: rgb(102,255,51)">0<font color=red>11</font></span> = <span style="background-color: rgb(102,255,51)">100</span>. Правило для раскрытия двоек является следствием этого равенства: <span style="background-color: rgb(102,255,51)">0<font color=red>2</font>00</span> = <span style="background-color: rgb(102,255,51)">0100</span> + <span style="background-color: rgb(102,255,51)">00<font color=red>11</font></span> = <span style="background-color: rgb(102,255,51)">0<font color=red>11</font>1</span> = <span style="background-color: rgb(102,255,51)">1001</span>.
{{заготовка раздела}}

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

{| align=right class=standard style="margin-right: 20px"
|-
! Число
! Представление<br />через степени{{nbsp|1}}<math>\varphi</math>
|-
| 1
|<tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1</tt>
|-
| 2
|<tt>&nbsp;&nbsp;&nbsp;&nbsp;10,01</tt>
|-
| 3
|<tt>&nbsp;&nbsp;&nbsp;100,01</tt>
|-
| 4
|<tt>&nbsp;&nbsp;&nbsp;101,01</tt>
|-
| 5
|<tt>&nbsp;&nbsp;1000,1001</tt>
|-
| 6
|<tt>&nbsp;&nbsp;1010,0001</tt>
|-
| 7
|<tt>&nbsp;10000,0001</tt>
|-
| 8
|<tt>&nbsp;10001,0001</tt>
|-
| 9
|<tt>&nbsp;10010,0101</tt>
|-
|10
|<tt>&nbsp;10100,0101</tt>
|-
|11
|<tt>&nbsp;10101,0101</tt>
|-
|12
|<tt>100000,101001</tt>
|-
|13
|<tt>100010,001001</tt>
|-
|14
|<tt>100100,001001</tt>
|}

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

Любое [[вещественное число]] {{math|''x''}} из отрезка [0,1] допускает разложение в [[степенной ряд|ряд]] через отрицательные степени золотого сечения:
: <math>x = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\qquad \varepsilon_k \in \{0,1\}</math>
где <math>\left\{ \varepsilon_k \right\}</math> обладает тем же свойством отсутствия соседних единиц.
Коэффициенты находятся последовательным сравнением {{math|''x''}} с <math>\varphi^{-1}</math> — золотым сечением отрезка [0,1], вычитанием <math>\varphi^{-1}</math> (если <math>\varepsilon_k = 1</math>) и умножением на <math>\varphi</math>.
Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:
: <math>a = \sum_{k=N-1}^{-\infty} \varepsilon_k \varphi^k\,,</math>
где ''N'' таково, что <math>a < \varphi^N</math>.
Разумеется, следует считать, что <math>\varepsilon_k = 0</math> для всех <math>k \ge N</math>.

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями.
Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент [[Кольцо (математика)|кольца]] <math>{\mathbb Z}+\varphi{\mathbb Z}</math>) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.<ref>{{iw|Система счисления на основе золотого сечения|||Golden ratio base}}<!-- тут хорошо бы найти настоящий источник --></ref>

Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
: <math>F_k = F_{k-1} + F_{k-2}</math>
: <math>\varphi^k = \varphi^{k-1} + \varphi^{k-2}</math>
позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.<!--
 Тут надо уточнить, на самом деле связь будет с некоторыми оговорками и с точностью до множителя √5 или что-то такое.
 Думаю, что должна быть связь с формулой секцией ниже, поскольку то умножение действует по той же логике, что и перемножение чисел в Φ-системе. 
 --Incnis Mrsi -->

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

== Фибоначчиево умножение ==
Для целых чисел <math>a = \sum_k \varepsilon_k F_k\ </math> и <math>b = \sum_l \zeta_l F_l\ </math> можно определить «умножение»<ref>{{OEIS|A101330}}{{ref-en}}, {{iw|Теорема Цекендорфа|||Zeckendorf’s theorem}}</ref>
: <math>a \circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l},</math>
которое аналогично умножению чисел в [[двоичная система счисления|двоичной системе счисления]].

Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой:<ref>[http://www.research.att.com/~njas/sequences/a101330.txt Notes on the Fibonacci circle and arroba products]{{ref-en}}</ref>
: <math>a\circ b =  3 a b  -  a \lfloor(b+1)\varphi^{-2}\rfloor -  b \lfloor(a+1)\varphi^{-2}\rfloor,</math>
где <math>\lfloor\cdot\rfloor</math> — [[целая часть]], <math>\varphi=\frac{1+\sqrt{5}}{2}</math> — [[золотое сечение]].

Эта операция обладает [[Ассоциативная операция|ассоциативностью]], на что впервые обратил внимание [[Кнут, Дональд Эрвин|Дональд Кнут]]<ref>{{cite journal |author=D. E. Knuth |title=Fibonacci multiplication |journal=Applied Mathematics Letters |volume=1 |issue=1 |year=1988 |pages=57-60 |doi=10.1016/0893-9659(88)90176-0}}</ref>. Следует отметить, что другое «произведение» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> отличающееся лишь сдвигом на два разряда, уже не является

{{заготовка раздела}}

== Примечания ==
{{примечания|2}}

== Литература ==
* {{книга
|автор        = Воробьёв&nbsp;Н.&nbsp;Н.
|заглавие     = Числа Фибоначчи
|серия        = [[Популярные лекции по математике]]
|издательство = Наука
|том          =  39
|год          = 1978
|ссылка       = http://ilib.mccme.ru/plm/ann/a06.htm
}}

* {{статья
|заглавие     = Система счисления Фибоначчи, реализация на C++
|год          = 2014
|ссылка       = http://www.moveinfo.ru/article/stablelink?page=0000041
}}
[[Категория:Системы счисления]]
[[Категория:Золотое сечение]]
[[Категория:Сжатие данных]]