Перший основний алгоритм множення
Використовує добуток Z=X*Y у вигляді
Z=X*Y=хn∙2-n∙Y+ хn-1∙2-n∙Y+…+ х2∙2-n∙Y+ х1∙2-n∙Y=
((…((0+ хn∙Y)∙2-1+ хn-1∙Y)∙2-1+…+x2∙Y)∙2-1+x1∙Y)∙2-1
Звідси слід, що добуток Z за допомогою рекурентної формули можна записати
де Z0 = 0; Zn = Z, Zi – сума часткових добутків.
Граф-схема алгоритму (ГСА) такого множення має вигляд:
Множення тут починається з молодших розрядів множника, на кожному кроці множення сума часткових добутків зсувається вправо, кількість кроків множення дорівнює 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 можна отримати за рекурентною формулою добутку
Zi = Zi-1 2 + xi 2 – n Y, i = де Z0 = 0, Zn = Z.
ГСА алгоритму має вигляд:
В відповідності з цією формулою множення починається зі старших розрядів множника, сума часткових добутків зсувається вліво, число кроків множення дорівнює n, закінчується виконання алгоритму додаванням. Довжину в 2n розрядів повинен мати тільки регістр PZ. Проте оскільки зсуви в РХ та PZ виконуються в одну й ту ж сторону, то в варіантах цього алгоритму старші розряди добутку можна заносити в регістр РХ. |
Приклад цифрової діаграми множення чисел Х=11/16 та Y=10/16, n=4
x1*PX | PY | PZ | СТК | Пояснення |
END | Початковий стан +Y Результат сумування Зсув Зсув +Y Результат сумування Зсув +Y Результат сумування | |||