Фибоначчиева система счисления | это... Что такое Фибоначчиева система счисления? (original) (raw)
Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи 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 Литература
Представление натуральных чисел
Любое неотрицательное целое число можно единственным образом представить через последовательность битов …εk…ε4ε3ε2: , причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: . За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Обоснование
В основе лежит теорема Цекендорфа[1] — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
Доказательство существования легко провести по индукции. Любое целое число попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого верно неравенство: . Таким образом, , где , так что разложение числа уже не будет содержать слагаемого .
Использование
Юпана
Юпана
Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен[2].
В теории информации
На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системе счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:
ε2ε3…ε_n_1,
где 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] допускает разложение в ряд через отрицательные степени золотого сечения:
где {εk} обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с — золотым сечением отрезка [0,1], вычитанием (если εk=1) и умножением на . Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:
где N таково, что . Разумеется, следует считать что для всех .
Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца ) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[3]
Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.
Правила сложения аналогичны показанным выше с той поправкой, что перенос в сторону младших разрядов распространяется без ограничения. В данной системе счисления можно производить и умножение.
Фибоначчиево умножение
Для целых чисел и можно определить «умножение»[4]
которое аналогично умножению чисел в двоичной системе счисления.
Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой:[5]
где — целая часть, — золотое сечение.
Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут.[6] Следует отметить, что другое «произведение» отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.
Примечания
- ↑ Эдуард Цекендорф
- ↑ Antonio Aimi, Nicolino De Pasquale Andean Calculators. Проверено 12 декабря 2009.
- ↑ en:Golden ratio base (англ.)
- ↑ последовательность A101330 в OEIS, Zeckendorf's theorem (англ.)
- ↑ 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. — (Популярные лекции по математике).