Как компьютер умножает 2 числа?

Как компьютер выполняет умножение на 2 числа, скажем, 100 * 55.

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

Примечание. Это было задано в интервью.

Ответ 1

Повторное добавление было бы очень неэффективным способом умножения чисел, представьте, что вы умножаете 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)

Ответ 2

Обычно используемый метод называется частичными продуктами, такими как люди, поэтому, например, имея 100*55, он сделает что-то вроде

  100 X
   55
 ----
  500 +
 500
 ----

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

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

Посмотрите здесь: http://en.wikipedia.org/wiki/Binary_multiplier

В конце вы можете найти некоторые реализации, такие как

Ответ 3

Один из способов - использовать длинное умножение в двоичном формате:

       01100100 <- 100
     * 00110111 <- 55
     ----------
       01100100
      01100100
     01100100
   01100100
  01100100
---------------
  1010101111100 <- 5500

Это иногда называют сдвигом и добавлением.

Ответ 4

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

Ответ 5

Хорошо, вот иди. Я написал это некоторое время назад (1987!), Поэтому некоторые вещи изменились, в то время как другие остались теми же...

http://moneybender.com/transactor_article.pdf

Ответ 6

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

В терминах поплавков эта статья выглядит довольно актуальной:

http://oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_14/CH14-1.html#HEADING1-19

Ответ 7

Ответ: это зависит. Как указывали другие, вы можете использовать тот же алгоритм, что и в школе, но вместо этого использовали двоичный код. Но для небольших чисел есть и другие способы.
Скажем, что вы хотите размножить два 8-битных номера, это можно сделать с помощью большой таблицы поиска. Вы просто объединяете два 8-битных числа, чтобы сформировать 16-битное число, и используйте этот nunber для индексации в таблицу со всеми продуктами.
Или вы можете просто иметь большую сеть ворот, которая напрямую вычисляет функцию. Эти сети ворот, как правило, становятся довольно громоздкими для умножения больших чисел.

Ответ 8

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

Умножьте мантиссы
Добавьте экспоненты
Нормализовать результат (десятичная точка появляется после первой ненулевой цифры)

Итак, в базе 10 для умножения 5.1E3 и 2.6E-2

Умножьте мантиссы = > 5.1 * 2.6 = 13.26 (это можно сделать с помощью целочисленного умножения, если вы отслеживаете, где должна быть десятичная точка)

Добавьте экспоненты = > 3 + -2 = 1

Дает нам результат 13.26E1

Нормализовать 13.26E1 = > 1.326E2

Ответ 9

Я просто кодирую простую программу, умножая два числа, хранящихся в 2 строках в файле, используя алгоритм длительного умножения. Он может умножать два числа, которые имеют более 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