Умножение чисел в формате с фиксированной запятой без знака
По сравнению со сложением и вычитанием, умножение – более сложная операция, как при программном, так и при аппаратном воплощении. В ВМ применяются различные алгоритмы реализации операции умножения.
Умножение производится согласно таблице умножения, которая для двоичных чисел имеет вид:
Рассмотрим пример:
Таким образом, умножение двоичных чисел сводится к операциям сдвига на один двоичный разряд влево и повторения первого сомножителя в тех разрядах, где второй сомножитель содержит 1, и сдвига без повторения в разрядах с 0. Сдвиг всегда чередуется со сложением, поскольку для выполнения операций имеется всего два регистра (два места для записи чисел). Другими словами, реализации отдельной операции умножения в процессоре не требуется.
Как и в операции сложения, при умножении чисел с ограниченной разрядной сеткой может возникнуть переполнение. Решается проблема рассмотренными выше способами.
Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения двух n-разрядных двоичных чисел без знака сводится к формированию частичных произведений (ЧП) по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего. Перемножение двух n-разрядных двоичных чисел P=A*B приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций – сложения и сдвига. Суммирование ЧП обычно производится нена завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Устройство умножения предполагает наличие регистров множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига (если операция сдвига не реализована иным способом).
Существуют алгоритмы умножения:
§ Алгоритм сдвига вправо - начиная с младших разрядов множителя, со сдвигом суммы ЧП вправо и при неподвижном множимом.
§ Алгоритм сдвига влево - начиная со старших разрядов множителя, со сдвигом суммы ЧП влево и неподвижном множимом.
1. | Алгоритм сдвига вправо Алгоритм сводится к следующим шагам: | ![]() |
1. | Исходное значение суммы ЧП принимается равным нулю; | |
2. | Анализируется очередная цифра множителя (начиная с младшего разряда). Если она равна единице, то к СЧП прибавляется множимое, иначе – прибавление не производится. | |
3. | Выполняется сдвиг суммы частичных произведений вправо на один разряд. | |
4. | Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя. |
2. | Алгоритм сдвига влево Алгоритм сводится к следующим шагам: | ![]() |
1. | Исходное значение суммы ЧП принимается равным нулю; | |
2. | Выполняется сдвиг суммы частичных произведений влево на один разряд. | |
3. | Анализируется очередная цифра множителя (анализ начинается со старшей цифры разряда). Если она равна единице, то к СЧП прибавляется множимое, иначе – прибавление не производится. | |
4. | Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя. |