俄罗斯农夫算法

troy

俄罗斯农夫算法 今天做题的时候，偶然在网上看到了一个十分有趣的算法，据说是俄罗斯的农夫发明的。特别适合在计算机里面算整数乘法。 我们来看简单的等式 a * b = (a /2 )* (2 * b) (如果a是偶数) a * b = ((a-1)/2 )* (2 * b) + b (如果a是奇数) 我们来看看运算步骤如下表 比如我们要计算 77 * 33 a b 77 33 38 66 +33 19 132 9 264 +132 4 528 +264 2 1056 1 2112 那么结果就是 2112 + 264 + 132 + 33 = 2541 分析：在计算机中除2与乘2的操作是很快的，用位运算就可以了，而且对于很大的数来讲，这种方法也是可行的，因为对这种算法讲，a是以指数下降的，即使一个32位才能表示的整数也只要移位31次就可以为1，在机器层面讲，乘法是比移位慢的多的操作。 因此，这个算法对整数计算是很有实际意义的！ 自己写了个C++程序^-^[不是大数的] #include int mul(int a,int b) { int r=0; if(a==1) return b; if(a%2==1) r+=b; return r+mul(a>>1,b<<1); } int main() { int a,b; scanf("%d%d",&a,&b); printf("%d\n",mul(a,b)); return 0; }

cauchy

看上去不错 不知道用在高精度上的效果怎么样 如果用数组存，位移就很烦 顺便问一下：楼主做什么题？

troy

做ACM题的时候，描述里提到了农夫算法~~ 高精度的话我不算太熟。一般人用数组时候是每个int表示0-9，就是表示1位数。因为int型的最大值为0x7fffffff(2147483647)，所以你也可以设定每个int最大表示999999999，就是表示9位数。有空编个程序看看。

cauchy

可能这个算法适用于汇编 高精度计算一般用10000进制来优化 每个int存大了乘时会溢出

troy

也许吧，我也没试过

zed

复杂度为O(n)次长度为n的大数加法或移位，也就是O(n^2)的算法，所以不适合大数乘法计算。 其实上面过程同我们手工乘法过程没有任何区别（二进制下）

gxqcn

楼上说的极是。

troy

嗯，理解了。 另外问一下，写大数的话，怎么样提供运算效率。

无心人

看上去很美的算法而已 现代计算机的乘都很快 所以普通乘效率很高 连高级的快速算法都要在大数上才显示优势