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


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

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

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

Zeckendorf representations.png
Число Запись
в ФСС
Код
Фибоначчи
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

Содержание

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

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

Обоснование

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

Доказательство существования легко провести по индукции. Любое целое число a\ge 1 попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n\ge 2 верно неравенство: F_n \le 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 (см. таблицу). То есть, кодовая последовательность имеет вид:

ε2ε3…εn1,

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

Арифметика

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

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

  • Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0200 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1=1=F2 и F0=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\}

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

a = \sum_{k=N-1}^{-\infty} \varepsilon_k \varphi^k\,,

где N таково, что a < \varphi^N. Разумеется, следует считать что \varepsilon_k = 0 для всех k \ge 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 =  3 a b  -  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}, отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.


Примечания

  1. Эдуард Цекендорф
  2. Antonio Aimi, Nicolino De Pasquale Andean Calculators. Проверено 12 декабря 2009.
  3. en:Golden ratio base (англ.)
  4. последовательность A101330 в OEIS, Zeckendorf's theorem (англ.)
  5. Notes on the Fibonacci circle and arroba products (англ.)
  6. D. E. Knuth (1988). «Fibonacci multiplication». Applied Mathematics Letters 1 (1): 57-60. DOI:10.1016/0893-9659(88)90176-0.

Литература


Wikimedia Foundation. 2010.

См. также в других словарях:

  • Система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Троичная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Позиционная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Унарная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Двоичная система счисления — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей …   Википедия

  • Кириллическая система счисления — Башенные часы с кириллическими числами в Суздале …   Википедия

  • Шестидесятеричная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Двенадцатеричная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Вигезимальная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Двадцатеричная система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия