Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи 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
Представление натуральных чисел Любое неотрицательное целое число можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 () так, что , причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: . За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Обоснование В основе лежит теорема Цекендорфа — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора попарно различных чисел Фибоначчи с индексами, большими единицы, не содержащего пар соседних чисел Фибоначчи.
Доказательство существования легко провести по индукции. Любое целое число попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого верно неравенство: . Таким образом, , где , так что разложение числа уже не будет содержать слагаемого .
Использование
Юпана
Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен.
В теории информации На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (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,010110 10100,010111 10101,010112100000,10100113100010,00100114100100,001001
Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению .
Любое вещественное число из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:
где обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением с — золотым сечением отрезка [0,1], вычитанием (если ) и умножением на . Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:
где таково, что . При этом для всех .
Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца ) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.
Аналогия между числами Фибоначчи и степенями золотого сечения основана на одинаковой форме тождеств:
позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.
Правила сложения аналогичны показанным выше с той поправкой, что перенос в сторону младших разрядов распространяется без ограничения. В данной системе счисления можно производить и умножение.
Фибоначчиево умножение Для целых чисел и можно определить «умножение», Теорема Цекендорфа
которое аналогично умножению чисел в двоичной системе счисления.
Эта операция не является настоящим умножением чисел, и выражается формулой:Notes on the Fibonacci circle and arroba products
где — целая часть, — золотое сечение.
Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут. Другое «произведение» отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.
Примечания
Литература
Стахов А., Слученкова А., Щербаков И. Код да Винчи и ряды Фибоначчи. СПБ. Издательство: Питер, 2006. 320 с. ISBN 5-469-01369-3 Стахов А. П. Алгоритмическая теория измерения: новый подход к теории позиционных систем счисления и компьютерной арифметике// Журнал «Управляющие машины и системы», 1994, No 4-5. Стахов А. П. Компьютеры Фибоначчи и новая теория кодирования: история, теория, перспективы// Электронный журнал Таганрогского радиотехнического университета «Перспективные информационные технологии и интеллектуальные системы», № 2 (18), 2004// http://pitis.tsure.ru/files18/p5.pdf. Категория:Системы счисления Категория:Золотое сечение Категория:Сжатие данных