Алгоритм - умножение
Cтраница 1
Алгоритм умножения допускает использование в качестве множителя ненс рмализованного числа. При этом циклы умножения выполняются до тех пор, пока не встретится первая нулевая цифра. Таким образом, выход из цикла умножения происходит до того, как мантисса множителя будет исчерпана. Это эквивалентно тому, что умножение производится на нормализованный операнд. Поэтому если результат получается ненормализованным, то не более чем на одну цифру. В этом случае происходит нормализация результата с соответствующей корректировкой характеристики. В любом случае характеристика результата перед формированием и записью окончательного результата должна быть откорректирована вычитанием суммарного ПНЛ, который в общем случае равен сумме ПНЛ множимого и множителя. [1]
Алгоритм умножения в машине сводится к принципу умножения в столбик. Машинная операция умножения выполняется как сложение и сдвиг результата сложения. [2]
Алгоритмы умножения и деления в МП ВМ86 реализованы не аппаратно, а в виде микропрограмм. Поэтому длительность команд MUL, IMUL, DIV, IDIV включает большое число тактов, причем длительность каждой команды зависит не только от разрядности операндов и расположения операнда src ( в регистре или в памяти), но и от конкретных значений операндов в пределах, указанных в табл. 2.10 диапазонов длительности команд. В первом столбце в скобках указана длина сомножителей команд умножения и длина делителя ( частного) для команд деления. [3]
 |
Функциональная схема универсального операционного суммирующего блока для чисел с плавающей запятой. [4] |
Алгоритм умножения чисел с плавающей запятой следующий. [5]
Рассмотрим юбычный алгоритм умножения десятичных чисел: для двух чисел, каждое из которых имеет п знаков, требуется п2 произведений однозначных чисел. Обычно полагают, что это минимальное количество. Мы пренебрегаем затратами на операцию сдвига влево. [6]
Можно обобщить алгоритм умножения из разд. [7]
Мы почерпнули алгоритм умножения у Кнута, а алгоритм деления - у Ахо, Хопкрофта и Ульмана; оба алгоритма переработаны для наших целей. [8]
Так, алгоритм умножения числа 119 на 102 может быть представлен всего одной командой, если операция умножения является для-нее простой. Данный алгоритм может также состоять из нескольких операций сложения и сдвига, если указанные операции являются простыми для машины. [9]
Для реализации алгоритма умножения используют суммирующие схемы со сдвигами множимого или сумм частичных произведений как влево, так и вправо. Умножение может начинаться как с младшего, так и со старшего разряда множителя. При умножении n - разрядных чисел получается произведение, содержащее 2п разрядов. Так как разрядная сетка ограничена до п разрядов, то п младших разрядов теряются. Округление при прямых кодах сомножителей выполняется прибавлением 1 к старшему из отбрасываемых разрядов результата. Если при этом возникает единица переноса, то она суммируется с младшим из оставшихся разрядов произведения. В конце операции умножения знак произведения передается из сумматора знаков сомножителей в знаковый разряд сумматора. Выполнение операции умножения в прямом коде рационально только в случае хранения чисел в памяти ЭВМ в том же коде. [10]
Для реализации алгоритма умножения используются суммирующие схемы со сдвигами множимого или сумм частичных произведений как влево, так и вправо. Умножение может начинаться как с младшего, так и со старшего разряда множителя. При умножении - разрядных чисел получается произведение, содержащее 2л разрядов. Так как разрядная сетка ограничена до п разрядов, то п младших разрядов теряется. Округление при прямых кодах сомножителей выполняется прибавлением 1 к старшему из отбрасываемых разрядов результата. Если при этом возникает единица переноса, то она суммируется с младшим из оставшихся разрядов произведения. В конце операции умножения знак произведения передается из сумматора знаков сомножителей в знаковые разряды сумматора. Сигнал ф при умножении чисел всегда равен О, так как переполнения разрядной сетки при умножении чисел не бывает. [11]
Для реализации алгоритма умножения используются суммирующие схемы со сдвигами множимого или сумм частичных произведений как влево, так и вправо. Умножение может начинаться как с младшего, так и со старшего разряда множителя. При умножении n - разрядных чисел получается произведение, содержащее 2п разрядов. Так как разрядная сетка ограничена до п разрядов, то п младших разрядов теряется. Округление при прямых кодах сомножителей выполняется прибавлением 1 к старшему из отбрасываемых разрядов результата. Если при этом возникает единица переноса, то она суммируется с младшим из оставшихся разрядов произведения. В конце операции умножения знак произведения передается из сумматора знаков сомножителей в знаковые разряды сумматора. По состоянию знакового разряда произведения определяется сигнал со. Сигнал ф при умножении чисел всегда равен О, так как переполнения разрядной сетки при умножении чисел не бывает. [12]
Один из алгоритмов умножения на четыре разряда иллюстрируется табл. 84 на примере первого способа умножения, где буквами хп, хп -, xn-i и хп-з обозначены цифры, зафиксированные в четырех младших разрядах регистра RGX. В каждом такте умножения сдвиг осуществляется одновременно на четыре разряда. [13]
 |
Зависимость ускорения S от числа процессоров р для различных алгоритмов линейной алгебры. [14] |
Наилучшим ускорением обладает алгоритм умножения матрицы на вектор, что объясняется тем, что, во-первых, граф данного метода состоит из 10 ( в данном случае) независимых подграфов, во-вторых, этот граф имеет наименьшее число дуг в расчете на одну вершину. Последним свойством обладает и граф скалярного умножения векторов, однако он имеет в десять раз меньше вершин, что приводит к более плохой балансировке загрузки процессоров и, следовательно, к снижению ускорения. Наихудшим ускорением обладает метод решения блоч-но-треугольной системы линейных уравнений, так как граф этого метода имеет наименьшую среднюю степень параллелизма, что опять же приводит к очень плохой балансировке загрузки процессоров. [15]
Страницы: 1 2 3 4