Перший основний алгоритм множення

Використовує добуток Z=X*Y у вигляді

Z=X*Y=х_n∙2^-n∙Y+ х_n-1∙2^-n∙Y+…+ х₂∙2^-n∙Y+ х₁∙2^-n∙Y=

((…((0+ х_n∙Y)∙2^-1+ х_n-1∙Y)∙2^-1+…+x₂∙Y)∙2^-1+x₁∙Y)∙2^-1

Звідси слід, що добуток Z за допомогою рекурентної формули можна записати

де Z₀ = 0; Z_n = Z, Z_i – сума часткових добутків.

Граф-схема алгоритму (ГСА) такого множення має вигляд:

Множення тут починається з молодших розрядів множника, на кожному кроці множення сума часткових добутків зсувається вправо, кількість кроків множення дорівнює n, останній крок закінчується зсувом.   xn* – цифра в молодшому розряді регістру множника РХ на даному кроці множення (“поточна” цифра множника)   СТК – лічильник числа кроків множення.   Довжина регістрів операндів складає n – розрядів, регістрів результату – 2n розрядів.

Приведемо цифрову діаграму станів регістрів при множенні чисел Х = 11/16 та Y = 9/16, n = 4 відповідно схемі алгоритму.

PX xn*	PY		PZ	СТК	Пояснення
		+		END	Початковий стан +Y Результат сумування Зсув +Y Результат сумування Зсув Зсув +Y Результат сумування Зсув
+
+

Другий основний алгоритм множення

Операція множення по другому алгоритму зводиться до обчислювання за рекурентною формулою

де

ГСА такого множення має вигляд:

Регістр множника повинен мати довжину в n розрядів, регістри множеного та суми часткових добутків – по 2n розрядів.   Перед початком множення множене повинно бути записано в відповідний регістр зі зсувом вправо на n розрядів для того, щоб було сформовано значення Yn.   Початкове встановлення лічильника в одиницю зумовлене тим, що значення Yn вже сформовано при запису його в регістр множеного.

Приведемо приклад цифрової діаграми множення чисел Х = 13/16 та Y = 12/16, n = 4.

PX xn*	PY		PZ	СТК	Пояснення
		+		END	Початковий стан +Y Результат сумування Зсув Зсув +Y Результат сумування Зсув +Y Результат сумування
+
+

Третій основний алгоритм множення

Третій основний алгоритм множення Z= X*Y можна отримати за рекурентною формулою добутку

Z_i = Z_i-1 2 + x_i 2 ^{– n} Y, i = де Z₀ = 0, Z_n = Z.

 

 

ГСА алгоритму має вигляд:

В відповідності з цією формулою множення починається зі старших розрядів множника, сума часткових добутків зсувається вліво, число кроків множення дорівнює n, закінчується виконання алгоритму додаванням.   Довжину в 2n розрядів повинен мати тільки регістр PZ.   Проте оскільки зсуви в РХ та PZ виконуються в одну й ту ж сторону, то в варіантах цього алгоритму старші розряди добутку можна заносити в регістр РХ.

Приклад цифрової діаграми множення чисел Х=11/16 та Y=10/16, n=4

x1*PX	PY	PZ	СТК	Пояснення
			END	Початковий стан +Y Результат сумування Зсув Зсув +Y Результат сумування Зсув +Y Результат сумування