Каким образом в компьютере реализуется операция умножения

Обновлено: 06.07.2024

Хочу рассказать читателям о программистском трюке, с которым я познакомился в какой-то переводной книжке, содержащей подборку таких трюков, в те далёкие времена, когда ещё не изобрели не то что байт, а страшно сказать — стек, а великий Дейкстра ещё не проклял оператор GOTO (sic, in uppercase).

Трюк настолько мне понравился простотой и изяществом, что уже в этом тысячелетии я с удовольствием рассказывал о нём студентам в виде следующей задачи.

Представьте себе, что в процессе возвращения в 2030 году с Луны вы вдруг обнаружили, что ваш бортовой компьютер неправильно выполняет операции целочисленного умножения, и это непременно приведёт к аварии при посадке.

В таком сюжете нет ничего особо фантастического. Вспомним, например, какие проблемы случались когда-то с процессорами Pentium , а к моменту отправки на Луну вы ещё не достигли полного импортозамещения. И вообще надо проверить, а не были ли процессоры просверлены специально.

Но к делу. Вам надо срочно реализовать умножение программно, чтоб работало быстро в реальном времени и укладывалось в доступный ресурс.

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

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

Если, наоборот, взять цифры длинные (например от 0 до 65535), то для 16-битной арифметики
результат берётся прямо из таблицы, а столбики отсутствуют. Однако размер классической таблицы Пифагора при этом оказывается около 17GB (4*65536*65536), если учесть симметрию относительно диагонали, то половина — около 8.5GB.

Может оказаться многовато.

Напрягаемся и вспоминаем алгебру.

Вычитаем (2) из (1)

Таким образом, имея таблицу квадратов в массиве sqr, получаем

a * b = ( sqr[a + b] — sqr[a — b]) / 4 (*)

Размер таблицы 8*(65535+65535) около 8.4MB, что уже может оказаться приемлемым.

Размер элемента таблицы в 8 байт связан с тем, что при максимальных a и b квадрат их суммы в 4 байта не влезает — не хватает 2-х бит.

Далее опишу некоторое улучшение, которого в книжке не было. Его я придумал сам, когда уже писал эту заметку.

Заметим, что два младших бита квадрата чётного числа всегда 00, а квадрата нечётного — всегда 01. С другой стороны для любой пары чисел их сумма и разность имеют одинаковую чётность.
Поэтому в нашей формуле (*) процесс вычитания в скобках не может иметь переносов,
связанных с двумя младшими битами. Поэтому содержимое элементов таблицы квадратов
можно заранее сдвинуть на два бита вправо и тем самым сэкономить половину памяти.

a * b = sqr4[a + b] — sqr4[a — b] (**)

где sqr4 — модифицированная таблица квадратов.

В нашем примере её размер около 4.2 MB.

Ниже для иллюстрации этого подхода включен текст программы на языке Lua.

Тема реферата «Выполнение операций умножения и деления в ЭВМ».

Цель работы – ознакомится с выполнением операций умножения и деления в ЭВМ, как с фиксированной, так и с плавающей запятой.
1. Выполнение операции умножения в ЭВМ

Операция умножения является наиболее частой после сложения. Умножение может выполняться суммированием сдвинутых на один или несколько разрядов частичных произведений, каждое из которых является результатом умножения множимого на соответствующий разряд (разряды) множителя.

При точном умножении двух чисел количество значащих цифр произведения может в пределе достичь двойного количества значащих цифр сомножителей. Еще сложнее возникает ситуация при умножении нескольких чисел. Поэтому в произведении только в отдельных случаях используют двойное количество разрядов.

Наиболее просто операция умножения выполняется в прямом коде. При этом на первом этапе определяется знак произведения путем сложения знаковых разрядов сомножителей по модулю 2, затем производится перемножение модулей сомножителей согласно двоичной таблице умножения. Результату присваивается полученный знак.

Так как умножение производится в двоичной системе счисления, частные произведения либо равны 0 (при умножении на 0), либо самому сомножителю (при умножении на 1), сдвинутому на соответствующее количество разрядов.

Произведение можно получить двумя путями:

1) сдвигом множимого на требуемое количество разрядов и прибавлением полученного очередного частичного произведения к ранее накопленной сумме частичных произведений;

