Лучшие вопросы
Таймлайн
Чат
Перспективы

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

смешанная система счисления для целых чисел на основе чисел Фибоначчи Из Википедии, свободной энциклопедии

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

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

Подробнее Число, Запись в ФСС ...
Remove ads

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

Суммиров вкратце
Перспектива

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

Обоснование

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

Доказательство существования легко провести по индукции. Любое целое число попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого верно неравенство: . Таким образом, , где , так что разложение числа уже не будет содержать слагаемого .

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

Юпана

Thumb
Юпана

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

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

Суммиров вкратце
Перспектива
Подробнее ...

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

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

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

где N таково, что . При этом для всех .

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

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

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

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

Remove ads

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

Суммиров вкратце
Перспектива

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

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

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

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

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

Remove ads

Примечания

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads