49440 (572341), страница 2
Текст из файла (страница 2)
Начнем с простой задачи перемножения двух чисел без знака (т.е. неотрицательных чисел), а затем рассмотрим один из наиболее широко известных алгоритмов умножения целых чисел со знаком, представленных в двоичном коде.
Умножения чисел без знака
1. При выполнении умножения необходимо формировать частичные произведения, по одному на каждый разряд множителя. Эти частичные произведения затем суммируются, а их сумма и есть результат умножения — полное произведение.
2. Сформировать частичные произведения в двоичном коде довольно легко. Если соответствующий разряд множителя равен 0, частичное произведение также равно 00..00. Если соответствующий разряд множителя равен 1 . частичное произведение равно множимому.
3. Полное произведение вычисляется суммированием частичных произведений, причем каждое очередное частичное произведение в этой сумме сдвигается на одну позицию влево относительно предыдущего.
4. Результатом перемножения двух n-разрядных целых чисел будет 2n-разрядное число.
Во-первых, суммирование очередного частичного произведения можно выполнять немедленно после того, как оно будет сформировано, не дожидаясь остальных. Во-вторых, можно сформировать частичные произведения. Для разряда в коде множителя, равного 1, нужно выполнить сдвиг и сложение кода множимого, а для разряда, равного 0, — только сдвиг.
Умножение чисел в дополнительном коде
Мы уже отмечали, что при выполнении сложения и вычитания чисел в дополнительном коде они интерпретируются как числа без знака. Схема оказывается неработоспособной при выполнении умножения. Она неприменима, если оба сомножителя отрицательны. Она неправильного результата в случае, если отрицателен хотя бы один из сомножителей.
Единственное отличие в том, что частичные произведения трактуются как 2n-разрядные числа, сформированные из n-разрядного множимого. Рассматривая 4-разрядное множимое как число без знака, получим после расширения до восьми разрядов. Любое частичное произведение, соответствующее умножению этого числа на некоторый разряд множителя, отличный от 0-го, формируется сдвигом расширенного кода множимого влево на соответствующее число разрядов, причем освободившиеся справа разряды, заполняются кодом 0. Каждое частичное - введение, образованное от отрицательного множимого, при его формировании знаковый разряд исходного числа должен быть расширен. Разряды отрицательного множителя в дополнительном коде не соответствуют частичным произведениям, сформированным сдвигом множимого. Для суммирования частичных произведений нельзя использовать значения разрядов кода множителя
Решить эту дилемму можно по-разному. Один из способов - преобразовать оба сомножителя в положительные числа, перемножить их по правилам умножения чисел без знака, а затем, если знаки сомножителей были разными, выполнить операцию отрицания результата по правилам, принятым для чисел в дополнительном коде. Конструкторы АЛУ предпочитают способ, который не требует выполнения дополнительного преобразования после завершения умножения: алгоритм Бута (Booth). Схема алгоритма Бута приведена в приложении (рисунок 3). Сомножители размещаются в регистрах. Кроме них имеется одноразрядный регистр, который связан с младшим разрядом регистра. Если оба разряда имеют одинаковые значения, все разряды регистров сдвигаются на 1 разряд вправо. Такую операцию принято называть сдвигом с сохранением знака или арифметическим сдвигом. Следовательно, произведение на такой множитель можно получить с помощью всего одной операции сложения и одной операции вычитания.
Представление чисел в формате с плавающей точкой
В формате с фиксированной точкой, в частности в дополнительном коде, можно представлять положительные и отрицательные числа в диапазоне, симметричном на числовой оси относительно точки 0. Расположив воображаемую разделяющую точку в середине разрядной сетки, можно в этом формате представлять не только целые, но и смешанные числа, а также дроби.
Однако такой подход позволяет представить на ограниченной разрядной сетке множество вещественных чисел в довольно узком диапазоне. Нельзя представить очень большие числа или очень маленькие. При выполнении деления больших чисел, как правило, теряется дробная часть частного.
При работе в десятичной системе счисления ученые давно нашли выход из положения, применяя для представления числовых величин так называемую научную нотацию.
Этот же подход можно применить и в двоичной системе счисления. Компоненты можно сохранить в двоичном слове, состоящем из трех полей:
• поле знака числа (плюс или минус);
• поле мантиссы;
• поле порядка.
Основание характеристики во всех существующих стандартах такой формы представления подразумевается неявно и не сохраняется, поскольку оно одинаково для всех чисел.
Для представления порядка используется так называемый смещенный формат. Для получения действительного двоичного кода пс рядка из значения, сохраняемого в этом поле, нужно вычесть фиксированное смещение. Этого не наблюдается при представлении чисел в прямом и дополнительном кодах. Преимущество смещенного представления порядка в формате числа с плавающей точкой в том, что результат сравнения двух неотрицательных вещественных чисел будет таким же, как и результат сравнения : кодов, рассматриваемых как целые числа без знака.
Для упрощения алгоритмов выполнения арифметических операций обычно принято нормализовать мантиссу. Код, состоящий из нулей во всех разрядах, считается допустим и представляет число 0. В области переполнения можно попасть в том случае, если результат арифметической операции имеет абсолютную величину.
Стандарт IEEE формата с плавающей точкой
Хотя унификации формата представления чисел с плавающей точкой, что является необходимым условием переносимости программного обеспечения. Разработан стандарт 754-CLE85. В последнее десятилетие практически все процессоры и арифметические процессоры проектируются с учетом требований этого стандарта.
Стандарт специфицирует два варианта формата: 32-битовый — обычное представление и 64-битовый — удвоенная точность представления. В первом формате поле порядка занимает 8 бит, а во втором — 11 бит. Стандарт регламентирует использование числа 2 в качестве неявно заданного значения основания характеристики. Помимо основных, в стандарте предусмотрены два расширенных варианта форматов обычной и удвоенной точности. Расширенные форматы позволяют включать дополнительные биты в поле порядка, предназначаются для промежуточных вычислений. За счет повышения точности снижается вероятность появления слишком больших ошибок. А при расширении диапазона снижается вероятность появления переполнения. Еще одно достоинство расширенного формата обычной состоит в том, что он позволяет использовать некоторые свойства формата с удвоенной точностью, но при этом не требует соответствующего увеличения времени выполнения арифметических операций.
Арифметические операции над числами в формате с плавающей точкой
При сложении и вычитании необходимо предварительно уравнять порядки операндов, что требует сдвига положения разделительной точки в мантиссе. Операции умножения и деления уравнивания порядков операндов не требуют. При выполнении операций могут возникнуть следующие особые ситуации.
• Переполнение порядка. Положительный порядок результата превышает максимальное значение, предусмотренное форматом. Такой результат может трактоваться как величина + или - .
• Потеря значимости порядка. Отрицательный порядок результата меньше минимального значения, допускаемого принятым форматом
• Потеря значимости мантиссы. В процессе уравнивания порядков мантисса сдвигается настолько сильно вправо, что старший значащий ее разряд выходит за пределы разрядной сетки. Как будет показано далее, в этом случае требуется определенная форма округления.
• Переполнение мантиссы. При сложении мантисс с одинаковыми знакам: возможно появление переноса из старшего разряда.
Сложение и вычитание
Алгоритмы выполнения операций сложения и вычитания в формате с плавающей точкой сложнее, чем аналогичные алгоритмы для чисел с фиксированной точкой. Связано это с необходимостью выравнивания порядков операндов. Алгоритм включает четыре основных этапа.
1. Проверка на нуль.
2. Сдвиг мантисс для выравнивания порядков.
3. Суммирование или вычитание мантисс.
4. Нормализация результата.
Детальный пошаговый анализ этого алгоритма покажет, какие функции используются при выполнении операций сложения и вычитания чисел в формате с плавающей точкой. В дальнейшем для определенности будем считать, что используется формат регламентированный стандартом IEEE 754. Перед началом выполнения операций операнды должны быть помещены в регистры АЛУ. Если в используемом формате с плавающей точкой предполагается неявный старший разряд мантиссы, этот разряд должен быть в явном виде включен в регистры операндов, и все операции с ним в дальнейшем будут проводиться точно так как и с остальными разрядами мантиссы. Поскольку операции сложения и вычитания отличаются только тем, что при вычитании предварительно изменяется знак второго операнда (вычитаемого), эта операция включена в ветвь вычитание на схеме алгоритма: после чего обе ветви сливаются. Далее анализируется, не равен ли один из операндов нулю. Если это так, то результат — значение второго операнда. Очевидно, что нельзя просто сложить мантиссы этих двух чисел. Нужно выровнять разрядные сетки мантисс так, чтобы соответственные разряды (разряды с равным весом) занимали одинаковые позиции.
Выравнивание выполняется за счет сдвига мантиссы меньшего числа вправо, мантиссы большего числа — влево. Поскольку в любом варианте теряются, выполняется сдвиг мантиссы меньшего числа вправо, что привел к утере ее младших разрядов. Сдвиги выполняются до тех пор, пока значения порядков обоих чисел не станут равны. Таким образом, если порядки слагаемых существенно отличаются, меньшее слагаемое в результате не учитывается. После того, как порядки будут выровнены, наступает этап сложения. Поскольку слагаемые могут иметь разные значения алгебраическая сумма может оказаться равной нулю.
В этом случае необходимо выполнить дополнительный сдвиг результата вправо и временно увеличить на 1 значение порядка. Но тогда возможно появление - переполнения порядка, которое расценивается как аварийная ситуация и влечет за собой прекращение операции. После сложения мантисс наступает этап нормализации результата, Нормализация представляет собой серию сдвигов кода мантиссы влево с одновременным уменьшением значения порядка до тех пор, а значение старшей цифры мантиссы не станет отличным от нуля.
Умножение и деление
При работе с числами в формате с плавающей точкой алгоритмы умножения и деления оказываются проще алгоритмов сложения и вычитания. Сначала рассмотрим алгоритм умножения (Приложение, рисунок 4). Сразу же после начала операции проверяется, не равен ли нулю один из сомножителей. Если это так, то произведение также будет равно нулю. Следующий шаг — суммирование порядков. Поскольку, как правило, для хранения порядков используется смещенное представление, при суммировании двух смещенных представлений результат будет смещен дважды. Поэтому после суммирования кодов порядков из суммы вычитается значение смещения. При суммировании может возникнуть как переполнение порядка, так и потеря значимости. В обоих случаях формируется соответствующий сигнал.
Если порядок произведения не выходит из диапазона, определенного форматом, далее перемножаются мантиссы сомножителей с учетом их знаков. Умножение мантисс выполняется по тому же алгоритму, что и умножение целых чисел в прямом коде, т.е. фактически перемножаются числа без знака, а затем произведению приписывается знак "плюс" или "минус" в зависимости от сочетания знаков сомножителей. Произведение мантисс имеет разрядность, вдвое большую, чем каждый из сомножителей. Лишние младшие разряды отбрасываются при округлении. После того как будет получено произведение мантисс, результат нормализуется и округляется. Эти операции выполняются так же, как и при сложении или вычитании. Необходимо учесть, что при нормализации может возникнуть переполнение или потеря значимости порядка.
Теперь рассмотрим алгоритм деления (Приложение, рисунок 5). Как и ранее, первый этап — анализ операндов на равенство нулю. Если нулю равно делимое, то результату сразу присваивается значение 0. Если же нулю равен делитель, то в зависимости от конкретной реализации АЛУ результату может быть присвоено значение "бесконечность" с соответствующим знаком или сформирован сигнал арифметической ошибки. Следующий этап — вычитание кода порядка делителя из кода порядка делимого. При этом получится несмещенный код разности, который нужно скорректировать — сложить с кодом смещения. После завершения операций с порядком результата проверяется, не возникло ли переполнение порядка или потеря значимости. Следующий этап — деление мантисс. За ним следуют обычные операции нормализации и округления.
Точность выполнения операций. Дополнительные разряды
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
