Часть 4 Вопросы 10-12

Нормализованная форма числа

Вещественное число X может быть представлено в двух формах - естественной и нормализованной. В естественной форме у X имеется целая и дробная части, между которыми помещается разделитель (запятая или точка), например, 123,4567. Однако такая запись неудобна для слишком больших или, наоборот, слишком малых чисел. Кроме того, использование такой формы (она называется также «представление числа с фиксированной запятой») в компьютере вызвало бы снижение точности вычислений из-за необходимости приведения в соответствие разрядов обрабатываемых чисел и связанных с этим округлений или могло бы породить ситуацию, называемую переполнением, когда старший разряд числа не умещается в отведенной разрядной сетке. По указанным причинам вещественные числа в компьютере представляются в нормализованном виде (другое название - «представление числа с плавающей запятой»), главным достоинством которой является автоматическое масштабирование числа на каждом этапе обработки, что, с одной стороны, обеспечивает максимально возможную точность вычислений, а с другой - избавляет от необходимости принимать меры по предотвращению переполнения (за исключением достаточно экзотических ситуаций с выходом числа за отведенную разрядную сетку).

Число X₁₀ называется нормализованным, если оно представлено в виде

X₁₀ = ± M₁₀ · 10 ^±k10

В этой записи M₁₀ называется мантиссой нормализованного числа; значения мантиссы лежат в интервале 0,1 M₁₀<1. k₁₀ называется порядком нормализованного числа - это целое положительное десятичное число. Примеры: - 1234₁₀ = - 0,1234·10⁴; 0,03456₁₀ = 0,3456·10^-1.

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

Аналогично нормализации десятичного числа можно в нормализованной форме представить и число в произвольной системе счисления p:

Например, для p = 2:

X₂ = - 101,01₂ = - 0,10101₂ · 2¹¹²

Мантисса располагается в промежутке 0,1₂ M₂<1, что соответствует десятичному интервалу 0,5₁₀ M₁₀<1.

Подобно задаче о преобразовании целых и дробных чисел, можно поставить задачу о преобразовании представления числа в нормализованной форме в системе счисления p к нормализованному представлению в системе q. Практическое значение такого преобразование состоит в том, что, как было сказано, в компьютере все вещественные числа хранятся и обрабатываются в нормализованном двоичном представлении и, следовательно, при их вводе осуществляется перевод X₁₀ X₂, а при выводе - обратный перевод X₂ X₁₀. Однако прежде, чем обсуждать такой перевод, необходимо рассмотреть, как производится преобразование вещественного числа из естественной формы к нормализованному виду.

При нормализации различаются ситуации X_p>1 и X_p< p^-1. В первом случае для нормализации необходимо перемещать разделитель разрядов влево по числу до тех пор, пока не исчезнет целая часть числа, но первая цифра после разделителя будет ненулевой; каждое перемещение разделителя на 1 разряд влево эквивалентно делению числа на p и, чтобы число не менялось, показатель должен возрастать на 1 при каждом сдвиге. Если обозначить эту операцию N (будем называть ее «нормализация влево»), то N  [(123,45)₁₀] = 0,12345₁₀·10³; N [(23,4·10⁵)₁₀] = 0,234₁₀·10⁷; N [(1212,2)₃] = 0,12122₃·3¹¹. Аналогично можно ввести операцию «нормализация вправо» (N ), обеспечивающая нормализацию чисел меньших p^-1; очевидно, такие числа необходимо умножать на p с одновременным уменьшением показателя на 1 до тех пор, пока первая цифра после разделителя станет ненулевой. Например, N [(0,000101·2^-101)₂] = 0,101·2^-1000; N [(0,000987)₁₀] = 0,987₁₀·10^-3.

Пример: Выполнить преобразование X₁₀=16,5₁₀ X₂.

Перевод можно осуществить отдельно для целой и дробной части, а затем их объединить - для нас этот результат послужит эталоном для проверки нового алгоритма. Легко получить, что 16₁₀ = 10000₂, а 0,5₁₀ = 0,1₂; следовательно, 16,5₁₀ = 10000,1₂ = (0,100001·2¹⁰¹)₂.

Пример: Выполнить преобразование: X₂ = (0,11·2¹¹⁰)₂ X₁₀

Для контроля результата: 0,11₂=0,75₁₀; (2¹¹⁰)₂=(2⁶)₁₀=64; следовательно, (0,11·2¹¹⁰)₂=0,75·64=48₁₀.

Таким образом, получаем: (0,11·2¹¹⁰)₂=0,48·10² =48.

Представление чисел в памяти компьютера

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

·         целые положительные числа (целые числа без знака);

·         целые числа со знаком;

·         вещественные нормализованные числа.

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

Конечный размер разрядной сетки порождает понятие «наибольшее целое число», которого в обычном (немашинном) представлении чисел просто не существует. Если количество разрядов k и p=2, то (Z₂)^max = 2^k - 1. В частности, при k=16 (Z₂)^max = 2¹⁶ - 1 = 111111111111111₂ =65535₁₀. Другими словами, целого числа, скажем, 65636 и более в компьютере просто не может существовать и, следовательно, появление в ходе вычислений чисел, превышающих (Z₂)^max, должно интерпретироваться как ошибка. Минимальным целым числом в беззнаковом представлении, очевидно, является (Z₂)^min = 000000000000000₂ = 0₁₀. В языке программирования PASCAL целые числа без знака, для записи которых отводится 2 байта, определены как тип Word. Тип устанавливает способ кодирования числа, количество отводимых для записи ячеек памяти (т.е. разрядность числа), а также перечень допустимых операций при обработке. Выход за границу 65535 возможен только путем увеличения количества разрядов для записи числа, но это порождает новый тип со своим Z^max; например, тип Longint¹ с максимальным значением 2147483647₁₀, числа которого занимают 4 байта.

Кодирование положительных чисел

Рассмотрим, как с беззнаковыми числами выполняются арифметические операции, не меняющие типа числа; очевидно, к ним относятся сложение и умножение.

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

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

Пример: Найти сумму 1594₁₀ + 17563₁₀ при беззнаковой двоичной кодировке и 16-битном машинном слове. После перевода слагаемых в двоичную систему счисления и выполнения сложения получим (для удобства восприятия 16-ти разрядное число разобьем на группы по четыре разряда):

Пример: Найти сумму 65534₁₀ + 3₁₀

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

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

Пример: Найти произведение 13₁₀ × 5₁₀

Таким образом, умножение двоичных чисел сводится к операциям сдвига на один двоичный разряд влево и повторения первого сомножителя в тех разрядах, где второй сомножитель содержит 1, и сдвига без повторения в разрядах с 0. Сдвиг всегда чередуется со сложением из-за ограниченности числа регистров, которые имеются в процессоре для размещения операндов. Другими словами, реализации отдельной операции умножения в процессоре не требуется. Как и в операции сложения, при умножении чисел с ограниченной разрядной сеткой может возникнуть переполнение. Решается проблема рассмотренными выше способами.