计算机乘法算法流程,布斯乘法算法
布斯乘法算法是计算机中⼀种利⽤数的2的补码形式来计算乘法的算法。该算法由安德鲁·唐纳德·布斯于1950 年发明,当时他在伦敦⼤学伯克贝克学院做晶体学研究。布斯曾使⽤过台式计算器,由于⽤这种计算器来做移位计算⽐加法快,他发明了该算法来加快计算速度。布斯算法在计算机体系结构学科中备受关注。
中⽂名
布斯乘法算法
外⽂名
Booth's multiplication algorithm发明⼈
安德鲁·唐纳德·布斯
发明时间
1950 年
布斯乘法算法算法描述
编辑
语⾳
对于 N 位乘数 Y,布斯算法检查其2的补码形式的最后⼀位和⼀个隐含的低位,命名为 y[i-1] ,初始值为 0 。对于 y[i], i = 0, 1, ..., N -1,考察 y[i] 和 y[i - 1 ]。当这两位相同时,存放积的累加器 P 的值保持不变。当 y[i] = 0 且 y[i - 1] = 1 时,被乘数乘以 2^i 加到 P 中。当 y[i]= 1 且 y[i - 1] = 0 时,从 P 中减去被乘数乘以 2^i 的值。算法结束后, P 中的数即为乘法结果。
该算法对被乘数和积这两个数的表达⽅式并没有作规定。⼀般地,和乘数⼀样,可以采⽤2的补码⽅式表达。也可以采⽤其他计数形式,只要⽀持加减法就⾏。这个算法从乘数的最低位执⾏到最⾼位,从 i = 0 开始,接下来和 2^i 的乘法被累加器 P 的算术右移所取代。较低位可以被移出,加减法可以只在 P 的前 N 位上进⾏。[1]
布斯乘法算法典型实现
编辑
语⾳
布斯算法的实现,可以通过重复地在 P 上加两个预设值 A 和 S 其中的⼀个,然后对 P 实施算术右移。设 m 和 r 分别为被乘数和乘数,再令 x 和 y 分别为 m 和 r 中的数字位数。
确定 A 和 S 的值,以及 P 的初始值。这三个数字的总长度应等于( x + y + 1 ):
对于 A ,以 m 的补码值填充前x位(最靠左的位),⽤零填满剩下的( y + 1 )位;
对于 S ,以( - m )的补码值填充前x位,⽤零填满剩下的( y + 1 )位;
对于 P :⽤0填满最左的 x 位,将 r 的值附加在尾部;最右⼀位⽤零占位(辅助位,当i=0时i-1=-1,指的就是这个辅助位);
考察 P 的最右两位:
如果等于 01,求出 P + A 的值,忽略上溢;
如果等于 10,求出 P + S 的值,忽略上溢;
如果等于 00,不做任何运算,在下⼀步中直接采⽤ P 的值;
如果等于 11,不做任何运算,在下⼀步中直接采⽤ P 的值。
对第 2 步中得到的值进⾏算术右移⼀位,并将结果赋给 P ;
重复第 2 步和第 3 步,⼀共做 y 次;
舍掉 P 的最右⼀位,得到的即为 m 和 r 的积。
换另⼀种说法:把前x位⽤⼀个单独的数R0表⽰,中间y位⽤另⼀个数R1表⽰,辅助位⽤Z表⽰ 在这⾥,要通过重复的把R0加上m或者减去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的值来判断怎么加减了:
如果为01,则R0+m,进位忽略。然后R0,R1,Z右移⼀位,再下⼀步判断,直到把R1的每⼀位都判断过后为结束
如果为10,则R0-m,借位忽略(只要x位的R0的值)。然后R0,R1,Z右移⼀位,再下⼀步判断,直到把R1的每⼀位都判断过后为结束
如果为00或是11,则R0的值保持不变。然后R0,R1,Z右移⼀位,再下⼀步判断,直到把R1的每⼀位都
判断过后为结束
booth算法乘法例题讲解
最后是结果,结果就是R0并上R1的值。⽐如R0=3,R1=25,结果就是325.
注意:在实际应⽤中,“减去m”多⽤“加上-m”来代替。[2]
布斯乘法算法算法原理
编辑
语⾳
考虑⼀个由若⼲个0包围着若⼲个1的正的⼆进制乘数,⽐如00111110,积可以表达为:
其中,M代表被乘数。变形为下式可以使运算次数可以减为两次:
事实上,任何⼆进制数中连续的1可以被分解为两个⼆进制数之差:
因此,我们可以⽤更简单的运算来替换原数中连续为1的数字的乘法,通过加上乘数,对部分积进⾏移位运算,最后再将之从乘数中减去。它利⽤了我们在针对为零的位做乘法时,不需要做其他运算,只需移位这⼀特点,这很像我们在做和99的乘法时利⽤99=100−1这⼀性质。这种模式可以扩展应⽤于任
何⼀串数字中连续为1的部分(包括只有⼀个1的情况)。那么,
布斯算法遵从这种模式,它在遇到⼀串数字中的第⼀组从0到1的变化时(即遇到01时)执⾏加法,在遇到这⼀串连续1的尾部时(即遇到10时)执⾏减法。这在乘数为负时同样有效。当乘数中的连续1⽐较多时(形成⽐较长的1串时),布斯算法较⼀般的乘法算法执⾏的加减法运算少。[1]
参考资料
1.
Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.
2.
Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。