На этом шаге мы рассмотрим преобразование нормализованных чисел..
Вещественное число X может быть представлено в двух формах - естественной и нормализованной. В естественной форме у X имеется целая и дробная части, между которыми помещается разделитель (запятая или точка), например, 123,4567. Однако такая запись неудобна для слишком больших или, наоборот, слишком малых чисел. Кроме того, использование такой формы (она называется также "представление числа с фиксированной запятой") в компьютере вызвало бы снижение точности вычислений из-за необходимости приведения в соответствие разрядов обрабатываемых чисел и связанных с этим округлений или могло бы породить ситуацию, называемую переполнением, когда старший разряд числа не умещается в отведенной разрядной сетке. По указанным причинам вещественные числа в компьютере представляются в нормализованном виде (другое название - "представление числа с плавающей запятой"), главным достоинством которой является автоматическое масштабирование числа на каждом этапе обработки, что, с одной стороны, обеспечивает максимально возможную точность вычислений, а с другой - избавляет от необходимости принимать меры по предотвращению переполнения (за исключением достаточно экзотических ситуаций с выходом числа за отведенную разрядную сетку). По сути, это универсальная форма записи всех чисел, кроме определенных как "тип: целые" (например, Integer, Word или Byte в PASCAL'е).
Сначала познакомимся с необходимыми понятиями применительно к десятичной системе счисления.
Число X10 называется нормализованным, если оно представлено в виде
X10 = [+|-] M10· 10 [+|-] k10
В этой записи M10
называется мантиссой нормализованного числа; значения мантиссы лежат в
интервале 0,1
M10<1.
k10 называется порядком нормализованного числа - это целое
положительное десятичное число. Примеры: - 123410 = - 0,1234·104;
0,0345610 = 0,3456·10-1.
Понятие нормализованного числа
следует отличать от понятия числа в нормальной форме; данная форма достаточно
часто используется при записи чисел в математике, физике, технических
дисциплинах и отличается от нормализованного представления тем, что мантисса
лежит в интервале 1M10<10,
например, kБ=1,38·10-23.
При нормализации происходит расчленение "составляющих" числа с выделением знака числа, мантиссы, знака порядка и порядка - как будет показано ниже, это создает определенные удобства при хранении и обработке чисел в компьютере.
Аналогично нормализации десятичного числа можно в нормализованной форме представить и число в произвольной системе счисления p:
Xp = [+|-] Mp · p [+|-] kp (12)
При этом значения мантиссы лежат в
интервале p-1Mp<1
(т.е. первая значащая цифра мантиссы всегда ненулевая), а показатель степени
представляется в системе p (kp). Например, для p = 2:
X2 = - 101,012 = - 0,101012 · 2112
Мантисса
располагается в промежутке 0,12 M2<1,
что соответствует десятичному интервалу 0,510M10<1.
Рис.1. Алгоритм нормализации
Подобно задаче о преобразовании целых
и дробных чисел, можно поставить задачу о преобразовании представления числа в
нормализованной форме в системе счисления p к нормализованному представлению в
системе q. Практическое значение такого преобразование состоит в том, что, как
было сказано, в компьютере все вещественные числа хранятся и обрабатываются в
нормализованном двоичном представлении и, следовательно, при их вводе
осуществляется перевод X10
X2,
а при выводе - обратный перевод X2
X10.
Однако прежде, чем обсуждать такой перевод, необходимо рассмотреть, как
производится преобразование вещественного числа из естественной формы к
нормализованному виду.
При нормализации различаются ситуации
Xp>1 и Xp< p-1. В первом случае для
нормализации необходимо перемещать разделитель разрядов влево по числу до тех
пор, пока не исчезнет целая часть числа, но первая цифра после разделителя
будет ненулевой; каждое перемещение разделителя на 1 разряд влево эквивалентно
делению числа на p и, чтобы число не менялось, показатель должен возрастать на
1 при каждом сдвиге. Если обозначить эту операцию N
(будем
называть ее "нормализация влево"), то N
[(123,45)10] =
0,1234510·103; N
[(23,4·105)10]
= 0,23410·107; N
[(1212,2)3]
= 0,121223·311. Аналогично можно ввести операцию
"нормализация вправо" (N
),
обеспечивающая нормализацию чисел меньших p-1; очевидно, такие числа
необходимо умножать на p с одновременным уменьшением показателя на 1 до тех
пор, пока первая цифра после разделителя станет ненулевой. Например,
N[(0,000101·2-101)2]
= 0,101·2-1000;
N[(0,000987)10]
= 0,98710·10-3. Общий алгоритм нормализации можно изобразить
в виде блок-схемы на рисунке 1.
При практической реализации данного алгоритма не следует забывать, что изменение значения kp на 1 должно производиться по правилам арифметики системы счисления p. В дальнейшем при необходимости проведения нормализации в ходе каких-либо преобразований будем просто ссылаться на приведенный алгоритм как готовый модуль.
Вернемся к задаче перевода нормализованного числа из одной системы счисления в другую. Пусть, имеется число Xp = [+|-]Mp · p [+|-]kp, для которого необходимо найти соответствующее ему Xq = [+|-] Mq · q [+|-]kq. Представляется достаточно очевидным, что преобразование не затронет знаков мантиссы и показателя степени. Таким образом, для осуществления преобразования необходимо установить соответствие между (Mp, kp) и (Mq, kq). Оно получается достаточно просто, исходя из того, что Xp = Xq, откуда следует:
(13)
Из (13) вытекает, что для осуществления преобразования можно Mp
умножить на pkp, т.е. перейти к естественной форме числа в системе
p, перевести его в систему q, а затем нормализовать. Однако в таком варианте
действий теряется точность числа и возможно переполнение на промежуточных
этапах преобразования. Во избежание этого необходимо чередовать умножение (или
деление) на p и нормализацию по основанию q. При этом, поскольку все операции
выполняются по правилам арифметики в системы p, будут получены не (Mq
,kq) в окончательном варианте, а их представления в системе p -
обозначим их (Mq)p и (kq)p,
которые затем нужно будет перевести в систему q. Различаются также ситуации kp
0 и kp<0
- в первом случае необходимо умножать начальное и промежуточные значения
мантиссы на p и для нормализации делить на q, во втором - наоборот. Каждый раз
при умножении или делении на p показатель kp будет менять свой
значение на 1; продолжать действия следует до тех пор, пока не выполнится
условие kp= 0. Алгоритм действий для ситуации kp
0
представлен на рисунке 2.
Рис.2. Алгоритм действий для ситуации kp
0
Пример 8. Выполнить преобразование X10=16,510
X2.
Перевод можно осуществить отдельно для целой и дробной части, а затем их объединить - для нас этот результат послужит эталоном для проверки нового алгоритма. Легко получить, что 1610 = 100002, а 0,510 = 0,12; следовательно, 16,510 = 10000,12 = (0,100001·2101)2.
Алгоритм Real_1 начинает функционировать после нормализации исходного числа; для этой цели можно воспользоваться алгоритмом Norma; в результате начальными значениями будут M10 = 0,165; k10 = 2. Результаты операций будем заносить в таблицу:
| Шаг | Действие | M=(M2)10 | k10 | (k2)10 |
|---|---|---|---|---|
| 0 | 0,165 | 2 | 0 | |
| 1 | M:=M·10; k10= k10-1 | 1,65 | 1 | 0 |
| 2 | M:=M/2; k2= k2+1 | 0,825 | 1 | 1 |
| 3 | M:=M·10; k10= k10-1 | 8,25 | 0 | 1 |
| 4 | Т.к. k10= 0, MM2 | 1000,012 | 1 | |
| 5 | Нормализация по q=2 | 0,1000012 | 5 | |
| 6 | (k2)10k2 | 1000,012 | 101 |
Окончательно имеем: X2 = (0,100001·2101)2.
Подобным же будет алгоритм
преобразования X10X2
и при kp<0.
Последовательность действий при
обратном переводе X2X10
отчасти противоположна только что рассмотренной; для kp
0 она
представлена в виде блок-схемы на рисунке 3.
Нормализация в конце (после k=0) производится при необходимости.
Рис.3. Последовательность действий при обратном переводе
Пример 9. Выполнить преобразование: X2 = (0,11·2110)2
X10.
Для контроля результата: 0,112=0,7510; (2110)2=(26)10=64; следовательно, (0,11·2110)2=0,75·64=4810. Для преобразования воспользуемся построенным алгоритмом Real_2 (рис. 3). Промежуточные результаты снова будем заносить в таблицу:
| Шаг | Действие | M=(M2)10 | (k2)10 | k10 |
|---|---|---|---|---|
| 0 | Перевод | 0,75 | 6 | 0 |
| 1 | M:=M·2; k=k-1 | 1,5 | 5 | 0 |
| 2 | M:=M/10; k10= k10+1 | 0,15 | 5 | 1 |
| 3 | M:=M·2; k = k-1 | 0,3 | 4 | 1 |
| 4 | M:=M·2; k = k-1 | 0,6> | 3 | 1 |
| 5 | M:=M·2; k = k-1 | 1,2 | 2 | 1 |
| 6 | M:=M/10; k10= k10+1 | 0,12 | 2 | 2 |
| 7 | M:=M·2; k = k-1 | 0,24 | 1 | 1 |
| 8 | M:=M·2; k = k-1 | 0,48 | 0 | 2 |
| 9 | Т.к. k= 0, M = M10 | 0,48 | 0 | 2 |
Таким образом, получаем: (0,11·2110)2=0,48·102=48.
Как и в предыдущем преобразовании, алгоритм в случае kp<0 будет отличаться только тем, что число в процессе перевода необходимо делить на q и умножать на p.
Со следующего шага мы начнем рассматривать кодирование чисел в компьютере и действия над ними.
