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

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

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

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

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

(Страница41)

Алгоритмы перевода 0, Y₁₀ → 0, Y_q выводятся путем следующих рассуждений Если основание системы счисления q, простая дробь содержит n цифр, и b _k – цифры дроби (1<b _k <n, 0<b_k<п-1), то она может быть представлена в виде суммы:

(3.5)

Часть дроби от разряда i до ее конца обозначим и примем Очевидно, , тогда в (3.5) легко усматривается рекуррентное соотношение:

(3.6)

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

(3.7)

Соотношения (3.7) задают алгоритм преобразования: 0, Y ₁₀ → 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, Y ₁₀, как и в случае натуральных чисел, сводится к вычислению значения формы (3.5) в десятичной системе счисления. Например:

0, 011₂=0*2 ^{- 1}+1*2 ^{- 2}+1*2 ^{- 3}=0+0, 25+0, 125=0, 375₁₀.

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

Пример 3.4

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

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

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

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

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

Восьмеричная система счисления имеет основание 8 и цифры 0, 1,..., 7, Шестнадцатеричная система счисления имеет основание 16 и цифры 0, 1,..., 9, А, В, С. D, E, F. При этом знак A является шестнадцатеричной цифрой, соответствующей числу 10 в десятичной системе, В₁₆=11₁₀, С₁₆=12₁₀, D₁₆=13₁₀, Е₁₆=14₁₀ и. F₁₆=15₁₀. Другими словами, в данном случае A,..., F — это не буквы латинского алфавита, а цифры шестнадцатеричной системы счисления.

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

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

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

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

где

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

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

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

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

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

Тогда

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