Жмакин А.П. Архитектура ЭВМ (2006), страница 7

По этой причине переход, например, Z₃ Z_g проще осуществить через промежуточное преобразование к десятичной системе Z₃ -> Z₁₀ -> Z₈. Си­туация, однако, значительно упрощается, если основания исходной и конеч­ной систем счисления оказываются связанными соотношением p = q^r, где г — целое число (естественно, большее 1) или г = \/п (и > 1, целое) — эти случаи будут рассмотрены далее.

3.2.2. Перевод дробных чисел

из одной системы счисления в другую

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

Введем следующие обозначения: правильную дробь в исходной системе счисления р будем записывать в виде 0,Y_p, дробь в системе q — 0,Y_q, а

преобразование — в виде 0, Y_p -> 0, Y_q .

Последовательность рассуждений весьма напоминает проведенную ранее для натуральных чисел. В частности, это касается рекомендации осуществлять преобразование через промежуточный переход к десятичной системе, чтобы избежать необходимости производить вычисления в "непривычных" систе­мах счисления, т. е. 0,Y_p -> 0,7₁₀ -> 0,Y_q.

Это, в свою очередь, разбивает задачу на две составляющие: преобразование 0,Y_p -> 0,У₁₀ и 0,У₁₀ -» 0,Y_q , каждое из которых может рассматриваться не­зависимо.

Алгоритмы перевода 0,К₁₀ -> 0,Y_q выводятся путем следующих рассужде­ний. Если основание системы счисления q , простая дробь содержит п цифр, и Ь_к — цифры дроби {\<b_k <п, 0<Ь_к <п-\), то она может быть пред­ставлена в виде суммы:

Часть дроби от разряда / до ее конца обозначим е, и примем е„ =b_n/q. Очевидно, Е] = 0,Y_q, тогда в (3.5) легко усматривается рекуррентное соот­ношение:

Если вновь позаимствовать в PASCAL обозначение функции — на этот раз trunc, производящей округление целого вещественного числа путем отбра­сывания его дробной части, то следствием (3.6) будут соотношения, позво­ляющие находить цифры новой дроби:

Соотношения (3.7) задают алгоритм преобразования: 0,У|₀ -» 0,Y_q :

1. Умножить исходную дробь в десятичной системе счисления на q, выде­лить целую часть — она будет первой (старшей) цифрой новой дроби; от­бросить целую часть.

2. Для оставшейся дробной части операцию умножения с выделением целой и дробных частей повторять, пока в дробной части не окажется 0 или не будет достигнута желаемая точность конечного числа; появляющиеся при этом целые будут цифрами новой дроби.

3. Записать дробь в виде последовательности цифр после нуля с разделите­лем в порядке их появления в пп. 1 и 2.

| Пример 3.3

Выполнить преобразование 0,375₁₀ -> 0,Y₂. Результат — на рис. 3.2. Таким образом, 0,375₁₀ ->0,011₂.

Рис. 3.2. Результат выполнения примера 3.3

Перевод 0,Y_p ->0,У₁₀, как и в случае натуральных чисел, сводится к вычис­лению значения формы (3.5) в десятичной системе счисления. Например:

0,011₂ = 0 ■ 2"¹ +1 • 2~² +1 • 2"³ = 0 + 0,25 + 0,125 = 0,375,₀.

Следует сознавать, что после перевода дроби, которая была конечной в ис­ходной системе счисления, она может оказаться бесконечной в новой систе­ме. Соответственно, рациональное число в исходной системе может после перехода превратиться в иррациональное. Справедливо и обратное утвержде­ние: число иррациональное в исходной системе счисления в иной системе может оказаться рациональным.

! Пример 3.4

Выполнить преобразование 5,3(3)₁₀ -> У₈.

Перевод целой части, очевидно, дает: 5₁₀ =12₃ . Перевод дробной части: 0,3(3)i₀ -> 0,1. Окончательно: 5,3(3)ю —> 12,1₃.

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

3.2.3. Перевод чисел

между системами счисления 2 <-> 8 <-> 16

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

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

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

Шестнадцатеричная система счисления имеет основание 16 и цифры О, 1,..., 9, А, В, С. D, Е, F. При этом знак А является шестнадцатеричной цифрой, соответствующей числу 10 в десятичной системе, В₁₆=11,₀,

С₁₆=12_]0, D_I6=13₁₀, Е₁₆ = 14₁₀ и. F₁₆ =15₁₀. Другими словами, в данном случае А,F — это не буквы латинского алфавита, а цифры шестнадца­теричной системы счисления.

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

Теорема 1. Для преобразования целого числа Z_p -> Z_q в том случае, если

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

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

Таким образом, г -разрядные числа системы с основанием р оказываются записанными как цифры системы с основанием q. Этот результат можно обобщить на ситуацию произвольного к-\>г — в этом случае выделятся не две, а больше (w) цифр числа с основанием q. Очевидно,

Z_q = {b_m ...b₀)_q.

Теорема 2. Для преобразования целого числа Z_p -> Z_q в том случае,

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

Для каждой цифры справедливо: 0<а, <р-1 и поскольку p = q^r,

0<a_t<q^r -1, то в представлении этих цифр в системе счисления q максимальная степень многочленов (3.1) будет не более r-1 и эти мно­гочлены будут содержать по r цифр:

причем число Z_? содержит 2r цифр. Доказательство легко обобщается на случай произвольного количества цифр в числе Z„.

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

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

Количество разрядов числа при переходе от одной системы счисления к дру­гой в общем случае меняется.

Очевидно, если р = q (а — не обязательно целое), то

т. е. количество разрядов числа в системах счисления р и q будут разли­чаться в а раз, причем

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

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

Определение__

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

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

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