laplandian (laplandian) wrote,
laplandian
laplandian

Category:

Альтернативная двоичная система счисления

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

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

Пусть p1, p2, p3... - последовательность простых чисел. Любое натуральное число однозначно выражается в виде произведения неотрицательных степеней p1k1...pnkn, где pn - его наибольший простой делитель.

Обозначим каждое число pn в этой последовательности сочетанием kn единиц и нуля, и запишем их справа налево, по возрастанию делителей. Обозначим число 1 нулем. Любая последовательность сочетание нулей и единиц в этой системе однозначно выражает определенное натуральное число. И наоборот: любое натуральное число однозначно записывается нулем или последовательностью, начинающейся с единицы. Аналогично привычным логарифмическим системам счисления, лишние нули слева не меняют значения и отбрасывается в стандартной записи. Иными словами, получается вполне работоспособная альтернативная двоичная система. Примеры:

1=0
2=1
4=11
8=111
3=10
9=110
27=1110
6=101
5=100
25=1100
125=11100
10=1001
100=110011
1000=11100111
50=11001
20=10011
30=10101
17(7-е простое число)=1000000
170=100001001
1000000=11111100111111

Ноль обозначается пустой строкой или точкой.

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

1/3=(0).01
1/5=(0).001
3/5=10.001
5/10=100.1001=0.1 (единицы, стоящие в одинаковых позициях справа и слева, отбрасываются, что гарантирует несократимость)

Аналогично обычным системам счисления, лишние нули справа от точки могут быть отброшены: 00100.0010000=100.1001

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

6/55=101.001001
55/6=100100.101

Сложение, вычитание и вычисление остатка становится, однако, весьма нетривиальной, но решаемой, задачей. К примеру, для сложения можно разделить слагаемые на их НОД (для оптимизации алгоритма), перевести в обычную двоичную систему, сложить, перевести обратно и умножить на НОД. Рациональные числа записываются четко, безо всяких бесконечных циклов.

Для удобочитаемости можно заменить группы нулей и единиц на наборы символов, аналогичные восьмеричной или 16-ричной системе, хотя наглядность принципа при этом теряется:

7=1000p=Ap16
14=10001p=11p16
49=11000p=1Ap16

В общем, довольно любопытная и удобная для многих задач система счисления. Странно, что ее вроде никто раньше не описывал...
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 5 comments