Понятие экономичности системы счисления

Число в системе счисления р с k разрядами, очевидно, будет иметь наибольшее значение в том случае, если все цифры числа окажутся максимальными, т.е. равными р - 1. Тогда

Количество разрядов числа при переходе от одной системы счисления к другой в общем случае меняется. Очевидно, если р = q^σ (σ - не обязательно целое), то (Z_p)^max = p^k - 1 = q^σk - 1. Т.е. количество разрядов числа в системах счисления р и q будут различаться в σ раз. Очевидно соотношение:

При этом основание логарифма никакого значения не имеет, поскольку σ определяется отношением логарифмов. Сравним количество цифр в числе 99₁₀ и его представлении в двоичной системе счисления: 99₁₀ = 1100011₂; т.е. двоичная запись требует 7 цифр вместо 2 в десятичной, σ = ln(10)/ln(2) = 3,322; следовательно, количество цифр в десятичном представлении нужно умножить на 3,322 и округлить в большую сторону: 2-3,322 = 6,644 = 7.

Введем понятие экономичности представления числа в данной системе счисления.

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

Речь в данном случае идет не о количестве разрядов, а об общем количестве сочетаний цифр, которые интерпретируются как различные числа. Поясним на примере: пусть в распоряжении имеется 12 цифр. Можно разбить их на 6 групп по 2 цифры («0» и «1») и получить шестиразрядное двоичное число; общее количество таких чисел, как уже неоднократно обсуждалось, равно 2⁶. Можно разбить заданное количество цифр на 4 группы по три цифры и воспользоваться троичной системой счисления - в этом случае общее количество различных их сочетаний составит 3⁴. Аналогично можно произвести другие разбиения; при этом число групп определит разрядность числа, а количество цифр в группе - основание системы счисления. Результаты различных разбиений можно проиллюстрировать таблицей:

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

Точное расположение максимума экономичности может быть установлено путем следующих рассуждений. Пусть имеется п знаков для записи чисел, а основание системы счисления р. Тогда количество разрядов числа k = п/р, а общее количество чисел (N), которые могут быть составлены, равно:

Если считать N(p) непрерывной функцией, то можно найти то значение р_т, при котором iN принимает максимальное значение. Функция имеет вид, представленный на рис.4.3.

Для нахождения положения максимума нужно найти производную функции N(p), приравнять ее к нулю и решить полученное уравнение относительно р.

Приравнивая полученное выражение к нулю, получаем ln p = 1, или р_т = е, где е = 2,71828... - основание натурального логарифма. Ближайшее к е целое число, очевидно, 3 - по этой причине троичная система счисления оказывается самой экономичной для представления чисел. В 60-х годах в нашей стране была построена вычислительная машина «Сетунь», которая работала в троичной системе счисления. Предпочтение все же отдается двоичной системе, поскольку по экономичности она оказывается второй за троичной, а технически она реализуется гораздо проще остальных. Таким образом, простота технических решений оказывается не единственным аргументом в пользу применения двоичной системы в компьютерах.

4.2.4. Перевод чисел между системами счисления 2 ↔ 8 ↔ 16

Интерес к двоичной системе счисления вызван тем, что именно эта система используется для представления чисел в компьютере. Однако двоичная запись оказывается громоздкой, поскольку содержит много цифр, и, кроме того, она плохо воспринимается и запоминается человеком из-за зрительной однородности (все число состоит из нулей и единиц). Поэтому в нумерации ячеек памяти компьютера, записи кодов команд, нумерации регистров и устройств и пр. используются системы счисления с основаниями 8 и 16; выбор именно этих систем счисления обусловлен тем, что переход от них к двоичной системе и обратно осуществляется, как будет показано ниже, весьма простым образом.

Двоичная система счисления имеет основанием 2 и, соответственно, 2 цифры: 0 и 1.

Восьмеричная система счисления имеет основание 8 и цифры 0, 1.....7.

Шестнадцатеричная система счисления имеет основание 16 и цифры 0, 1, ..., 9, А, В, С, D, Е, F. При этом знак «А» является 16-ричной цифрой, соответствующей числу 10 в десятичной системе; В₁₆ = 11₁₀; С₁₆ = 12₁₀; D₁₆ = 13₁₀; Е₁₆ = 14₁₀; F₁₆ = 15₁₀. Другими словами, в данном случае А ... F - это не буквы латинского алфавита, а цифры 16-ричной системы счисления и поэтому они имеют только такое начертание (не могут быть представлены в виде, например, соответствующих строчных букв, как в текстах).

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

Докажем две теоремы.

Теорема 1. Для преобразования целого числа Z_p → Z_q в том случае, если системы счисления связаны соотношением q = р^r, где r - целое число большее 1, достаточно Z_p разбить справа налево на группы по г цифр и каждую из них независимо перевести в систему q.

Доказательство:

Пусть максимальный показатель степени в записи числа р по форме (4.1) равен k - 1, причем, 2r > k -1 > r.

Таблица 4.1.

Вынесем множитель р^r из всех слагаемых, у которых j ≥ r. Получим:

где

Таким образом, r-разрядные числа системы с основанием р оказываются записанными как цифры системы с основанием q. Этот результат можно обобщить на ситуацию произвольного k-1 > r - в этом случае выделится не две, а больше (т) цифр числа с основанием q. Очевидно, Z_q = (b_m … b₀ )_q.