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

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

Для компьютеров, основанных на классической двоичной системе счисления, не всегда можно эффективно решать проблему отсутствия механизма обнаружения ошибок. В 80-х годах XX столетия группа ученых под руководством профессора Алексея Петровича Стахова из Таганрогского радиотехнического института создала опытный экземпляр помехоустойчивого процессора [3]. Этот процессор мог сам контролировать возникающие в его работе сбои. Для кодирования информации была выбрана фибоначчиева система счисления. Ее использование позволило построить удивительный процессор, на званный “Фибоначчи-процессор”, или “Ф-процессор”. И хотя успешная попытка построения помехоустойчивого процессора на основе фибоначчиевой системы счисления носила скорее теоретический, чем практический интерес, изучение этой замечательной системы счисления заслуживает внимания.

Для указания, что число записано в ФСС, будем использовать в нижнем индексе сокращение fib. Например, 10000101fib = 3810 .

Числа Фибоначчи — элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10 946, …, в которой каждое последующее число, начиная с третьего, равно сумме двух предыдущих чисел.

Для формального определения чисел Фибоначчи используют следующее рекуррентное соотношение:

Последовательность, известная у нас как числа Фибоначчи, использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи (1170-1250).

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

Леонардо Пизанский Фибоначчи. Благодаря книге Фибоначчи “Liber Abaci” Европа узнала индоарабскую систему чисел, которая позднее вытеснила традиционные для того времени римские числа.

ФСС относится к позиционным системам. Алфавитом ФСС являются цифры 0 и 1, а ее базисом — последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …. Обратите внимание, что F 0 = 1 в базис не включается.

В табл. перечислены некоторые числа в двоичной и фибоначчиевой системах счисления.

10100100 или 10011100 или 10100011 или 10011011

Фибоначчиева система является разновидностью двоичной системы — ее алфавит составляют цифры 0 и 1. Следовательно, эту неклассическую двоичную систему счисления, вообще говоря, можно использовать для кодирования информации в компьютере, так как элементная база современной компьютерной техники ориентирована на обработку двоичных последовательностей.

Избыточность ФСС проявляется в различных кодовых представлениях одного и того же числа.

4.1. Алгоритмы перевода целых чисел из ФСС в десятичную систему и обратно

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

В P -ичных системах счисления базис является геометрической прогрессией. Вклад в значение числа цифры a, стоящей на k -м месте слева, равен a-P k , где P — основание системы счисления. Часто говорят, что “вес” k -го разряда равен P k .

В ФСС “вес” каждого разряда числа также определяется базисом этой системы. Для удобства дальнейшей работы выпишем “веса” первых 10 разрядов ФСС (нумерацию разрядов ведем справа налево, начиная с первого). Такая нумерация разрядов удобна, поскольку в качестве веса k -го разряда используется k -е число Фибоначчи.

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

Число 137=1×89+09times;55+19times;34+09times;21 +1×13 +0×8+09times;5 +0×3+09times;2+19times;1 запишется в виде 1010100001fib. Отметим, что в фибоначчиевой записи не встречается две единицы подряд.

Любопытства ради, заметьте, что

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

Число 0,6180… называют золотым сечением и используют в численном анализе, в строительстве сооружений, при поиске гармонии в природе и обществе. Еще строители Парфенона усматривали золотую пропорцию катетов 0,6180. 0,3820 в приятнейшем для глаза треугольнике.

Ознакомьтесь с принципами работы непозиционных и смешанных систем счисления и ответьте на приведенные ниже вопросы.

1. Дайте определения непозиционных и смешанных систем счисления.

2. Назовите и охарактеризуйте свойства непозиционных и смешанных систем счисления.

3. Назовите известные вам непозиционные системы счисления.

4. Назовите известные вам смешанные системы счисления.

5. Объясните причину неполной непозиционности римской системы счисления.

6. Охарактеризуйте различие между цифрой и числом.

7. Ознакомившись с позиционными системами счисления, охарактеризуйте систему счисления майя.

8. Сравните между собой факториальную и фибоначчиеву системы счисления.

9. Чему равно отношение 15-го и 16-го чисел Фибоначчи и насколько оно далеко от золотого сечения?

10. Находится ли представительство партий в Государственно думе в отношении золотого сечения?

11. Чему равна обратная величина золотого сечения? Не наводит ли эта величина на размышления, которые позволили бы найти золотое сечение с большим числом знаков?

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

1. Гашков, С. Б. Системы счисления и их применение. – М. МЦНМО, 2004. – 52 с. – [Электронный ресурс]. – Режим доступа: http://www.mccme.ru/mmmf-lectures/books/books/book.29.pdf, свободный. – Загл. с экрана.

2. Стахов, А. П. Музей Гармонии и Золотого Сечения / А.П. Стахов, А.А. Слученкова. – [Электронный ресурс]. – Режим доступа: http://www.goldenmuseum.com/index_rus.html, свободный. – Загл. с экрана.

3. Фомин, С. В. Популярные лекции по математике. – М. Наука, 1987. – 48 с. – [Электронный ресурс]. – Режим доступа: http://ilib.mirror1.mccme.ru/plm/ann/a40.htm, свободный. – Загл. с экрана.

4. Яглом, И. М. Системы счисления // Научно-популярный физико-математический журнал «Квант». – М. МЦНМО, 1970. – №6. – С. 2-10. – [Электронный ресурс]. – Режим доступа: http://kvant.mirror1.mccme.ru/1970/06/sistemy_schisleniya.htm, свободный. – Загл. с экрана.

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

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

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

