俄罗斯农夫算法

引⼊问题

　　众所周知，位运算⽐加减乘除法省时间。

　　那么问题来了，给你⼀个⾮⾼精度数a和b，要求你不⽤任何乘除号完成a*b的运算，如何实现。

写在第⼆

　　当当当当，俄罗斯农夫算法闪亮出场。

　　当我真的开始着⼿研究这个算法时，惊讶于这⽅⾯的资料之少。想来如果可以重载⼀下运算符的话，如果能把每⼀边乘法的时间都进⾏优化的话，说不定能使整个算法的效率⼤⼤提⾼。然⽽当我花了半个⼩时才写出⼀个正确代码后，不仅感慨⽤这么多代码去换⼀丝丝丝的时间是否真的值得。虽然如此，即以决定，就把这个详细介绍俄罗斯农夫算法的博客写完吧。

理解算法　

规则：什么是俄罗斯农民乘法？我要怎么使⽤它？原理：俄罗斯农民乘法的⼯作原理是什么？

联系：俄罗斯农民乘法是如何与⼆进制相关联的呢？

什么是俄罗斯农民乘法？我要怎么使⽤它？我们绝⼤多数⼈学的都是这样做⼤数字乘法的： 86 x 57 ------ 602 + 4300 ------ 4902

如果你懂得乘法算式，那么这种“长式相乘”的⽅法是快速和相对简单的。不过，还有许多其它的计算⽅法。其中之⼀通常被称之为俄罗斯农民算法。使⽤它时不需要你懂得乘法算式，你只需要将数字加倍，减半再进⾏合计。具体规则如下： * 把每⼀个数字分别写在列头。

* 将头⼀列的数字加倍，将第⼆列的数字减半。

如果在第⼆列的数字是奇数，将它除以⼆并把余数去掉。 * 如果第⼆列的数字是偶数，将其所在⾏删除。 * 继续加倍、减半和删除直到第⼆列的数字为1。

* 将第⼀列中剩余的数字相加。于是就得出了根据原始数字计算出的结果。让我们以计算57乘以86为例。 把每⼀个数字分别写在列头。 57 86

将头⼀列的数字加倍，将第⼆列的数字减半。 57 86 114 43

如果第⼆列的数字是偶数，将其所在⾏删除。 57 86 114 43

继续加倍、减半和删除直到第⼆列的数字为1。 57 86 114 43 228 21 456 10

912 5 1824 2 3648 1

将第⼀列中剩余的数字相加。于是就得出了根据原始数字计算出的结果。 57 86 114 43 228 21 456 10 912 5 1824 2 + 3648 1 4902

真实的俄罗斯农民们可能会⽤好⼏碗的鹅卵⽯来记录他们加倍的数字，⽤来代替写在列⾥⾯的数字。（当然，他们或许不会对我们的例⼦⾥那么⼤的数字感兴趣，要知道四千多个鹅卵⽯可是很难操作的哟！）俄罗斯的农民们并不是唯⼀使⽤这种算法的⼈，在数千年之前古埃及⼈就已经发明了类似的⽅法，⽽同时在今天的计算机中仍然在使⽤与之相关的程序。俄罗斯农民乘法的⼯作原理是什么？让我们以计算9×8为例： 9 8 18 4 36 2 72 1

72是唯⼀⼀个留在左列⾥的数字，所以我们的答案就是72。请注意我们在其中⼀边乘以2，在另⼀边除以2，2 × 1/2 = 1，所以对最终结果并没有影响:

9 * 8

= 18 * 4

= 36 * 2 = 72 * 1

我们刚才对数字进⾏了不同的组合，⽽对结果并没有影响。如果我们将8乘以9，我们应该得到同样的答案。那我们能⽤同样的⽅法来解释吗？ 8 9 16 4 32 2 + 64 1 72

当我们将9除以2，我们将余数去除因为9是⼀个奇数。由于我们“丢失”了⼀个，所以接下去的产⽣的每⼀⾏都会变得更⼩。让我们从第⼀⾏和第⼆⾏中寻找不同。 8*9 - 16*4 = 72 - 64 = 8

我们可以重写个减法来计算总和：

8 * 9

= 16 * 4 + 8

因为我们的结果少了8,所以我们就必须在最后把8给加回去。我们可以把这种追加认为是恢复了1组8，就是在前⾯我们丢掉的余数1。在不同的问题⾥，我们有可能会恢复不同组的数字。俄罗斯农民乘法是如何与⼆进制相关联的呢？

⼆进制是以2代替10来作为基数的进制。这就意味着在位数上我们要⽤2的次⽅来代替10的次⽅：代替个位、⼗位和百位，⼆进制有⼀位、⼆位和四位等等。例如，14在⼆进制⾥表⽰为1110： 1110 (base 2)

= 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 8 + 4 + 2 + 0 = 14

