布斯乘法算法

维基百科,自由的百科全书
跳转至: 导航搜索

布斯乘法算法英语Booth's multiplication algorithm)是计算机中一种利用数的2的补码形式来计算乘法的算法。该算法由安德鲁·唐纳德·布斯于 1950 年发明,当时他在伦敦大学柏贝克学院晶体学研究。布斯曾使用过一种台式计算器,由于用这种计算器来做移位计算比加法快,他发明了该算法来加快计算速度。布斯算法在计算机体系结构学科中备受关注。

算法描述[编辑]

对于 N 位乘数 Y,布斯算法检查其2的补码形式的最后一位和一个隐含的低位,命名为 y-1 ,初始值为 0 。对于 yi, i = 0, 1, ..., N - 1,考察 yiyi - 1 。当这两位相同时,存放积的累加器 P 的值保持不变。当 yi = 0 且 yi - 1 = 1 时,被乘数乘以 2i 加到 P 中。当 yi = 1 且 yi - 1 = 0 时,从 P 中减去被乘数乘以 2i 的值。算法结束后, P 中的数即为乘法结果。

该算法对被乘数和积这两个数的表达方式并没有作规定。一般地,和乘数一样,可以采用2的补码方式表达。也可以采用其他计数形式,只要支持加减法就行。这个算法从乘数的最低位执行到最高位,从 i = 0 开始,接下来和 2i 的乘法被累加器 P 的算术右移所取代。较低位可以被移出,加减法可以只在 P 的前 N 位上进行。[1]

典型实现[编辑]

布斯算法的实现,可以通过重复地在 P 上加两个预设值 A 和 S 其中的一个,然后对 P 实施算术右移。设 mr 分别为被乘数和乘数,再令 xy 分别为 mr 中的数字位数。

  1. 确定 AS 的值,以及 P 的初始值。这三个数字的总长度应等于( x + y + 1 ):
    1. 对于 A ,以 m 的填充前x位(最靠左的位),用零填满剩下的( y + 1 )位;
    2. 对于 S ,以( - m )的值填充前x位,用零填满剩下的( y + 1 )位;
    3. 对于 P :用0填满最左的 x 位,将 r 的值附加在尾部;最右一位用零占位(辅助位,当i=0时i-1=-1,指的就是这个辅助位);
  2. 考察 P 的最右两位:
    1. 如果等于 01,求出 P + A 的值,忽略上溢;
    2. 如果等于 10,求出 P + S 的值,忽略上溢;
    3. 如果等于 00,不做任何运算,在下一步中直接采用 P 的值;
    4. 如果等于 11,不做任何运算,在下一步中直接采用 P 的值。
  3. 对第 2 步中得到的值进行算术右移一位,并将结果赋给 P
  4. 重复第 2 步和第 3 步,一共做 y 次;
  5. 舍掉 P 的最右一位,得到的即为 mr 的积。

换另一种说法:把前x位用一个单独的数R0表示,中间y位用另一个数表示R1表示,辅助位用Z表示 在这里,要通过重复的把R0加上或者减去m来得到结果。具体如下: 初始值R0=0,R1=r.Z=0,此时来考查yi和yi-1这两位,在这里就是m的最后一位和Z的值。这里要说下为什么每次看的都是这两位了。 在下边每次运算后都会把R0,R1,Z中的值右移一次,RO的最后一位移入R1的高位,R1的最后一位移入Z。这里要注意的是在右移R0时,如果他的最高位是1,则移位后最高位用1填充,如果最高位是0,移位后最高位用0填充。 接下来要按m的最后一位和Z的值来判断怎么加减了:

    1. 如果为01,则R0+m,进位忽略。然后R0,R1,Z右移一位,再下一步判断,直到把R1的每一位都判断过后为结束
    2. 如果为10,则R0-m,借位忽略(只要x位的R0的值)。然后R0,R1,Z右移一位,再下一步判断,直到把R1的每一位都判断过后为结束
    3. 如果为00或是11,则R0的值保持不变。然后R0,R1,Z右移一位,再下一步判断,直到把R1的每一位都判断过后为结束

最后是结果,结果就是R0并上R1的值。比如R0=3,R1=25,结果就是325.

算法原理[编辑]

考虑一个由若干个 0 包围着若干个 1 的正的二进制乘数,比如 00111110,积可以表达为:

 M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^2 + 2^1) =  M \times 62

其中,M 代表被乘数。变形为下式可以使运算次数可以减为两次:

 M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^1) = M \times 62.

事实上,任何二进制数中连续的 1 可以被分解为两个二进制数之差:

 (\ldots 0 \overbrace{1 \ldots 1}^{n} 0 \ldots)_{2} \equiv (\ldots 1 \overbrace{0 \ldots 0}^{n} 0 \ldots)_{2} - (\ldots 0 \overbrace{0 \ldots 1}^{n} 0 \ldots)_2.

因此,我们可以用更简单的运算来替换原数中连续为 1 的数字的乘法,通过加上乘数,对部分积进行移位运算,最后再将之从乘数中减去。它利用了我们在针对为零的位做乘法时,不需要做其他运算,只需移位这一特点,这很像我们在做和 99 的乘法时利用 99 = 100 − 1 这一性质。 这种模式可以扩展应用于任何一串数字中连续为 1 的部分(包括只有一个 1 的情况)。那么,

 M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58
 M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \mbox{-1} \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^6 - 2^3 + 2^1) = M \times 58.

布斯算法遵从这种模式,它在遇到一串数字中的第一组从 0 到 1 的变化时(即遇到 01 时)执行加法,在遇到这一串连续 1 的尾部时(即遇到 10 时)执行减法。这在乘数为负时同样有效。当乘数中的连续 1 比较多时(形成比较长的 1 串时),布斯算法较一般的乘法算法执行的加减法运算少。

参考来源[编辑]

  1. ^ Chi-hau Chen. Signal processing handbook. CRC Press. 1988. 234. ISBN 9780824779566. 

延伸阅读[编辑]

  1. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [1]
  2. Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
  3. Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
  4. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.

外部链接[编辑]