俄式乘法

来自计算思维百科
跳转至: 导航搜索

俄式乘法又称作俄国农夫法,它是对两个正整数相乘的一种算法,这种算法不是很高效,但是它的乘法过程非常有趣。

基本概念

据说从前俄罗斯的农民使用过一种乘法,只需要用到2的乘除表。其方法是有系统地将被乘数除以2,同时将乘数乘以2。例如计算50x65,这个过程展示在下面这个表中。

n        

m

附加值

 

50

65

 

 

25       

130

 

50除以2,65乘以2,这个乘积值没有变化

12       

260

130

25除以2,130乘以2,因为25除以2有余数1,所以增加一个附加值130

6        

520

 

12除以2,260乘以2

3       

1040

 

6除以2,520乘以2

1        

2080

1040

3除以2,520乘以2,因为3除以2有余数1,所以增加一个附加值1040

         

 

 

n*m为2080+1040+130=3250

应用范围

可以用于一些不太大的数乘法快速计算,也被广泛用于硬件设计中。

使用方法及步骤

假设n和m是两个正整数,

1当n为偶数,n*m=n/2 * 2m;当n为奇数,n*m=(n-1)/2 * 2m+m

2若两数形如1*m=m,则结束;否则重复1

3将计算中产生的额外加数全部相加即得两数乘积。

应用案例

应用1-移位实现二进制数的折半和加倍

案例:以十进制数39为例,来计算39x2在机器中的表现形式

解决步骤:

39x2,利用俄式乘法我们列出表格如下:

n      

m

 

余数(n/2)

39                  

2

n为奇数(+2)   

1

19      

4=22

n为奇数(+22

1

9       

8=23

n为奇数(+23)

1

4       

16=24

 

0

2        

32=25

 

0

1        

64=26

n为奇数(+26)

1

         

 

n*m为26+23+22=78

 

从上面的表格里我们可以看出39/2的过程中产生的余数倒序即为其2进制表示,即将被乘数减半挑出奇数的过程就是将一个十进制转为二进制的过程;当乘以2时,就相当于所有被乘数为奇数的项上/2即末尾多出了一位,也就是计算机中的移位操作的原理。

可以体现的计算思维

该算法只包括折半、加倍和相加这几个简单的操作,将两个数的乘法转化为较简单的操作,而计算机中涉及到的加倍、减半都是利用了这个算法思想来简化为移位操作,这正是计算思维中问题约简的一个体现。