俄罗斯农民乘法能快速有效的将数字转换成⼆进制模式，将它们相乘，然后再转换回我们⽇常所使⽤的数字系统。这种关联两种进制的能⼒并不惊奇，因为⼆进制使⽤2作为基数，同时俄罗斯农民乘法使⽤2来相乘和相除。为了使这种关联更为清晰，让我们来研究⼀下12*13。减半

你能够通过对数字进⾏重复的除以2并且留下余数来将其转换成⼆进制。让我们试⼀下12： 12/2 = 6 余数 0 6/2 = 3 余数 0 3/2 = 1 余数 1 1/2 = 0 余数 1

从下往上读取余数，我们得到了1100,所以12所对应的⼆进制数字为1100。

这种转换⽅法的⼯作原理是什么呢？让我们再⼀次试着⽤同样的⽅法将12减半。这⼀次，我们将把所有的数字都基于⼆进制（当然，数字2在⼆进制⾥头是10）。 1100/10 = 110 余数 0 110/10 = 11 余数 0 11/10 = 1 余数 1 1/10 = 0 余数 1

将数字除以2然后再取其余数，最终我们所得到的就是基于⼆进制的数字。关于数字12，到⽬前为⽌我们所得出的： 12 = 1100 (base 2)

= 1*2^3 + 1*2^2 + 0*2 + 0*1 = 2^3 + 2^2 = 8 + 4

通过反复的对12减半，我们就可以将其分解成2的次⽅。因式分解

我们现在来试着将12乘以13。⼀种⽅法是使⽤长式相乘： 13 * 12 ---- 26 + 130 ----- 156

注意我们通过将 2*13 和 10*13 相加来得出我们的最终结果。它的⼯作原理是因式分解： 12 * 13

= (2 + 10) * 13 = 2*13 + 10*13

当然，我们能将12分解成任何我们想要的形式，并且仍然能得到正确的答案。现在让我们⽤前⾯所做的⼯作来将这个题⽬分解成2的次⽅： 12 * 13

= (4 + 8) * 13

= (2^2 + 2^3) * 13 = 2^2 * 13 + 2^3 * 13

如果我们能将 13 乘以 2^2 和 2^3，那我们就完成了。加倍

重复的将⼀个数字乘以2的次⽅。让我们试试将13加倍： 数字 累计相乘过程 2的次⽅ 13 13 2^0 26 13*2 2^1 52 13*2*2 2^2 104 13*2*2*2 2^3

我们的图表告诉我们 2^2 * 13 + 2^3 * 13 = 52 + 104 = 156，所以 12 * 13 = 156，我们完成计算了。把所有的⼀切放在⼀起

我们刚才通过重复的减半和相乘将12转成⼆进制模式，然后将其与13相乘。俄罗斯农民算法做得是同样的事情，但是它节省了很多的步骤，过程也更快。让我们结合我们加倍和减半的步骤来⽐较这两种⽅法的不同。数字加倍 累计相乘过程 2的次⽅ 数字减半 除以2 余数 13 13 2^0 12 12/2 = 6 0 26 13*2 2^1 6 6/2 = 3 0 52 13*2*2 2^2 3 3/2 = 1 1 104 13*2*2*2 2^3 1 1/2 = 0 1

加粗的列使⽤的是俄罗斯农民乘法。注意当余数列为0时，其所对应的俄罗斯乘法⾏要删去。

算法实现

算法公式

a*b = (a/2)*(b*2) a为偶数 ((a-1)/2)*(b*2))+b a为奇数 算法思想

回溯，位运算，分治 设计⽅法

先对输⼊的2个数判断正负，⽤⼀个flag去记录结果的正负。

通过位运算的 & 让m去和1做与运算，判断m的奇偶性，分奇偶性进⾏不同的处理。 ⽤s记录运算的结果。因为不能⽤乘除法，所以⽤移位运算的左移1位相当乘以2，⽤移位运算的右移1位相当除以2。 复杂度时间复杂度O(1)

空间复杂度O(1) 代码参考PASCAL代码：

var n,m,sum,flag:longint;procedure change;begin

flag:=0; if m<0 then begin

flag:=1-flag; m:=0-m; end; if n<0 then begin

flag:=1-flag; n:=0-n; end; sum:=0;end;

//判断正负号

procedure farmer;var x:longint;begin

while (m>=1) do begin

if (m and 1=1) then begin

sum:=sum+n; m:=(m-1) shr 1; n:=n shl 1; end else begin

m:=m shr 1; n:=n shl 1; end; end;end;

procedure printf;begin

if flag<>0 then write('-'); write(sum);end;

begin

readln(n,m); change; farmer; printf;end.

View Code

C++代码：

#includevoid main(){

int m,n,s,flag;

while(scanf(\"%d%d\",&m,&n)==2) {

flag=0; if(m<0) {

flag=1-flag; m=0-m; }

if(n<0) {

flag=1-flag; n=0-n;

} s=0;

while(m>=1) {

if(m&1==1) {

s+=n;

m=(m-1)>>1; n=n<<1; } else {

m=m>>1; n=n<<1; } }

if(flag==0)

printf(\"%d\\n\",s); else

printf(\"-%d\\n\",s); }}

View Code