2) сдвигом суммы ранее полученных частичных произведений на каждом шаге на 1 разряд и последующим прибавлением к сдвинутой сумме неподвижного множимого либо 0.

Причем каждый из этих методов может различаться еще и тем, с младших или со старших разрядов начинается умножение.

1а) 0,1101 1б) 0,1101

Основываясь на вышеизложенном можно создать 4 основных метода машинного умножения в прямом коде:

1) умножение младшими разрядами множителя со сдвигом накапливаемой суммы частных произведений вправо;

2) умножение младшими разрядами множителя со сдвигом множимого влево;

3) умножение старшими разрядами множителя со сдвигом накапливаемой суммы частных произведений влево;

4) умножение старшими разрядами множителя со сдвигом множимого вправо;

Рассмотрим более детально каждую из схем умножения.

1) умножение младшими разрядами множителя со сдвигом накапливаемой суммы частных произведений вправо.

Алгоритм получения результата по данному методу может быть следующим:

1) содержимое сумматора обнуляется;

2) множимое умножается на очередной разряд множителя;

3) результат суммируется с содержимым сумматора;

4) содержимое сумматора сдвигается на 1 разряд вправо;

5) пункты 2, 3, 4 повторяются n-1 раз.

Заданы операнды А=0,0101; В=0,1011, выполнить операцию умножения.

2) умножение младшими разрядами множителя со сдвигом множимого влево.

Алгоритм получения результата по данному методу может быть следующим:

1) содержимое сумматора обнуляется;

2) множимое умножается на очередной разряд множителя;

3) результат суммируется с содержимым сумматора;

4) множимое сдвигается на 1 разряд влево;

5) пункты 2, 3, 4 повторяются n-1 раз.

Выполнение умножения по 3-му и 4-му способам умножения можно рассмотреть по аналогии к выше рассмотренным способам.

Анализ приведенных схем умножения показывает, что длительность процесса умножения по любой схеме составляет n циклов:

2) по количеству оборудования предпочтение следует отдать первой, а потом третьей схеме умножения.

Наиболее удобными для применения в ЭВМ являются 1 и 4 схемы умножения.

2. Умножение чисел, представленных в форме с плавающей запятой

Если операнды заданы в форме с плавающей запятой:

А=a2 ma и B=b2 mb , то их произведение С=АхВ и С=с2 mc

Алгоритм умножения нормализованных чисел состоит из следующих этапов:

1. Определение знака произведения путем сложения знаковых разрядов мантисс операндов по модулю 2.

2. Алгебраическое сложение порядков сомножителей в с целью определения порядка произведения.

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

4. Нормализация и округление мантиссы результата. Следует учесть, что мантиссы сомножителей являются нормализованными числами. Поэтому денормализация мантиссы произведения возможна только на один разряд вправо. Она устраняется путем сдвига мантиссы на один разряд влево и вычитания 1 из порядка результата.

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

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

Наиболее просто операция умножения выполняется в ПК, при этом на первом этапе определяется знак произведения путем сложения знаковых цифр сомножителей по модулю два.

Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения Р(р_2n-1, p_2n-2, …, p₁, p₀) двух n-разрядных двоичных чисел без знака А(a_2n-1, a_2n-2, …, a₁, a₀) и В(b_2n-1, b_2n-2, …, b₁, b₀) сводится к формированию частичных произведений (ЧП) W_i (по одному на каждую цифру множителя) с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего согласно весу цифры множителя, которой это ЧП соответствует. Поскольку операндами являются двоичные числа, вычисление ЧП упрощается: если цифра множителя b_i равна 0, то W_i тоже равно 0, а при b_i = 1 частичное произведение равно множимому (W_i=А). Перемножение двух п-разрядных двоичных чисел Р = АВ приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций - сложения и сдвига (рис. 3.1).

Рис. 3.1. Общая схема умножения со сдвигом суммы частичных произведений влево или вправо

Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Согласно данной схеме устройство умножения предполагает наличие регистров множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига, если операция сдвига не реализована иным способом, например, за счет «косой» передачи данных между узлами умножителя.

В зависимости от способа получения суммы частичных произведений (СЧП) возможны четыре варианта реализации «традиционной» схемы умножения [10]:

Рис. 3.1. Общая схема умножения со сдвигом суммы частичных произведений влево или вправо

Читайте также: