Элективный курс для предпрофильной подготовки девятиклассников «Машинная арифметика»

Умножение целых чисел

Простейший способ умножения целых беззнаковых чисел X×Y=Z есть суммирование множимого X с накоплением его столько раз, сколько единиц содержит значение множителя Y. Этот способ требует при больших значениях Y значительных затрат времени на выполнение многократных операций сложения, и поэтому применение его в компьютерах ограниченно.

Сокращение количества операций сложения при реализации умножения основано на методах совместного анализа цифр множителя. Эти методы дробят процесс получения произведения на ряд шагов, связанных с формированием частичных произведений (ЧП) – произведений множимого на отдельные разряды или группы разрядов множителя – и их суммированием, то есть формированием суммы частичных произведений (СЧП).

Методы умножения двоичных беззнаковых чисел основаны на представлении произведения в виде полинома:

где – двоичные цифры множителя, – частичные произведения (ЧП_i=X, если y_i=1, и ЧП_i=0, если y_i=0).

Заметим, что умножение на степень 2ⁱ эквивалентно сдвигу множимого на i разрядов влево.

Формирование произведения, согласно формуле (2), представляется как последовательность таких действий:

1. 
   обнуление СЧП;
   
2. 
   анализ младшего разряда множителя: если y₀=1, выполняется сложение ЧП₀=X с СЧП и переход к п.3; если y₀=0, сразу переход к п.3;
   
3. 
   сдвиг множимого влево;
   
4. 
   анализ очередного разряда множителя: если y₁=1, выполняется сложение ЧП₁∙2¹ с СЧП и переход к п.5; если y₁=0, непосредственно переход к п.5;
   
5. 
   сдвиг множимого влево;
   
6. 
   анализ очередного y₂ разряда множителя и т.д.
   

Рассмотрим на примере умножение двух целых беззнаковых чисел. Найдем произведение 45 и 29, пользуясь машинным алгоритмом. В десятичной системе счисления 45∙29=1305.

Переведем множимое и множитель в двоичную систему счисления: 45₁₀=101101₂, 29₁₀=11101₂.

Итак, результат произведения 10100011001₂=1305₁₀. То есть, можно сделать вывод, что алгоритм работает правильно.

Очевидно, что при работе с однобайтовыми беззнаковыми числами результат таковым не будет. Так как он занимает 11 разрядов. Можно предположить, что в разрядной сетке результата будет 00011001, то есть в 25₁₀. Проведем машинный эксперимент. Действительно, при отключенной проверке выхода результата за разрядную сетку, на экран выводится 25.

Упражнение 19. Напишите программу на Паскале, имитирующую процесс умножения двух целых беззнаковых чисел.

Решение.

temp,k: byte;

a,b,n,res:word;

begin

readln(a,b);{Ввод множимого и множителя}

res:=0; {Сумма частичных произведений}

k:=0; {Счетчик шагов, битов}

n:=1; {Переменная для вычисления значения очередного бита}

while k<=7 do {Пока не просмотрены все биты множителя b}

begin

temp:=n and b; {Находим значение очередного бита}

then res:=res+a; {очередное частичное произведение}

a:=a shl 1; {Сдвигаем множимое на один бит влево}

n:=n*2; {Будем рассматривать очередной бит}

k:=k+1;

end;

end.

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

Пусть целые двоичные сомножители X и Y представлены в дополнительном коде в n-разрядном формате, старший разряд которого используется для представления знака. При умножении этих чисел возможны четыре ситуации:

1. 
   X>0, Y>0. Так как D(X, n)=X и D(Y, n)=Y, то D(X Y, n)=X Y, то есть результат умножения совпадает с произведением беззнаковых чисел.
   
2. 
   X<0, Y>0. Согласно формуле (1), D(X<0, n)= 2ⁿ+X, и произведение, полученное методом умножения беззнаковых чисел, - псевдопроизведение – равно . Правильный же результат равен . Очевидно, что для получения правильного результата из псевдопроизведения необходимо к последнему прибавить 2²ⁿ (эту операцию практически не надо выполнять, так как данное число выходит за рамки формата произведения) и вычесть множитель , то есть вычесть множитель, сдвинутый влево на n разрядов.
   
3. 
   X>0, Y<0. Эта ситуация аналогична предыдущей. Для получения правильного произведения необходимо вычесть множимое, сдвинутое влево на n разрядов.
   
4. 
   X<0, Y<0. Так как D(X<0, n)=2ⁿ+X и D(Y<0, n)=2ⁿ+Y, то псевдопроизведение равно , а правильное произведение . Следовательно, для получения правильного произведения из псевдопроизведения необходимо вычесть число , то есть вычесть и множитель и множимое, сдвинутые предварительно на n разрядов влево.
   

Решение.

1. 
   При умножении двух положительных знаковых чисел, алгоритм полностью совпадает с алгоритмом умножения беззнаковых чисел. См. примеры выше.
   
2. 
   Пусть X= -5, а Y=32. Дополнительный код числа X равняется D(X, 8)=11111011, Y=00100000. Тогда псевдопроизведение равно:
   

3. 
   Данный случай решается аналогично предыдущему.
   
4. 
   Пусть X= -5, а Y= -32. Тогда D(X, 8)=11111011, D(Y, 8)=11100000. Отсюда, псевдопроизведение равно:
   

Над множеством целых чисел со знаком операция деления не определена, поскольку в общем случае ее результатом будет вещественное число. Однако допустимыми являются операции целочисленного деления и нахождения остатка от целочисленного деления (те, что в паскале обозначаются div и mod). Точнее, значения обеих величин находятся одновременно в одной процедуре, которая в конечном счете сводится к последовательности вычитаний или, еще точнее, сложений с дополнительным кодом делителя.

a,b,ost,chast: word;

begin

writeln('Введите делимое и делитель a и b');

ost:=a; {Остаток от деления}

chast:=0; {Целочисленное частное}

While ost>=b do {Пока остаток от деления больше делителя}

begin

chast:=chast+1; {Увеличиваем частное на единицу}

end;

writeln('Остаток при целочисленном делении равен',ost);

end.