计算机如何对两个数字进行乘法,例如100 * 55。
我的猜测是计算机通过重复加法来实现乘法。当然,对于整数来说这可能是正确的。但对于浮点数,必须有其他逻辑。
注意:这是在一次面试中提出的问题。
计算机如何对两个数字进行乘法,例如100 * 55。
我的猜测是计算机通过重复加法来实现乘法。当然,对于整数来说这可能是正确的。但对于浮点数,必须有其他逻辑。
注意:这是在一次面试中提出的问题。
重复加法将是一种非常低效的乘数方法,想象一下用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)
通常使用的方法被称为部分积,就像人类一样,例如对于100*55
,它会执行以下操作
100 X
55
----
500 +
500
----
旧的方法基本上使用了一种移位累加算法,其中您在移动第二个数字的每个数字时保留总和并移动部分乘积。这种方法的唯一问题是数字存储为2补码,因此在移位时无法进行纯位逐位乘法。
现在大多数优化都能够在仅1个周期中将所有部分求和,使您可以更快地进行计算并更容易地实现并行化。
在这里看看:http://en.wikipedia.org/wiki/Binary_multiplier
最后,您可以找到一些实现,例如
一种使用二进制长乘法的方法:
01100100 <- 100
* 00110111 <- 55
----------
01100100
01100100
01100100
01100100
01100100
---------------
1010101111100 <- 5500
这种方法有时被称为“移位相加法”(shift and add method)。
好的,这就给你。我在很久以前(1987年)写了这篇文章,所以有些东西已经改变了,而有些仍然保持不变...
计算机使用 Booth 算法或其他进行移位和加法运算的算法。如果您曾经学习过计算机体系结构课程,那么计算机体系结构书籍应该是学习这些算法的好地方。
我刚编写了一个简单的程序,使用长乘法算法来计算文件中存储的两个数字的乘积。它可以计算两个数相乘,每个数都超过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
直观上,您可以通过使用移位来最小化重复相加。
就浮点数而言,这篇文章看起来非常相关:
http://oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_14/CH14-1.html#HEADING1-19