logo标签列表

计算机如何对两个数字进行乘法运算？

computer-sciencemathematical-optimization
33

计算机如何对两个数字进行乘法，例如100 * 55。

我的猜测是计算机通过重复加法来实现乘法。当然，对于整数来说这可能是正确的。但对于浮点数，必须有其他逻辑。

注意：这是在一次面试中提出的问题。

5
当然不是，请查看“乘法算法”。 - Nick Dandoulakis
那么你的意思是根据数字的长度或值使用不同的算法。 - ckv
现代X86处理器如何计算乘法？- Dadda树。 https://en.wikipedia.org/wiki/Dadda_multiplier。在现代主流CPU中，固定宽度整数（例如32位或64位）的乘法是恒定时间的，例如，在现代x86上进行标量整数乘法的完全流水线化的3个周期延迟（每个时钟1个）。 x86_64：IMUL是否比2x SHL + 2x ADD更快？ /每个汇编指令需要多少CPU周期？ - Peter Cordes
9个回答
40

重复加法将是一种非常低效的乘数方法，想象一下用85324154乘以1298654825会有多慢。使用二进制的长乘法要快得多。

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)
18

通常使用的方法被称为部分积，就像人类一样，例如对于100*55，它会执行以下操作

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

旧的方法基本上使用了一种移位累加算法，其中您在移动第二个数字的每个数字时保留总和并移动部分乘积。这种方法的唯一问题是数字存储为2补码，因此在移位时无法进行纯位逐位乘法。

现在大多数优化都能够在仅1个周期中将所有部分求和，使您可以更快地进行计算并更容易地实现并行化。

在这里看看：http://en.wikipedia.org/wiki/Binary_multiplier

最后，您可以找到一些实现，例如

因此，在计算机处理器中，没有一种固定的方式或算法。根据数据的不同，选择不同的算法。如果我有错误，请纠正我。 - ckv
即使这样，你仍然需要将100x5乘以两次，不是吗？ - bragboy
在十进制中，你需要将1005和105相乘，但在二进制中，你只需要用1或0相乘，也就是说你要么加上它，要么不加。 - David Sykes
6

一种使用二进制长乘法的方法：

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

这种方法有时被称为“移位相加法”（shift and add method）。

5
1
很棒的文章，非常有帮助。 - Nick
2
请在您的回复中包含文章摘要，链接可能会在未来失效。 - JohannesB
1
这是一篇关于“高速整数乘除法”的文章，作者是Donald A. Branson。该文章发表于1987年7月的The Transactor杂志（第8卷，第01期，第42页）。您也可以在此处找到一份副本：https://archive.org/details/transactor-magazines-v8-i01/page/n43/mode/2up - Keeler
3

计算机使用 Booth 算法或其他进行移位和加法运算的算法。如果您曾经学习过计算机体系结构课程，那么计算机体系结构书籍应该是学习这些算法的好地方。

2
要将两个浮点数相乘，需要执行以下步骤：
1. 将尾数相乘 2. 将指数相加 3. 规范化结果（小数点位于第一个非零数字之后）
因此，在十进制下，要将5.1E3和2.6E-2相乘：
1. 将尾数相乘 => 5.1 * 2.6 = 13.26（注意：只要跟踪小数点的位置，就可以使用整数乘法来完成此步骤） 2. 将指数相加 => 3 + -2 = 1 3. 得到结果为13.26E1 4. 规范化13.26E1 => 1.326E2
1

我刚编写了一个简单的程序，使用长乘法算法来计算文件中存储的两个数字的乘积。它可以计算两个数相乘，每个数都超过10亿。

示例：

            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

1
1
答案是，这取决于情况。正如其他人指出的那样，您可以使用与我们在学校学到的相同的算法，但使用二进制代替。但对于小数字，还有其他方法。
假设您想要将两个8位数字相乘，可以使用一个大查找表来完成。只需将两个8位数字连接起来形成一个16位数字，并使用该数字索引到包含所有乘积的表中。
或者，您可以直接使用一组大门网络计算函数。然而，这些门网络在大数乘法方面往往变得非常难以控制。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接