February 5th, 2021

2017

Смена системы счисления и гибридные системы

Всё в том же Pour la science № 519 отличная рубрика о гибридных системах счисления. Сначала по определениям: бывают как минимум позиционные системы (наша) и унитарная система (палочки или точки, сколько палочек — такое число и записано).

Автор (имеется в виду не столько автор рубрики, сколько написавший ему постоянный читатель, автор этой системы) предлагает рассмотреть унитарную систему со знаком &.

Не могу удержаться: этот знак по-французски называется «esperluette», от окситанского «es-per-lou-et», дословно «это заменяет „и“». Английское «ampersand» точно так же раскладывается на «and — per se — and» — «„и“ в смысле „и“».

Вернёмся к унитарной системе. Число 5 в ней записывается как &&&&&.

Автор предлагает три правила замены:
1. &x -> 0&x
2. x0&&y -> x&0y
3. x0&y -> x1y

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

&&&&& -> (r1) -> 0&&&&& -> (r2) -> &0&&& -> (r1) ->0&0&&& -> (r2) -> 0&&0& -> (r2) &00& -> (r1) -> 0&00& -> (r3) -> 100& -> (r3) -> 101.

Итак, перед нами набор правил, позволяющий перевести любое число из унитарной записи в бинарную. Действительно, 1012 = 510.

Как это работает? Можно рассматривать все промежуточные строки в этом преобразовании как запись числа в смешанной системе. В ней три символа: 0, 1 и &. 0 — это «ноль позиционной системы», 1 — «один позиционной системы», а & — «один унитарной системы». С одним нюансом — унитарные единицы имеют вес, как в позиционной системе, то есть их значение зависит от количества 0 и 1 справа от них.

Примеры:
& = 1 (одна единица)
&0 = 2 (одна двойка)
&00 = 4 (одна четвёрка)
&&0 = 4 (две двойки)
&00& = 5 (одна четвёрка и одна единица)

То же самое с 1, только нужно не забывать считать и их:
&1 = 3 (одна двойка + 1)
&01 = 5 (одна четвёрка + 1)
&&10 = 10 (две четвёрки + 2)

Легко проверить, что описанные правила сохраняют выбранное число. Чуть сложнее, но тоже можно проверить, что процесс сходится, и начав с унитарной записи, мы придём к записи из ноликов и единичек => у нас получились правила перевода в бинарную запись.


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

Система достаточно просто расширяется на любую другую базу позиционного счисления.

Можно смешать правила перевода из бинарной системы в унитарную с правилами перевода из унитарной системы в десятичную — у нас получатся правила перевода из бинарной системы в десятичную. Ну и вообще, можно сделать правила перевода из любой системы в любую.

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


Зачем это нужно, помимо несомненной красоты? Наверное, такие алгоритмы проще / эффективнее тупого деления с остатком. А мне понравилась сама идея смешанной системы счисления.

И тут автор просто добил меня, рассказав, что именно такую систему использовали майя. У меня просто восхищение перед людьми, умеющими не просто понять что-то (я делал презентацию о системе счисления майя для детей — она не столь уж и сложная), но ещё и выйти на более высокий уровень абстракции, увидеть какую-то общую картину. Не только описание объекта, но и общие характеристики класса. А потом несколько других возможных реализаций этого класса. А потом несколько других возможных классов-обобщений.

У майя самый верхний уровень — позиционный, с базой в 20 (в случае календарного счёта могла быть и база 18, чтобы получить 20*18=360 — почти точное количество дней в году). А на каждой позиции записывался не просто знак от «0» до «19» (это была бы простая позиционная система), а знак, состоящий из палочек (5) и точек (1). То есть, одновременно унитарная система (количество точек и пятёрок), унитарно-пятеричная система (пять точек заменяются на палочку) и позиционная система с базой 20.

Другой пример смешанной системы — использовавшийся в калькуляторах BCD. Я как-то не задумывался раньше о задаче вывода результата расчёта на экран калькулятора. Вот посчитали мы 5556*6665=37030740. В бинарном виде этот результат выглядит как 10001101010000101101010100 — как его перевести в понятное человеку 37030740?

Оказывается, в калькуляторах числа часто хранили не в двоичной, а в двоично-десятичной системе. Это когда каждое число записывается в десятичной системе, а потом уже каждая его десятичная цифра записывается в двоичном виде. 5556 запишется как 0101-0101-0101-0110. Арифметические операции несколько усложняются, зато вывод на экран становится тривиальной задачей.

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