Умножение чисел в формате с фиксированной запятой без знака

По сравнению со сложением и вычитанием, умножение – более сложная операция, как при программном, так и при аппаратном воплощении. В ВМ применяются различные алгоритмы реализации операции умножения.

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

Рассмотрим пример:

Таким образом, умножение двоичных чисел сводится к операциям сдвига на один двоичный разряд влево и повторения первого сомножителя в тех разрядах, где второй сомножитель содержит 1, и сдвига без повторения в разрядах с 0. Сдвиг всегда чередуется со сложением, поскольку для выполнения операций имеется всего два регистра (два места для записи чисел). Другими словами, реализации отдельной операции умножения в процессоре не требуется.

Как и в операции сложения, при умножении чисел с ограниченной разрядной сеткой может возникнуть переполнение. Решается проблема рассмотренными выше способами.

Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения двух n-разрядных двоичных чисел без знака сводится к формированию частичных произведений (ЧП) по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего. Перемножение двух n-разрядных двоичных чисел P=A*B приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций – сложения и сдвига. Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Устройство умножения предполагает наличие регистров множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига (если операция сдвига не реализована иным способом).

Существуют алгоритмы умножения:

§ Алгоритм сдвига вправо - начиная с младших разрядов множителя, со сдвигом суммы ЧП вправо и при неподвижном множимом.

§ Алгоритм сдвига влево - начиная со старших разрядов множителя, со сдвигом суммы ЧП влево и неподвижном множимом.

1.	Алгоритм сдвига вправо Алгоритм сводится к следующим шагам:	10х11=110(10)
1.	Исходное значение суммы ЧП принимается равным нулю;
2.	Анализируется очередная цифра множителя (начиная с младшего разряда). Если она равна единице, то к СЧП прибавляется множимое, иначе – прибавление не производится.
3.	Выполняется сдвиг суммы частичных произведений вправо на один разряд.
4.	Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя.

2.	Алгоритм сдвига влево Алгоритм сводится к следующим шагам:
1.	Исходное значение суммы ЧП принимается равным нулю;
2.	Выполняется сдвиг суммы частичных произведений влево на один разряд.
3.	Анализируется очередная цифра множителя (анализ начинается со старшей цифры разряда). Если она равна единице, то к СЧП прибавляется множимое, иначе – прибавление не производится.
4.	Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя.