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

Разделы:

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

Число	Запись в ФСС	Код Фибоначчи

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

Содержание

1 Представление натуральных чисел
2 Обобщение на вещественные числа
3 Фибоначчиево умножение
4 Примечания
5 Литература

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

Любое неотрицательное целое число a{displaystyle a}

$a$ можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 (εk∈{0,1}{displaystyle varepsilon _{k}in {0,1}} $varepsilon _{k}in {0,1}$ ) так, что a=∑kεkFk{displaystyle a=sum _{k}varepsilon _{k}F_{k}} $a=sum _{k}varepsilon _{k}F_{k}$ , причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: ∀k≥2:(εk=1)⇒(εk+1=0){displaystyle forall kgeq 2:(varepsilon _{k}=1)Rightarrow (varepsilon _{k+1}=0)} $forall kgeq 2:(varepsilon _{k}=1)Rightarrow (varepsilon _{{k+1}}=0)$ .За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

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

Доказательство существования легко провести по индукции. Любое целое число a≥1{displaystyle ageq 1}

$ageq 1$ попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n≥2{displaystyle ngeq 2} $ngeq 2$ верно неравенство: Fn≤a<Fn+1{displaystyle F_{n}leq a<F_{n+1}} $F_{n}leq a<F_{{n+1}}$ . Таким образом, a=Fn+a′{displaystyle a=F_{n}+a’} $a=F_{n}+a'$ , где a′=a−Fn < Fn−1{displaystyle a’=a-F_{n} < F_{n-1}} $a'=a-F_{n} < F_{{n-1}}$ , так что разложение числа a′{displaystyle a’} $a'$ уже не будет содержать слагаемого Fn−1{displaystyle F_{n-1}} $F_{{n-1}}$ .

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

Юпана

Файл:Yupana 1.GIF Юпана

Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен[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.

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

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

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

Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению φ=(1+5)/2{displaystyle varphi =(1+{sqrt {5}})/2}

$varphi =(1+{sqrt {5}})/2$ .

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

x=∑k=−1−∞εkφk,εk∈{0,1}{displaystyle x=sum _{k=-1}^{-infty }varepsilon _{k}varphi ^{k},qquad varepsilon _{k}in {0,1}}

x=sum _{{k=-1}}^{{-infty }}varepsilon _{k}varphi ^{k},qquad varepsilon _{k}in {0,1}

где {εk}{displaystyle left{varepsilon _{k}right}}

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

a=∑k=N−1−∞εkφk,{displaystyle a=sum _{k=N-1}^{-infty }varepsilon _{k}varphi ^{k},,}

a=sum _{{k=N-1}}^{{-infty }}varepsilon _{k}varphi ^{k},,

где N таково, что a<φN{displaystyle a<varphi ^{N}}

$a<varphi ^{N}$ .Разумеется, следует считать, что εk=0{displaystyle varepsilon _{k}=0} $varepsilon _{k}=0$ для всех k≥N{displaystyle kgeq N} $kgeq N$ .

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями.Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца Z+φZ{displaystyle {mathbb {Z} }+varphi {mathbb {Z} }}

${{mathbb Z}}+varphi {{mathbb Z}}$ ) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[3]

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

Fk=Fk−1+Fk−2{displaystyle F_{k}=F_{k-1}+F_{k-2}}

F_{k}=F_{{k-1}}+F_{{k-2}}

φk=φk−1+φk−2{displaystyle varphi ^{k}=varphi ^{k-1}+varphi ^{k-2}}

varphi ^{k}=varphi ^{{k-1}}+varphi ^{{k-2}}

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

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

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

Для целых чисел a=∑kεkFk {displaystyle a=sum _{k}varepsilon _{k}F_{k} }

$a=sum _{k}varepsilon _{k}F_{k}$ и b=∑lζlFl {displaystyle b=sum _{l}zeta _{l}F_{l} } $b=sum _{l}zeta _{l}F_{l}$ можно определить «умножение»[4]

a∘b=∑k,lεkζlFk+l,{displaystyle acirc b=sum _{k,l}varepsilon _{k}zeta _{l}F_{k+l},}

acirc b=sum _{{k,l}}varepsilon _{k}zeta _{l}F_{{k+l}},

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

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

a∘b=3ab−a⌊(b+1)φ−2⌋−b⌊(a+1)φ−2⌋,{displaystyle acirc b=3ab-alfloor (b+1)varphi ^{-2}rfloor -blfloor (a+1)varphi ^{-2}rfloor ,}

acirc b=3ab-alfloor (b+1)varphi ^{{-2}}rfloor -blfloor (a+1)varphi ^{{-2}}rfloor ,

где ⌊⋅⌋{displaystyle lfloor cdot rfloor }

$lfloorcdotrfloor$ — целая часть, φ=1+52{displaystyle varphi ={frac {1+{sqrt {5}}}{2}}} $varphi ={frac {1+{sqrt {5}}}{2}}$ — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут [6]. Следует отметить, что другое «произведение» ∑k,lεkζlFk+l−2,{displaystyle sum _{k,l}varepsilon _{k}zeta _{l}F_{k+l-2},}

$sum _{{k,l}}varepsilon _{k}zeta _{l}F_{{k+l-2}},$ отличающееся лишь сдвигом на два разряда, уже не является

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Примечания

↑ Эдуард Цекендорф
↑ Antonio Aimi, Nicolino De Pasquale. Andean Calculators (неопр.). Дата обращения: 12 декабря 2009.
↑ Система счисления на основе золотого сечения [en]
↑ последовательность A101330 в OEIS (англ.), Теорема Цекендорфа ?!
↑ Notes on the Fibonacci circle and arroba products (англ.)
↑ D. E. Knuth (1988). “Fibonacci multiplication”. Applied Mathematics Letters. 1 (1): 57–60. DOI:10.1016/0893-9659(88)90176-0.

Литература

Воробьёв Н. Н. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).

Система счисления Фибоначчи, реализация на C++. — 2014.