Системы счисления

Введение

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

Основным определением будет следующее: позиционной системой счисления с основанием \(d\) (\(d\) — целое неотрицательное число, большее 1) называется множество \(D\) цифр и три отображения: \(v:D\to\mathbb{N}\), \(r:S\to\mathbb{N}\) и \(w:\mathbb{N}\to S\), в которых \(\mathbb{N}\) -- множество целых неотрицательных чисел, а \(S\) — множество непустых последовательностей элементов \(D\).

От указанных объектов требуются следующие свойства:

  • \(|D|=d\)
  • \(v(D)={x\in\mathbb{N} ,|, 0\leqslant x < d}\)
  • \(r(w(x))=x\)
  • \(r(a_n a_{n-1}\ldots a_1 a_0) = \sum_k d^k v(a_k)\)

Для них традиционны следующие названия: \(v\) — числовое значение цифры, \(w\) — \(d\)-ичная запись числа, \(r\) — число, соответствующее \(d\)-ичной записи. Мы будем далее называть \(w\) и \(r\) записью и считыванием соответственно.

Если одновременно рассматривается несколько систем счисления, то обычно их помечают нижним индексом. Например, \(r_3\circ w_2\) — композиция двоичной записи и троичного считывания. Переводом из системы счисления с основанием \(a\) в систему счисления с основанием \(b\) называют композицию \(w_b\circ r_a\).

Традиционно множество цифр состоит из знаков 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и букв латинского алфавита. Числовые значения «арабских» цифр стандартны. Числовые значения «латинских» цифр начинаются с десяти и идут в том же порядке, в котором идут латинские буквы. То есть, например, числовое значение буквы «z» равно тридцати пяти.

Во избежание путаницы договоримся далее, что последовательности цифр внутри формул, не сопровождённые нижним индексом, в числовом контексте следует воспринимать как числа, десятично считанные с этих последовательностей. Последовательности цифр же, сопровождённые индексом \(d\), в числовом контексте следует воспринимать как числа, считанные \(d\)-ично.

Это означает, что формулу

\[ 27+14_5+1101_2 \]

следует интерпретировать как

\[ r_{10}(27) + r_{5}(14) + r_{2}(1101) \]

что, в свою очередь, равно сумме двадцати семи, девяти и тринадцати.

Считывание числа

Операция считывания достаточно примитивна: чтобы считать число, достаточно вычислить значение многочлена

\[ \sum_k d^k v(a_k) \]

Единственное, о чём стоит напомнить: иногда многочлен проще вычислять при помощи так называемой схемы Горнера

\[ \sum_k x^k c_k = (\ldots((c_n x + c_{n-1}) x + c_{n-2}) x + \ldots) x + c_0 \]

Для тех, кому эта формула кажется нечитаемой, приведём аналогичный код:

def evaluate(p,x):
    n = degree(p)
    
    total = coeff(p,n)
    for i in range(n,0,-1):
        total = current * x + coeff(p,i-1)
    
    return total

Например, \(123_7\) можно считать по схеме Горнера так:

\[ 123_7 = (1\cdot 7 + 2)\cdot 7 + 3 = 63 + 3 = 66 \]

Запись числа

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

Сейчас мы приведём два эквивалентных способа записи числа. Первый из них вычисляет цифры, начиная с самой младшей, второй — наоборот, начиная с самой старшей.

Способ первый

Пусть \(N = \sum_k d^k v(a_k)\). Требуется найти цифры \(a_i\) (или хотя бы их числовые значения; будем считать операцию восстановления цифры по числовому значению тривиальной).

Младшую цифру легко определить, если заметить, что

\[ v(a_0) = v(a_0)\bmod d = \left(\sum_k d^k v(a_k)\right)\bmod d \]

Правое из этих двух равенств очевидно, а левое следует из неравенств \(0\leqslant v(a_0) < d\).

Вычтя \(v(a_0)\) из левой и правой частей равенства

\[ N = \sum_k d^k v(a_k) \]

и разделив их на \(d\), получаем такую же по виду задачу для числа \((N-v(a_0))/d\).

Способ второй

Старшую цифру можно найти так: ищем максимальное \(m\), для которого \(d^m\leqslant N\). Далее ищем максимальное \(c\), для которого \(c d^m\leqslant N\). Это \(c\) и будет числовым значением старшей цифры. Осталось таким же образом найти цифры числа \(N-c d^m\).

Упражнения

  1. Напишите функцию generate_digit_maps, заполняющую два изначально пустых глобальных словаря NUMBER_TO_DIGIT и DIGIT_TO_NUMBER соответствием между цифрами и их числовыми значениями для систем счисления с основанием, не превышающем 36. Внимание: другие названия функций и глобальных переменных будут считаться ошибкой.

  2. Напишите функции, реализующие отображения \(r_d\) и \(w_d\) соответственно. Элементы множества \(\mathbb{N}\) считать имеющими тип int, а элементы множества S — тип str.

Указанные функции должны иметь вид

def read (digits, d): pass
def write(number, d): pass
  1. Факториальная система счисления, использующаяся, например, при перечислении перестановок, устроена так: у \(k\)-й цифры записи есть всего \(k+1\) различное значение. То есть числа 0, 1, 2, 3, 4, 5, 6, ... имеют следующие записи: 0, 10, 100, 110, 200, 210, 1000, ... Модифицируйте функции read и write так, чтобы при d="fac" они осуществляли чтение и запись в факториальной системе счисления.