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

'''[[Фибоначчи]]ева система счисления''' — [[позиционная система счисления]] для [[целое число|целых чисел]] на основе [[числа Фибоначчи|чисел Фибоначчи]] 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 cellpadding=6 style="margin-left: 20px"
 | colspan=3 |[[Image:Zeckendorf representations.png|320px]]
 |-
 !Число
 !Запись<br>в ФСС
 ![[#Использование в теории информации|Код<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>-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>+1
 |<tt>10</tt>……<tt>01</tt>
 | align=right |<tt>10</tt>……<tt>01<font color=#B20080>1</font></tt>
 |}

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

=== Обоснование ===
В основе лежит ''теорема [[Цеккендорф, Эдуар<!-- это не опечатка, имя французское! --Incnis Mrsi -->|Цеккендорфа]]'' — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.

Доказательство существования легко провести [[математическая индукция|по индукции]]. Любое целое число <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>.

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

{{section-stub}}

== Обобщение на действительные числа ==
Похожее устройство имеет позиционная система счисления для [[действительные числа|действительных чисел]], основанием которой служит [[золотое сечение]] <math>\varphi = (1 + \sqrt{5})/2</math> — [[иррациональное число]].
Оказывается, что любое действительное число ''x'' из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:
: <math>x = \sum_{k=-1}^{-\infty} \varepsilon_k \varphi^k,\ \varepsilon_k = 0,1\ ,</math>
где {ε<sub>k</sub>} обладает тем же свойством отсутствия соседних единиц.
Коэффициенты находятся последовательным сравнением ''x'' с <math>\varphi^{-1}</math> — золотым сечением отрезка [0,1], вычитанием <math>\varphi^{-1}</math> (если ε<sub>k</sub>=1) и умножением на <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>.

{| align=left class=standard style="margin-right: 20px"
|-
! Число
! Представление<br>через<br>степени&nbsp;<math>\varphi</math>
|-
|&nbsp;1
|<tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1,</tt>
|-
|&nbsp;2
|<tt>&nbsp;&nbsp;&nbsp;&nbsp;10,01</tt>
|-
|&nbsp;3
|<tt>&nbsp;&nbsp;&nbsp;100,01</tt>
|-
|&nbsp;4
|<tt>&nbsp;&nbsp;&nbsp;101,01</tt>
|-
|&nbsp;5
|<tt>&nbsp;&nbsp;1000,1001</tt>
|-
|&nbsp;6
|<tt>&nbsp;&nbsp;1010,0001</tt>
|-
|&nbsp;7
|<tt>&nbsp;10000,0001</tt>
|-
|&nbsp;8
|<tt>&nbsp;10001,0001</tt>
|-
|&nbsp;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>{\mathbb Z}+\varphi{\mathbb Z}</math>) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.<ref>[[:en:Golden ratio base]]{{ref-en}}<!-- тут хорошо бы найти настоящий источник --></ref>

Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
: <math>F_k = F_{k-1} + F_{k-2}\,,\ \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>{{OEIS2C|A101330}}, [[:en:Zeckendorf's theorem]]{{ref-en}}</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 [\varphi^{-2}(b+1)] -  b [\varphi^{-2}(a+1)]\ ,</math> где […] — [[целая часть]].

Эта операция обладает [[ассоциативность]]ю. <!--
 Доказательство не такое простое, тут надо думать.
 --Incnis Mrsi -->
Впервые на ассоциативность этой операции обратил внимание [[Дональд Кнут]]<ref> D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.</ref>.
Следует отметить, что другое «произведение» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> отличающееся лишь сдвигом на два разряда, уже не будет ассоциативно.
{{section-stub}}

== Источники ==
* [http://rain.ifmo.ru/cat/view.php/theory/coding/integer-2005#Fcode «Коды Фибоначчи»], факультет информационных технологий и программирования [[ИТМО]]
* [http://www.wikiznanie.ru/ru-wz/index.php/Код_Фибоначчи «Код Фибоначчи»] на Викизнании
{{примечания}}

[[Категория:Системы счисления]]
[[Категория:Золотое сечение]]
[[Категория:Сжатие данных]]

[[en:Fibonacci coding]]
[[eo:Vikipedio:Projekto matematiko/Fibonacci-a kodigo]]
[[fr:Codage de Fibonacci]]