Каким образом в компьютере реализуется операция умножения
Хочу рассказать читателям о программистском трюке, с которым я познакомился в какой-то переводной книжке, содержащей подборку таких трюков, в те далёкие времена, когда ещё не изобрели не то что байт, а страшно сказать — стек, а великий Дейкстра ещё не проклял оператор 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.
Операция умножения двоичных целых чисел, представленных в форме с фиксированной точкой, приводит к формированию в АЛУ компьютера произведения, имеющего двойную длину по сравнению с множителями.
Для реализации умножения необходимо иметь регистры множимого и множителя, а также сумматор, в котором производится последовательное суммирование частных произведений. Для (n-1) – разрядных сомножителей операция умножения состоит из (n-1) циклов. В каждом цикле инициализируется очередная цифра множителя. Если это единица, то к содержимому сумматора частичных произведений добавляется множимое, в противном случае (очередная цифра нуль) прибавление не производится. При этом множитель и сумма частичных произведений сдвигаются на один разряд вправо относительно неподвижного множителя.
Поскольку, по мере сдвига множителя, старшие разряды регистра множителя освобождаются, они могут быть использованы для хранения младших разрядов произведения, поступающих из сумматора частных произведений в процессе выполнения умножения. Для этого младший разряд сумматора частичных произведений соединяется со старшим разрядом регистра множителя. После завершения операции умножения старшие разряды произведения находятся в регистре сумматора, а младшие – в регистре множителя. На рис. 4.3 приведен алгоритм умножения чисел А и В. Здесь логическая операция AND с константой 1 позволяет выделить младший разряд множителя с целью формирования определенного частичного произведения. SHR – сдвиг множителя на один разряд вправо.
Рис. 4.3 Алгоритм умножения чисел А и В
Правило перемножения целых двоичных чисел очень похоже на перемножение в столбик. Пусть заданы множимое А=и множитель В=. Перемножение их по известным правилам арифметики имеет вид
Поскольку , то полученный результат является верным. Для выполнения этой операции в компьютере используются трехразрядные регистры множимого, множителя и сумматора частичных произведений. Сдвиг множимого А и суммы частичных произведений S производится вправо. По мере выполнения операций умножения младшие разряды суммы частичных произведений S перемещаются в старшие (освобождающиеся) разряды регистра множителя. Последовательность операций имеет вид, представленный в нижеприведенной таблице.
В итоге получен тот же результат, что и перемножении вручную, то есть А*В = .
Сдвиг в компьютере суммы частичного произведения вправо, а не сдвиг множителя влево, как это делается при перемножении вручную, производится из соображений упрощения технической реализации. При этом, как видно из примера, результат остается неизменным.
Операции | Разряд множителя В | Реализация |
S – 0 | 0 0 0 + 1 1 0 | |
S = S + A | ||
S | 1 1 0 | |
SHR 1 | 0 1 1 0 | |
SHR 1 | 0 0 1 1 0 + 1 1 0 | |
S = S + A | ||
S | 1 1 1 1 0 |
Умножение чисел с различными знаками можно свести к перемножению их модулей с последующим формированием знакового разряда произведения. Произведению устанавливается знак плюс, если знаки чисел одинаковы и знак минус, если знаки чисел различны.
Кроме того, в компьютере есть возможность выполнять операции умножения чисел, представленных их кодами. При этом, положительные множители представляются в прямом коде, а отрицательные – в дополнительном. Если множители имеют одинаковые знаки, то произведение представляется в прямом коде, если же знаки различны, то произведение представляется в дополнительном коде.
Принципы реализации операции умножения чисел, представленных в форме с фиксированной точкой аналогичны, с той лишь разницей, что при этом добавляется операция определения порядка произведения (алгебраического сложения порядков сомножителей) и проводится, если необходимо, нормализация результирующей мантиссы с соответствующим изменением порядка произведения.
Если при суммировании порядков возникло переполнение, и порядок произведения получился отрицательным, то это означает, что искомое произведение оказалось меньше минимально представленного в компьютере числа, и тогда в качестве результата операции может быть записан нуль без перемножений мантисс множителей. Если же возникло переполнение для положительного порядка, то результат при этом может все-таки находиться в диапазоне чисел, представляемых в компьютере. Это объясняется тем, что при умножении мантисс происходит нарушение нормализации вправо, поэтому после нормализации мантиссы переполнение в порядке произведения исчезает.
Операция деления чисел, представляемых в форме с фиксированной точкой, сводится к многократным вычитаниям и сдвигам. При этом разряды частного, начиная со старшего, определяются последовательным вычитанием делителя сначала из делимого, а затем из образующихся в процессе деления сдвигаемых остатков. Если разность между делимым (или очередным остатком) и делителем положительная или равна нулю, то в соответствующий разряд частного записывается единица, а если отрицательная – нуль. Поскольку в компьютере операция вычитания в непосредственном виде не выполняется, то последовательное вычитание заменяется сложением остатков с дополнительным кодом делителя. При этом новый остаток также получается в соответствующем коде.
В компьютере делимое в форме с фиксированной точкой представляется с удвоенным количеством разрядов по сравнению с делителем и частным.
4.4. Кодирование алфавитно – цифровой информации
Современные компьютеры обрабатывают не только цифровую, но и текстовую информацию. Иначе говоря, алфавитно – цифровую информацию, содержащую цифры, буквы, знаки препинания, математические и другие символы.
В настоящее время широкое распространение получило кодирование символов с использованием однобайтовых ячеек памяти, которая может содержать 256 различных вариантов информации, отвечающей тому или иному символу. Это в полной мере перекрывает количество символов, содержащихся в алфавитах различных языков. Принцип кодирования символов состоит в том, что каждому символу в соответствии с принятой таблицей кодов ASCII соответствует определенное десятичное число. Затем это число переводится в двоичное. Например, выражение USSR 1917 будет храниться в памяти в восьми байтах
Умножение двоичных чисел состоит в последовательном умножении множимого на отдельные разряды множителя с суммированием результатов умножения. Результат умножения множимого на один разряд множителя принято называть частным произведением.
Первый способ: 1 1 0 1
1 0 0 0 1 1 1 1 (143)10
Второй способ: 1 1 0 1
_________ 1 1 0 1
1 0 0 0 1 1 1 1
Особенности операций умножения целых чисел:
• каждое частное произведение либо совпадает с множимым, либо равно нулю;
• формируемые частные произведения должны быть определенным образом сдвинуты друг относительно друга для их последующего суммирования;
• частное произведение можно формировать, начиная как от младших, так и от старших разрядов множителя;
• в общем случае для результата умножения требуется количество цифр, равное сумме количества цифр операндов. Если операнды имеют одинаковое количество цифр, то для суммы потребуется 2n разрядов.
Особенности реализации операций умножения в ЭВМ:
1.В операционном устройстве для умножения двоичных чисел должен использоваться многоразрядный двоичный сумматор, поэтому умножение реализуется в виде последовательного многошагового процесса, на каждом шаге которого проводится умножение на один разряд множителя. Для фиксации суммы частных произведений необходимо использовать 2n-разрядный регистр при n-разрядных операндах. Перед началом операции этот регистр необходимо обнулить;
2.На каждом шаге умножения анализируется определенный разряд множителя. Если он равен 1, то на этом шаге проводится сложение суммы частных произведений с множимым. Если разряд равен 0, то сложение не проводится;
3.Каждый шаг умножения должен сопровождаться сдвигом суммы частных произведений (СЧП) относительно неподвижного множимого, или наоборот: сдвиг множимого относительно неподвижной СЧП;
4.Умножение можно начинать как с младших, так и со старших разрядов множителя;
5.В целях упрощения схемы умножения регистр множителя реализуется как сдвигающий, это дает возможность анализировать только один разряд регистра. При выполнении умножения, начиная от младших разрядов, схема анализа привязывается к младшему разряду регистра множителя, регистр при этом сдвигается вправо;
При реализации умножения, начиная от старших разрядов, схема анализа привязывается к старшему разряду множителя, реализуется сдвиг вправо.
6.Для фиксации момента завершения операции в операционном устройстве умножения должен быть использован суммирующий или вычитающий счетчик, который считает количество разрядов множителя;
7.Так как возможно умножение, начиная от старших и с младших разрядов (то есть сдвигается множимое или сумма частных произведений), то можно использовать четыре способа (схемы) умножения.
Способы (схемы) реализации умножения в ЭВМ
• начиная от младших разрядов множителя со сдвигом множимого влево;
• начиная от младших разрядов со сдвигом СЧП вправо;
• начиная от старших разрядов со сдвигом множимого вправо;
• начиная от старших разрядов со сдвигом СЧП влево.
Анализ схем
1. В схемах умножения со сдвигом множимого для его представления требуется два n-разрядных регистра.
2. Для схем умножения со сдвигом СЧП для представления множимого требуется n-разрядный регистр.
3. В схемах умножения, начиная от старших разрядов со сдвигом множителя вправо, необходимо использовать 2n-разрядный регистр.
4. Для схем умножения, начиняя от старших разрядов со сдвигом СЧП влево, требуется 2n-разрядный регистр для хранения суммы СЧП.
5. Для схем умножения, начиная от младших разрядов со сдвигом СЧП вправо, требуется n-разрядный регистр.
В целях экономии оборудования практически во всех ЭВМ реализована схема умножения, начиная от младших разрядов множителя со сдвигом СЧП вправо. Упрощенная схема операционного устройства для реализации умножения по этому способу представлена на рисунке.
Умножения чисел с фиксированной запятой
Задание:
1) В разрядной сетке длиной в байт (один разряд знаковый и семь – цифровых) выполнить операцию умножения заданных чисел А и В со всеми комбинациями знаков, используя метод умножения в дополнительных кодах с применением коррекции. При выполнении операции использовать способ умножения с поразрядным анализом множителя, начиная от его младших разрядов со сдвигом СЧП вправо. Результаты представить в десятичной системе и проверить их правильность.
2) В разрядной сетке длиной в байт (один разряд знаковый и семь – цифровых) выполнить операцию умножения заданных чисел А и В со всеми комбинациями знаков, используя метод умножения в дополнительных кодах без применения коррекции. При выполнении операции использовать способ умножения с поразрядным анализом множителя, начиная от его младших разрядов со сдвигом СЧП вправо. Результаты представить в десятичной системе и проверить их правильность.
Основные положения
Использование дополнительных кодов позволяет не переводить отрицательные числа в прямой код и отрицательный результат в дополнительный код.
Все операции с числами в ЭВМ реализуются в АЛУ (арифметико-логическом устройстве) процессора. Числа, которые участвуют в операциях, называются операндами. Главную роль в АЛУ играет «сумматор» в связи с тем, что все арифметические операции сводятся к простым элементарным действиям с прямыми, обратными и дополнительными кодами чисел. Основной операцией в сумматоре является сложение.
Прямой код числа – само исходное число.
Обратный код числа – инвертированный поразрядно прямой код , в этом случае производится замена 0→1, 1→0. Например, число в прямом коде 01102, а в обратном коде 10012
Дополнительный код образуется добавлением 1 к младшему разряду (крайнему справа) обратного кода.
1. Операция сложениядля положительных чисел заменяется поразрядным сложением операндов в прямых кодах.
Пример №1.1 012 + 012=102 или в десятичной системе счисления 1+1=2
Пример №1.2 000010112 + 000001102=? или в десятичной системе счисления 11+ 6=?
Первое слагаемое 00001011 (в прямом коде)
Второе слагаемое 00000110 (в прямом коде)
Результат сложения : 00001011
2. Операция вычитания для положительных чисел заменяется сложением операндов, причем второй операнд берется в дополнительном коде, т.е. А + В=А + (- В) , далее от полученного результата сложения в старшем (левом) разряде следует вычесть 1.
Пример № 2.1 10-7= 000010102-000001112=?
Переведем вычитаемое число 00000111 сначала в обратный код 11111000, а затем в дополнительный: 11111000+00000001=11111001 Теперь сложим уменьшаемое число ( в прямом коде) и вычитаемое (в дополнительном) коде:
100000011 Отбрасываем слева 1, тогда получим результат : 112=3
34 - 22 = 34 + (- 22) =12
Запишем этот пример в двоичном виде: 100010 - 010110 = 001100
Дополнительный код вычитаемого числа 10110 будет такой: 01001 + 00001 = 01010
Тогда исходный пример можно заменить сложением так 100010 + 01010 = 101100 Отбросим одну единицу в старшем разряде, получим 001100. Отбросим также незначащие нули слева и получим 11002=12, то есть пример решён правильно.
Решение: 1) Вычтем 1 из младшего разряда дополнительного кода, получим 101100102
2) Переведем полученный код числа в обратный код, получим 010011012
3) Переведем полученное двоичное число в десятичное, получим 77
3. Операция умножения двоичных чисел сводится к «школьному» умножению в столбик
Пример № 3.2. 1012 x1102=5 x 6=30
4. Операция деления двоичных чисел сводится к «школьному» делению, например:
|
Сначала мы записываем делимое. В данном случае это число 1000001 (в десятичном виде 65). Затем, справа от него, рисуем угол. В верхней части угла записываем делитель. В нашем случае – это 101 (десятичное 5). Затем мы начинаем находить частное поразрядно Нам придется лишь проверять не больше ли делитель, чем число, составляющее первые три разряда делимого. Как видим первые три разряда составляют число 100, что меньше, чем 101. Поэтому берем первые четыре разряда делимого. Число, составляющее первые четыре разряда делимого (1000) естественно больше делителя. Поэтому мы записываем делитель под первыми четырьмя разрядами делимого и вычитаем эти два числа. Операцию вычитания каждый раз заменяем сложением вычитаемого в дополнительном коде. Получаем разность 11. В первый разряд частного записываем 1. Находим следующий разряд частного. Для этого сносим следующий разряд делимого (так же, как это делается при делении в десятичной системе). Проверяем – можно ли теперь вычесть из него 101. Число 110 больше, чем 101. Поэтому мы записываем единицу в следующий разряд частного и производим вычитание этих двух чисел. Разность равна 1. Далее ищем третий разряд частного. Сносим еще один ноль с очередного разряда делимого. Но из числа 10 невозможно вычесть 101. 10 меньше, чем 101. Поэтому записываем в очередной разряд частного ноль и сносим последний разряд делимого. Теперь вычитание возможно. Более того, результат вычитания равен нулю. Это означает во-первых, что последний разряд частного равен единице, а во-вторых то, что число 1000001 поделилось на 101 без остатка. Результат деления равен 1101 (десятичное 13).
Помните, как в школе умножали "столбиком"? Скажем, числа 52 и 37 умножают так:
Умножение двузначных чисел мы свели 1) к умножению однозначных (оно короткое), 2) к сложению, 3) и еще к сдвигу, эта операция настолько проста, что мы её и не замечаем. Она соответствует умножению на степень десятки, и «почти бесплатна»:
Умножение двух двузначных чисел требует четырех коротких умножений.
Умножение двух трехзначных чисел требует девяти коротких умножений.
Умножение двух N -значных чисел сводится к N ² коротким умножениям (и ещё к сложениям и сдвигам).
Для компьютерных вычислений умножение – самая затратная по времени операция, а сложение и тем более сдвиг – нет; поэтому сложность алгоритма умножения длинных чисел оценивают числом коротких, «однозначных» умножений. (Внутри компьютера числа представляются не так, как в школьных тетрадках, основание счисления будет не 10, а какая-то степень двойки, но для оценки это непринципиально.)
Примерно в 1956 году А.Н.Колмогоров предположил, что алгоритм c N ² “однозначными” умножениями – наилучший из всех возможных. В его семинаре участвовал молодой математик Анатолий Карацуба, который и опроверг гипотезу учителя. В 1960 году он придумал алгоритм, который работает быстрее.
Через них получается выражение для
А это все, что нужно знать, чтобы вычислить произведение:
Нам потребовалось не N ² операций, а только
Для умножения в столбик ручкой на бумаге этот метод неудобен. У него нет такой элегантной формы записи, им сложнее овладеть, да и выигрыша во времени в бытовых ситуациях он не дает. Но для компьютерного умножения очень длинных чисел это заметное улучшение.
Как это бывает в математике, после первого шага началась гонка за наилучшим результатом. Всегда приятно поставить рекорд: найти больше всех цифр числа π или самое большое простое число.
Немецкие математики Арнольд Шёнхаге и Фолькер Штрассен в 1971 году придумали, как использовать быстрое преобразование Фурье, чтобы умножать большие числа еще быстрее. Они свели задачу умножения чисел к задаче умножения многочленов, и применили к таким функциям быстрое преобразование Фурье. (По версии журнала Computing in Science & Engineering БПФ – один из 10 важнейших алгоритмов ХХ столетия.) Теперь можно было умножать за
операций. И в XX веке все компьютеры так и умножали. Но сами Арнольд Шёнхаге и Фолькер Штрассен выдвинули две гипотезы: 1) что можно умножать еще быстрее – за N log ( N ), и 2) что это уже нижняя граница, быстрее умножить не получится.
В 2007 году Мартин Фюрер предложил алгоритм еще шустрее, но который все же не достиг идеала в N log ( N ).
Его достигли в этом году Дэвид Харви и Йорис ван дер Ховен (DAVID HARVEY AND JORIS VAN DER HOEVEN). Они опубликовали два новых алгоритма , которые оба требуют N log ( N ) простых операций. Первый технически проще, но опирается на недоказанное предположение о простых числах в арифметических прогрессиях. Второй требует изощренной техники, но зато достигает идеала без всяких недоказанных предположений.
Первая гипотеза Шёнхаге и Штрассена таким образом доказана, а вторая еще ждет своих героев. Математики научились умножать быстро и еще быстрее, но пока не знают: правда ли, что быстрее уже некуда.
Читайте также: