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

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

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

Содержание

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

Любое неотрицательное целое число   можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 ( ) так, что  , причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц:  . За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

В основе лежит теорема Цекендорфа[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.

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

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

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

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

 

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

 

где N таково, что  . Разумеется, следует считать, что   для всех  .

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

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

 
 

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

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

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

Для целых чисел   и   можно определить «умножение»[4]

 

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

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

 

где   — целая часть,   — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут[6]. Следует отметить, что другое «произведение»   отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

Примечания

  1. Эдуард Цекендорф
  2. Antonio Aimi, Nicolino De Pasquale. Andean Calculators. Дата обращения 12 декабря 2009.
  3. Система счисления на основе золотого сечения[en]
  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.

Литература