4. Алгоритм характеризуется тем, что для частичной суммы и для регистра множимого используются регистры двойной разрядности, а для множителя - одинарной, равной N. Кроме этого, значение множимого записывается в старшую часть регистра, с тем, чтобы вести его сдвиг в сторону младших разрядов, постепенно уменьшая его значение. Анализ разрядов множителя ведется, начиная со старших. Результат хранится в регистре частичной суммы.
Пусть А – множимое, В – множитель, D – частичная сумма.
Пример:
Пусть A = 610 = 011000002 (множимое);
B = 310 = 00112 (множитель);
D = 000000002 (частичная сумма)
№ такта | Действие | Флаг [C] | |
Сдвиг A вправо | D = 00110000|0 | ||
Сдвиг В влево | B = 0|0110 | ||
Сдвиг A вправо | D = 00011000|0 | ||
Сдвиг В влево | B = 0|1100 | ||
Сдвиг A вправо | A = 00001100|0 | ||
Сдвиг В влево | B = 1|1000 | ||
[C] = 1, след. Прибавляем множимое к частичной сумме | D = D + A | ||
Сдвиг A вправо | D = 00000110|0 | ||
Сдвиг В влево | B = 1|0000 | ||
[C] = 1, след. Прибавляем множимое к частичной сумме | D = D + A |
Результат в D: 00010010. Нетрудно видеть, что 000100102 = 1810.