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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т. д.

Файл:Zeckendorf representations.svg
Число Запись
в Шаблон:Comment 		Код
Фибоначчи
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>a</math> можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 (<math>\varepsilon_k \in \{ 0,1\}</math>) так, что <math>a = \sum_k \varepsilon_k F_k</math>, причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <math>\forall k\ge 2\colon (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</math>. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

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

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

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

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

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

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

ε2ε3…εn1,

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

Арифметика

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

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

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

Шаблон:Заготовка раздела

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

Число Представление
через степениШаблон:Nbsp<math>\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>\varphi = (1 + \sqrt{5})/2</math>.

Любое вещественное число Шаблон:Math из отрезка [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 с <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>

где Шаблон:Math таково, что <math>a < \varphi^N</math>. Разумеется, следует считать, что <math>\varepsilon_k = 0</math> для всех <math>k \geqslant N</math>.

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

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

<math>F_k = F_{k-1} + F_{k-2}</math>
<math>\varphi^k = \varphi^{k-1} + \varphi^{k-2}</math>

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

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

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

Для целых чисел <math>a = \sum_k \varepsilon_k F_k\ </math> и <math>b = \sum_l \zeta_l F_l\ </math> можно определить «умножение»[4]

<math>a \circ b = \sum_{k,l} \varepsilon_k \zeta_l F_{k+l},</math>

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

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

<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> — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут[6]. Другое «произведение» <math>\sum_{k,l} \varepsilon_k \zeta_l F_{k+l-2},</math> отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

Шаблон:Заготовка раздела

Примечания

Шаблон:Примечания

Литература

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

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Iw
  4. ↑ Шаблон:OEISШаблон:Ref-en, Теорема Цекендорфа
  5. ↑ Notes on the Fibonacci circle and arroba productsШаблон:Ref-en
  6. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Фибоначчиева_система_счисления&oldid=11155619