Как компьютер умножает 2 числа?
Как компьютер работает, умножение на 2 числах говорят 100 * 55.
Мое предположение было то, что компьютер сделал повторенное дополнение для достижения умножения. Конечно, это могло иметь место для целых чисел. Однако для чисел с плавающей точкой должна быть некоторая другая логика.
Примечание: Это спросили в интервью.
9 ответов
Повторное сложение было бы очень неэффективным способом умножения чисел, представьте себе умножение 1298654825 на 85324154. Намного быстрее просто использовать длинное умножение в двоичном формате.
1100100
0110111
=======
0000000
-1100100
--1100100
---0000000
----1100100
-----1100100
------1100100
==============
1010101111100
Для чисел с плавающей запятой используется научная запись.
100 is 1 * 10^2 (10 to the power of 2 = 100)
55 is 5.5 * 10^1 (10 to the power of 1 = 10)
Чтобы умножить их вместе, умножьте мантиссы и сложите экспоненты
= 1 * 5.5 * 10^(2+1)
= 5.5 * 1000
= 5500
Компьютер делает это, используя двоичные эквиваленты
100 = 1.1001 * 2^6
55 = 1.10111* 2^5
-> 1.1001 * 1.10111 * 2^(6+5)
Один из способов - использовать длинное умножение в двоичном формате:
01100100 <- 100
* 00110111 <- 55
----------
01100100
01100100
01100100
01100100
01100100
---------------
1010101111100 <- 5500
Иногда это называют методом сдвига и сложения .
Компьютеры используют алгоритм Бута или другие алгоритмы, которые выполняют сдвиг и сложение для арифметических операций. Если вы изучали курсы компьютерной архитектуры, книги по компьютерной архитектуре должны быть хорошим местом для изучения этих алгоритмов.
Ответ в зависимости от обстоятельств. Как отмечали другие, вы можете использовать тот же алгоритм, которому нас учили в школе, но вместо этого используйте двоичный код. Но для небольшого количества есть другие способы.
Допустим, вы хотите умножить два 8-битных числа, это можно сделать с помощью большой справочной таблицы. Вы просто объединяете два 8-битных числа, чтобы сформировать 16-битное число, и используете этот nunber для индексации в таблице со всеми продуктами.
Или у вас может быть просто большая сеть вентилей, которая вычисляет функцию напрямую. Эти сети ворот, как правило, становятся довольно громоздкими для умножения больших чисел.
Для умножения двух чисел с плавающей запятой используется следующая процедура:
- Умножение мантисс
- Сложение экспонент
- Нормализация результата (десятичная точка ставится после первой ненулевой цифры)
Итак, по основанию 10 для умножения 5.1E3 и 2. 6E-2
Умножить мантиссы => 5.1 * 2.6 = 13.26 (NB это можно сделать с целочисленным умножением, пока вы отслеживаете, где должна быть десятичная точка)
Сложить экспоненты => 3 + -2 = 1
Получаем результат 13.26E1
Нормализовать 13.26E1 => 1.326E2
Метод, который обычно используется, называется частичные продукты, как это делают люди, поэтому, например, имея 100*55, получится что-то вроде
100 X
55
----
500 +
500
----
В основном старые подходы использовали алгоритм сдвига и накопления, в котором вы сохраняете сумму, сдвигая частичные продукты для каждой цифры второго числа. Единственная проблема этого подхода заключается в том, что числа хранятся в двухкомпонентном виде, поэтому вы не можете выполнять простое умножение бит в бит при сдвиге.
Сегодня большинство оптимизаторов способны суммировать все частицы всего за 1 цикл, что позволяет ускорить вычисления и упростить распараллеливание.
Посмотрите здесь: http://en.wikipedia.org/wiki/Binary_multiplier
В итоге вы можете найти некоторые реализации, такие как
Интуитивно вы можете минимизировать повторные сложения, используя также сдвиг.
В терминах float эта статья выглядит довольно актуальной:
http://oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_14/CH14-1.html#HEADING1-19
Ладно, поехали. Я написал это некоторое время назад (1987 год!), Поэтому некоторые вещи изменились, а другие остались прежними ...
Я просто кодирую простую программу умножения двух чисел, хранящихся в двух строках файла, с использованием алгоритма длинного умножения. Он может умножать два числа, которые содержат более 1 миллиарда чисел друг в друге
Пример:
23958233
5830 ×
------------
00000000 ( = 23,958,233 × 0)
71874699 ( = 23,958,233 × 30)
191665864 ( = 23,958,233 × 800)
119791165 ( = 23,958,233 × 5,000)
Исходный код:
Пожалуйста, просмотрите и оставьте свой комментарий http://code.google.com/p/juniormultiply/source/browse/#svn/trunk/src