1.1. Обоснование

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

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

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

1.2.1. Юпана

Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен [2] .

1.2.2. В теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системе счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:

где n — номер самого старшего разряда с единицей.

1.3. Арифметика

Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 0 2 = 10 .

В фибоначчиевой системе счисления дело обстоит сложнее:

  • Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0 2 00 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1 =1=F2 и F0 =0.
  • Во-вторых, требуется избавляться от соседних единиц: 0 11 = 100. Правило для раскрытия двоек является следствием этого равенства: 0 2 00 = 0100 + 00 11 = 0 11 1 = 1001 .

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

Представление
через
степени 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. Эдуард Цекендорф — www.goldenmuseum.com/1601Mathematics_rus.html
  2. Antonio Aimi, Nicolino De Pasquale Andean Calculators — web.archive.org/web/*/http://www.quipus.it/english/Andean Calculators.pdf.
  3. en:Golden ratio base  (англ.)
  4. последовательность A101330 — oeis.org/A101330 в OEIS, Zeckendorf’s theorem  (англ.)
  5. Notes on the Fibonacci circle and arroba products — www.research.att.com/

njas/sequences/a101330.txt  (англ.)

  • D. E. Knuth (1988). «Fibonacci multiplication». Applied Mathematics Letters1 (1): 57-60. DOI:10.1016/0893-9659(88)90176-0 — dx.doi.org/10.1016/0893-9659(88)90176-0.
  • Литература

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

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

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

    Обоснование

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

    Доказательство существования легко провести по индукции. Любое целое число a ≥ 1 <\displaystyle a\geq 1> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n ≥ 2 <\displaystyle n\geq 2> верно неравенство: F n ≤ a < F n + 1 <\displaystyle F_\leq a> . Таким образом, a = F n + a ′ <\displaystyle a=F_+a’> . где a ′ = a − F n < F n − 1 <\displaystyle a'=a-F_\ <\ F_> . так что разложение числа a ′ <\displaystyle a'> уже не будет содержать слагаемого F n − 1 <\displaystyle F_> .

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

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

    Предполагают, что некоторые разновидности юпаны (абака инков ) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен [2] .

    В теории информации

    На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.

    Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:

    где n — номер самого старшего разряда с единицей.

    Арифметика

    Сложение чисел в позиционных системах счисления выполняется с использованием переноса. позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 0 2 = 10 .

    В фибоначчиевой системе счисления дело обстоит сложнее:

    • Во-первых, вес старших разрядов не является кратным весу разряда, из которого требуется перенос. При сложении двух единиц в одном разряде требуется перенос не только влево, но и вправо: 0 2 00 = 1001. При переносе в отсутствующие разряды ε1 и ε0 следует помнить, что F1 =1=F2 и F0 =0.
    • Во-вторых, требуется избавляться от соседних единиц: 0 11 = 100. Правило для раскрытия двоек является следствием этого равенства: 0 2 00 = 0100 + 00 11 = 0 11 1 = 1001 .

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

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

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

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

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

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

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

    Для целых чисел a = ∑ k ε k F k <\displaystyle a=\sum _\varepsilon _F_\ > и b = ∑ l ζ l F l <\displaystyle b=\sum _\zeta _F_\ > можно определить «умножение» [4]

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

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

    Эта операция обладает ассоциативностью. на что впервые обратил внимание Дональд Кнут [6]. Следует отметить, что другое «произведение» ∑ k. l ε k ζ l F k + l − 2. <\displaystyle \sum _\varepsilon _\zeta _F_,> отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

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

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

    Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д. Последовательность Фибоначчи определяется следующим образом:

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

    Несколько первых её членов : Фибоначчиева система счисления

    Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci) (также известный как Леонардо Пизанский (Leonardo Pisano)). Однако именно благодаря математику 19 века Люка (Lucas) название «числа Фибоначчи» стало общеупотребительным. Впрочем, индийские математики упоминали числа этой последовательности ещё раньше: Гопала (Gopala) до 1135 г. Хемачандра (Hemachandra) — в 1150 г.

    Числа Фибоначчи обладают множеством интересных математических свойств.

    Вот лишь некоторые из них:

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

    Теорема Цекендорфа утверждает, что любое натуральное число n можно представить единственным образом в виде суммы чисел Фибоначчи:

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

    где k1 >= k2+2, k2 >= k3+2. kr >= 2 (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

    Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:

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

    причём ни в каком числе не могут идти две единицы подряд.

    Нетрудно получить и правило прибавления единицы к числу в фибоначчиевой системе счисления: если младшая цифра равна 0, то её заменяем на 1, а если равна 1 (т.е. в конце стоит 01), то 01 заменяем на 10. Затем «исправляем» запись, последовательно исправляя везде 011 на 100. В результате за линейное время будет получена запись нового числа.

    Перевод числа в фибоначчиеву систему счисления осуществляется простым «жадным» алгоритмом: просто перебираем числа Фибоначчи от больших к меньшим и, если некоторое Фибоначчиева система счисления. то Фибоначчиева система счисления входит в запись числа Фибоначчиева система счисления. и мы отнимаем Фибоначчиева система счисления от Фибоначчиева система счисления и продолжаем поиск.

    В теории информации

    На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системе счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу). То есть, кодовая последовательность имеет вид:

    где n — номер самого старшего разряда с единицей.

    Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.

    В фибоначчиевой системе счисления дело обстоит сложнее:

    0200 = 0100 + 0011 = 0111 = 1001.

    Добавить комментарий

    Ваш e-mail не будет опубликован. Обязательные поля помечены *