green_fr (green_fr) wrote,
green_fr
green_fr

Category:

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

Всё в том же 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. Арифметические операции несколько усложняются, зато вывод на экран становится тривиальной задачей.

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

  • BD Louvre

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

  • Beaux Arts HS «Les secrets des chefs-d’oeuvre de la BD»

    Когда-то давно купил себе этот номер с мыслью, что нужно попытаться понять искусство комиксов. У нас в детстве комиксов не было вообще (редкие…

  • LG BD

    После « Жизни Адели» (блин, полтора года прошло, а фильм меня так и не отпускает!) захотелось прочитать комикс, по которому её сняли. Взял…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 29 comments

  • BD Louvre

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

  • Beaux Arts HS «Les secrets des chefs-d’oeuvre de la BD»

    Когда-то давно купил себе этот номер с мыслью, что нужно попытаться понять искусство комиксов. У нас в детстве комиксов не было вообще (редкие…

  • LG BD

    После « Жизни Адели» (блин, полтора года прошло, а фильм меня так и не отпускает!) захотелось прочитать комикс, по которому её сняли. Взял…