Умножение чисел со старших разрядов в прямом коде
Пусть два числа X и Y представлены с фиксированной запятой в виде:
[X]пк = sign X.x1x2...xn – множимое [Y]пк = sign Y.y1y2...yn – множитель
Представим множитель в виде:
[Y]пк = sign Y. (y1*2-1 + y2*2-2 + ... + yn*2-n)
Тогда:
[Z]пк = [X]пк*[Y]пк = sign Z. |X| (y1*2-1 + y2*2-2 + ... + yn*2-n) = = sign Z. (|X|*y1*2-1 + |X|*y2*2-2 + ... + |X|*yn*2-n) = = sign Z. (|X|*2-1*y1 + |X|*2-2*y2 + ... + |X|*2-n*yn)
Это есть аналитическая запись алгоритма умножения двух чисел, начиная со старших разрядов множителя.
Алгоритм:
Множимое сдвигается вправо на 1 разрядАнализируется цифра множителя. Если она – нуль, то частичное произведение не суммируется, а если она – единица, то частичное произведение добавляется к общему результату.Последовательность операций по пунктам 1 и 2 продолжается "n" раз.
Знак произведения находится независимо от получения цифровой части по формуле:
sign Z = sign X
Пример:
Видно, что в общем случае нужно иметь для точного результата сетку с числом разрядов, равным сумме разрядностей сеток сомножителей.
Если нужно получать произведение с точностью не хуже, чем 2-n, то достаточно иметь не удвоенную величину разрядной сетки, а лишь увеличенную на
d = log2n разрядов
Умножение с младших разрядов в дополнительном коде
Алгоритм:
[Z]дк = (...(0+[X]дк*[yn+1 – yn])*2-1 + [X]дк*[yn – yn-1])*2-1 + ... ... + [X]дк*[y2 – y1])*2-1 + [X]дк*[y1 – y0]
Если yn = yn+ 1 , то производится сдвиг частичного произведения.
Если yn = 0 и yn+1 = 1, то к частичному произведению прибавляется [X]дк
Если yn = 1 и yn+1 = 0, то из частичного произведения вычитается [X]дк.
Пример:
Умножение с младших разрядов в прямом коде
Напишем выражение для произведения двух чисел в несколько изменённом виде, а именно:
[Z]пк = [X]пк*[Y]пк = = sign Z.(|X|*y1*2-1 + |X|*y2*2-2 +... + |X|*yn*2-n ) = = sign Z.( |X|*2-1*y1 + 2-1 (|X|*2-1*y2 + 2-1 (|X|*2-1*y3 + (...)))) = = sign Z. ((...(( |X|*yn*2-1 + |X|*yn-1 )2-1 + |X|*yn-2 )2-1 + ... + + |X|*y2 )2-1 + |X|*y1 )*2-1
Это выражение называется преобразованием по схеме Горнера и задаёт алгоритм умножения с младших разрядов множителя.
Таким образом, для умножения должна выполняться следующая последовательность действий:
Анализируется младшая цифра множителя. Если она равна "1", то множимое участвует в формировании части произведения. В противном случае – не участвует.Полученное частичное произведение сдвигается вправо на 1 разряд.Операции по пунктам 1 и 2 выполняются до старшего разряда.
Пример:
signZ= 1
Умножение со старших разрядов в дополнительном коде
[Z]дк = [X]дк*[Y]дк = [X]дк*(y1 – y0 ) + [X]дк*(y2 – y1 )*2-1 + ... + + [X]дк*(yn+1 – yn )*2-n
[-X]дк = 1.01011 [Z]дк = [-X]дк + [X]*2-1 + [X]дк*2-2*0 + [-X]дк*2-3 + + [X]дк*2-4 + [-X]дк*2-5
+1.01011 [-X]дк 0.010101 [X]дк*2-1
________ +1.101011 1.11101011 [-X]дк*2-3
__________ +1.10010111 0.000010101 [X]дк*2-4
___________ +1.101000011 1.1111101011 [-X]дк*2-5
____________ 1.1001110001 Ответ: [Z]дк = 1.1001110001
с точностью не ниже, чем
Для получения произведения с точностью не ниже, чем 2-n нужно иметь только "n"– разрядную сетку.
Итак, видим, что для получения произведения как при умножении со старших,так и младших разрядов необходимо выполнять две микрооперации: суммирование чисел в позиционной системе счисления и сдвига.
Однако, известно, что числа могут быть представлены в различных кодах(это, прежде всего, отрицательные числа).
Мы уже знаем, как выполняется операция суммирования чисел (в том числе и с разными знаками).
Однако микрооперация сдвига имеет некоторые особенности:
Сдвиг вправо:
Сдвиг влево возможен только в случае, если сдвинутое число меньше единицы по модулю:
Исходные числа:
